Clasa QMA

În teoria complexității , QMA (din engleză Quantum Merlin Arthur ) este analogul cuantic al NP în teoria clasică a complexității și analogul MA în cea probabilistică. Este legat de BQP în același mod în care NP este legat de P sau MA este legat de BPP .

Informal, acesta este un set de limbaje pentru care există o demonstrație cuantică polinomială, acceptată de un algoritm cuantic polinomial timp cu mare probabilitate.

Definiție

Un limbaj L aparține dacă există un algoritm cuantic V polinom în timp și un polinom p(x) astfel încât: [1] [2] ${\mbox{QMA}}(c,s)$

$\forall x\in L$ , există o stare cuantică astfel încât probabilitatea ca V să ia mai mult de . $|\psi\rangle$ $(|x\rangle ,|\psi \rangle )$ $c$
$\forall x\notin L$ , pentru orice stare cuantică , probabilitatea ca V să ia mai puțin de . $|\psi\rangle$ $(|x\rangle ,|\psi \rangle )$ $s$

unde este starea cuantică cu p(x) qubiți. $|\psi\rangle$

Să definim o clasă ca o clasă egală cu . De fapt, constantele nu sunt importante și clasa nu se va schimba dacă constantele arbitrare sunt mai mari decât . De asemenea, pentru orice polinoame și , este adevărat ${\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)))\dreapta) ={\mbox{QMA}}(1-2^{-r(n)},2^{-r(n)})

Cursuri înrudite

${\mbox{QCMA}}$ (sau [2] ) numele se citește ca cuantic clasic Merlin Arthur (sau Merlin Quantum Arthur), este un analog al QMA, dar dovada (trimisă de Merlin) ar trebui să fie un șir obișnuit. Nu se știe dacă QMA și QCMA sunt la fel. ${\mbox{MQA}}$

${\mbox{QIP}}(k)$ este o clasă de limbaje recunoscute prin protocoale interactive cuantice cu timp polinomial și k runde, este o generalizare a QMA în care este permis să se transmită nu un mesaj, ci k. Din definiție rezultă că QMA coincide cu QIP(1). Se știe că QIP(2) este conținut în PSPACE. [3]

${\mbox{QIP}}$ este o clasă de limbaje din QIP(k), unde k este permis să fie polinom în numărul de qubiți. Se știe că QIP(3) = QIP. [4] De asemenea, se știe că QIP = IP. [5]

${\mbox{QMA}}_{1}$ este o clasă de limbi acceptate de protocoalele cuantice Merlin Arthur cu o completitudine ideală.

Relații cu alte clase

Se știe despre QMA că

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

Prima încorporare rezultă din definiția NP. Următoarele două incluziuni sunt corecte, deoarece verificatorii sunt din ce în ce mai puternici. Afirmația că QMA este conținută în PP a fost dovedită de Alexei Kitaev și John Watrus. PP este, de asemenea, conținut în PSPACE .

Nu se știe care dintre aceste incluziuni sunt stricte.

Note

↑ Dorit Aharonov & 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; Watrous, John Dovezi cuantice interactive cu două mesaje sunt în PSPACE // FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science . - IEEE Computer Society , 2009. - P. 534-543. — ISBN 978-0-7695-3850-1 .
↑ Watrous, JohnPSPACE are sisteme de dovezi interactive cuantice cu rotund constant // Informatică teoretică : jurnal. - Essex, Marea Britanie: Elsevier Science Publishers Ltd., 2003. - Vol. 292 , nr. 3 . - P. 575-588 . — ISSN 0304-3975 . - doi : 10.1016/S0304-3975(01)00375-9 .
↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John QIP = PSPACE // STOC '10: Proceedings of the 42th ACM simpozion on Theory of computing . - ACM, 2010. - P. 573-582. — ISBN 978-1-4503-0050-6 .

Literatură

„Algoritmi pentru calculul cuantic: logaritmi discreti și factoring” PW Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Link -uri

A. Kh. Shen, M. N. Vyaly, Curs de prelegeri „Clasic and quantum computing”. Cursul 8: Definirea calculului cuantic. Exemple // Intuit.ru, 15.03.2007

Clasele de complexitate ale algoritmilor
Considerată ușoară	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-complet ZPP RP BPP BQP EQP APX
Ar trebui să fie dificil	U.P. NP NP complet co-NP co-NP-complet AM M.A._ QMA PH ⊕P PP #P #P IP PSPACE PSPACE-complete
Considerat dificil	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTAR R PR RE RE-completare Co-RE Co-RE-complete TOATE

informatica cuantica

Concepte generale

comunicații cuantice

canal cuantic
- rețea cuantică
criptografia cuantică
- Distribuția cheii cuantice
Teleportarea energiei cuantice
teleportarea cuantică
Codare cuantică ultradensă
LOCC
distilare cuantică

Algoritmi cuantici

simulator cuantic
Algoritmul Deutsch-Yozhi
Algoritmul Bernstein-Wazirani
Algoritmul lui Grover
Transformată Fourier cuantică
algoritmul lui Shor
problema lui Simon
Algoritmul de estimare a fazei cuantice
Algoritmul de calcul cuantic
recoacere cuantică
Răcire algoritmică
Algoritm cuantic pentru rezolvarea unui sistem de ecuații liniare
Câștig de amplitudine

Teoria complexității cuantice

Modele de calcul cuantic

circuit cuantic
- poarta cuantică
Calculator cuantic unilateral
- cluster
Calcul cuantic adiabatic
Calculator cuantic topologic

Prevenirea decoerenței

Corectarea erorilor cuantice
Codurile de stabilizare
Formalismul de stabilizare
Cod convoluțional cuantic

Implementări fizice

optica cuantică	Electrodinamica cuantică a cavitației Electrodinamica cuantică de contur Calcul cuantic bazat pe optică liniară Protocolul KLM Prelevarea bosonică
atomi superreci	Calculator cuantic cu ioni absorbiți Gratar optic
pe spate	Calculator cuantic bazat pe rezonanța magnetică nucleară Calculatorul cuantic al lui Kane Pierdere computer cuantic - DiVincenzo Centrul NV
Calculatoare cuantice supraconductoare	încărcați qubit streaming qubit qubit de fază Transmon