QMA osztály

A komplexitáselméletben a QMA (az angol Quantum Merlin Arthur szóból ) az NP kvantumanalógja a klasszikus komplexitáselméletben és az MA analógja a valószínűségi elméletben. Ugyanúgy kapcsolódik a BQP -hez, mint az NP a P -hez, vagy az MA a BPP -hez .

Informálisan ez olyan nyelvek halmaza, amelyekre polinomiális kvantumbizonyítás létezik, amelyet egy időpolinomiális kvantum-algoritmus nagy valószínűséggel fogad el.

Definíció

Egy L nyelv akkor tartozik hozzá, ha létezik egy V kvantumalgoritmus időbeni polinom és egy p(x) polinom, amelyre: [1] [2] ${\mbox{QMA}}(c,s)$

$\forall x\in L$ , van olyan kvantumállapot , amelynek a valószínűsége, hogy V több mint . $|\psi\rangle$ $(|x\rangle ,|\psi \rangle )$ $c$
$\forall x\notin L$ , bármely kvantumállapot esetén annak a valószínűsége, hogy V kisebb lesz, mint . $|\psi\rangle$ $(|x\rangle ,|\psi \rangle )$ $s$

ahol a kvantumállapot p(x) qubittel. $|\psi\rangle$

Határozzuk meg az osztályt olyan osztályként , amely egyenlő . Valójában az állandók nem fontosak, és az osztály nem változik, ha a tetszőleges állandók nagyobbak, mint . Bármely és polinomra is igaz ${\mbox{QMA))$ ${\mbox{QMA}}({2}/{3}, 1/3)$ $c$ $s$ $c$ $s$ $q(n)$ $r(n)$

{\mbox{QMA}}\left({\frac {2}{3}},{\frac {1}{3}}\right)={\mbox{QMA}}\left({\ frac {1}{2}}+{\frac {1}{q(n)}},{\frac {1}{2}}-{\frac {1}{q(n)))\right) ={\mbox{QMA}}(1-2^{-r(n)},2^{-r(n)})

Kapcsolódó osztályok

${\mbox{QCMA}}$ (vagy [2] ) a név úgy hangzik, mint a kvantumklasszikus Merlin Arthur (vagy Merlin Quantum Arthur), a QMA analógja, de a (Merlin által küldött) bizonyítéknak egy szabályos karakterláncnak kell lennie. Nem ismert, hogy a QMA és a QCMA ugyanaz-e. ${\mbox{MQA))$

${\mbox{QIP}}(k)$ egy olyan nyelvosztály, amelyet kvantuminteraktív protokollok ismernek fel polinomidővel és k körrel, a QMA általánosítása, amelyben nem egy üzenetet, hanem k-t lehet továbbítani. A definícióból következik, hogy a QMA egybeesik a QIP-vel(1). Ismeretes, hogy a QIP(2) a PSPACE-ben található. [3]

${\mbox{QIP}}$ a QIP(k) nyelvek osztálya, ahol k-nek polinomiális lehet a qubitek száma. Ismeretes, hogy QIP(3) = QIP. [4] Az is ismert, hogy QIP = IP. [5]

${\mbox{QMA}}_{1}$ a Merlin Arthur kvantumprotokollok által ideális teljességgel elfogadott nyelvek osztálya.

Kapcsolatok más osztályokkal

A QMA-ról ismert, hogy

{\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{MA}}\subseteq {\mbox{QCMA}}\subseteq {\mbox{QMA}}\subseteq {\ mbox{PP}}\subseteq {\mbox{PSPACE}}

Az első beágyazás az NP definíciójából következik. A következő két felvétel helyes, mert a hitelesítők egyre erősebbek. Azt az állítást, hogy a PP tartalmaz QMA-t , Alekszej Kitaev és John Watrus bizonyította. A PP-t a PSPACE is tartalmazza .

Nem ismert, hogy ezek közül melyik zárvány szigorú.

Jegyzetek

↑ Dorit Aharonov és Tomer Naveh (2002), Quantum NP – A Survey, arΧiv : quant-ph/0210077v1 [quant-ph].
↑ 1 2 John Watrous (2008), Quantum Computational Complexity, arΧiv : 0804.3401v1 [quant-ph].
↑ Jain, Rahul; Upadhyay, Sarvagya; Vizes, John Kétüzenetes kvantuminteraktív bizonyítékok vannak a PSPACE-ban // FOCS '09: A számítástechnika alapjairól szóló 2009. évi 50. éves IEEE szimpózium előadásai . - IEEE Computer Society , 2009. - P. 534-543. — ISBN 978-0-7695-3850-1 .
↑ Vizes, JohnA PSPACE állandó körkörös kvantuminteraktív bizonyítási rendszerekkel rendelkezik // Theoretical Computer Science : folyóirat. - Essex, Egyesült Királyság: Elsevier Science Publishers Ltd., 2003. - Vol. 292 , sz. 3 . - P. 575-588 . — ISSN 0304-3975 . - doi : 10.1016/S0304-3975(01)00375-9 .
↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Vizes, John QIP = PSPACE // STOC '10: A 42. ACM szimpózium előadásai a számítástechnika elméletéről . - ACM, 2010. - P. 573-582. — ISBN 978-1-4503-0050-6 .

Irodalom

"Algoritmusok kvantumszámításhoz: diszkrét logaritmusok és faktorálás" PW Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Linkek

A. Kh. Shen, M. N. Vyaly, Előadások kurzusa "Klasszikus és kvantumszámítás". 8. előadás: A kvantumszámítás definíciója. Példák // Intuit.ru, 2007.03.15

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES

kvantuminformatika

Általános fogalmak

kvantumkommunikáció

kvantumcsatorna
- kvantumhálózat
kvantumkriptográfia
- Kvantumkulcs-elosztás
A kvantumenergia teleportálása
kvantum teleportáció
Ultra-sűrű kvantumkódolás
LOCC
kvantum desztilláció

Kvantum algoritmusok

kvantum szimulátor
Deutsch-Yozhi algoritmus
Bernstein-Wazirani algoritmus
Grover algoritmusa
Kvantum Fourier transzformáció
Shor algoritmusa
Simon problémája
Kvantumfázis-becslési algoritmus
Kvantumszámítási algoritmus
kvantumlágyítás
Algoritmikus hűtés
Kvantumalgoritmus lineáris egyenletrendszer megoldására
Amplitúdó erősítés

Kvantumkomplexitás elmélet

Turing kvantumgép
EQP
BQP
QMA
PostBQP
QIP

Kvantum számítástechnikai modellek

kvantumkör
- kvantumkapu
Egyoldalas kvantumszámítógép
- fürt
Adiabatikus kvantumszámítás
Topológiai kvantumszámítógép

Dekoherencia megelőzés

Kvantumhibák korrekciója
Stabilizációs kódok
Stabilizációs formalizmus
Kvantumkonvolúciós kód

Fizikai megvalósítások

kvantumoptika	Kavitációs kvantumelektrodinamika Kontúrkvantumelektrodinamika Lineáris optikán alapuló kvantumszámítás KLM protokoll Bozonikus mintavétel
szuperhideg atomok	Elnyelt ion kvantumszámítógép Optikai rács
hát alapú	Mágneses magrezonancián alapuló kvantumszámítógép Kane kvantumszámítógépe Veszteséges kvantumszámítógép - DiVincenzo NV központ
Szupravezető kvantumszámítógépek	töltés qubit streaming qubit Fázis qubit Transmon