Gottesman – Knillova věta - Gottesman–Knill theorem

v kvantové výpočty, Gottesman – Knillova věta je teoretický výsledek od Daniel Gottesman a Emanuel Knill, který uvádí, že obvody stabilizátoru, obvody, které se skládají pouze z bran z normalizátor qubit Skupina Pauli, také nazývaná Cliffordova skupina, může být dokonale simulována v polynomiálním čase na pravděpodobnostním klasickém počítači. Cliffordova skupina může být generováno pouze pomocí CNOT, Hadamard a fázových bran;^[1] a proto stabilizátor obvody lze konstruovat pouze pomocí těchto bran.

Důvod pro zrychlení kvantových počítačů dosud není zcela objasněn^{[Citace je zapotřebí ]}. Věta dokazuje, že pro všechny kvantové algoritmy se zrychlením, které spoléhá na zapletení, kterého lze dosáhnout pomocí CNOT a a Hadamard brána k vytváření zapletených stavů, tento druh zapletení sám o sobě neposkytuje žádnou výpočetní výhodu.

Existuje účinnější simulace obvodů stabilizátoru než konstrukce původní publikace^[1] s implementací.^[2]

Věta Gottesman – Knill byla publikována v jediné autorské práci Gottesmana, v níž připisuje Knillovi výsledek prostřednictvím soukromé komunikace.^[3]

Formální prohlášení

Věta: Kvantový obvod využívající pouze následující prvky lze efektivně simulovat na klasickém počítači:

1. Příprava qubits ve stavech výpočetní báze,
2. Kvantové brány ze skupiny Clifford (Hadamardovy brány, kontrolované NE brány, Phase Gate) a
3. Měření ve výpočetní bázi.

Věta Gottesman – Knill ukazuje, že i některé velmi zapletený stavy lze efektivně simulovat. Několik důležitých typů kvantových algoritmů používá pouze Cliffordovy brány, nejdůležitější jsou standardní algoritmy pro čištění zapletení a pro kvantovou korekci chyb. Z praktického hlediska byly obvody stabilizátoru simulovány v O (n logn) čas pomocí stav grafu formalismus.

Viz také

• Magická destilace

Reference

• S. Anders a H. J. Briegel (2006). Msgstr "Rychlá simulace obvodů stabilizátoru pomocí znázornění stavu grafu". Phys. Rev.A. 73: 022334. arXiv:quant-ph / 0504117v2. Bibcode:2006PhRvA..73b2334A. doi:10.1103 / PhysRevA.73.022334.
• Nielsen, Michael A.; Chuang, Isaac L. (2010). Kvantové výpočty a kvantové informace (2. vyd.). Cambridge: Cambridge University Press. ISBN  978-1-107-00217-3. OCLC  844974180.