QMA klasse

I kompleksitetsteori er QMA (fra engelsk Quantum Merlin Arthur ) kvanteanalogen af NP i klassisk kompleksitetsteori og analogen til MA i sandsynlighedsteori. Det er relateret til BQP på samme måde som NP er relateret til P , eller MA er relateret til BPP .

Uformelt er dette et sæt sprog, for hvilke der er et polynomisk kvantebevis, accepteret af en tidspolynomisk kvantealgoritme med høj sandsynlighed.

Definition

Et sprog L hører til, hvis der eksisterer et kvantealgoritme V polynomium i tid og et polynomium p(x), således at: [1] [2] ${\mbox{QMA}}(c,s)$

$\forall x\in L$ , er der en kvantetilstand sådan, at sandsynligheden for, at V vil tage mere end . $|\psi\rangle$ $(|x\rangle ,|\psi \rangle )$ $c$
$\forall x\notin L$ , for enhver kvantetilstand , sandsynligheden for at V vil tage mindre end . $|\psi\rangle$ $(|x\rangle ,|\psi \rangle )$ $s$

hvor er kvantetilstanden med p(x) qubits. $|\psi\rangle$

Lad os definere en klasse som en klasse lig med . Faktisk er konstanterne ikke vigtige, og klassen vil ikke ændre sig, hvis de vilkårlige konstanter er større end . Også for alle polynomier og , det er sandt ${\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)})

Relaterede klasser

${\mbox{QCMA))$ (eller [2] ) navnet lyder som kvanteklassisk Merlin Arthur (eller Merlin Quantum Arthur), er en analog af QMA, men beviset (sendt af Merlin) skal være en regulær streng. Det vides ikke, om QMA og QCMA er det samme. ${\mbox{MQA))$

${\mbox{QIP}}(k)$ er en klasse af sprog, der genkendes af kvanteinteraktive protokoller med polynomisk tid og k-runder, er en generalisering af QMA, hvor det er tilladt at transmittere ikke én besked, men k. Det følger af definitionen, at QMA falder sammen med QIP(1). QIP(2) vides at være indeholdt i PSPACE. [3]

${\mbox{QIP}}$ er en klasse af sprog fra QIP(k), hvor k har lov til at være polynomium i antallet af qubits. Det er kendt, at QIP(3) = QIP. [4] Det er også kendt, at QIP = IP. [5]

${\mbox{QMA}}_{1}$ er en klasse af sprog, der accepteres af kvanteprotokoller Merlin Arthur med ideel fuldstændighed.

Forhold til andre klasser

Det er kendt om QMA

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

Den første indlejring følger af definitionen af NP. De næste to medtagelser er korrekte, fordi verifikatorerne bliver stærkere. Påstanden om, at QMA er indeholdt i PP , er blevet bevist af Alexei Kitaev og John Watrus. PP er også indeholdt i PSPACE .

Det vides ikke, hvilke af disse inklusioner der er strenge.

Noter

↑ 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 Two-Message Quantum Interactive Proofs are in 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 har konstant runde kvante interaktive bevissystemer // Teoretisk datalogi : journal. - Essex, Storbritannien: Elsevier Science Publishers Ltd., 2003. - Vol. 292 , nr. 3 . - s. 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 42nd ACM symposium on Theory of computing . - ACM, 2010. - S. 573-582. — ISBN 978-1-4503-0050-6 .

Litteratur

"Algorithmer til kvanteberegning: diskrete logaritmer og factoring" PW Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Links

A. Kh. Shen, M. N. Vyaly, Forelæsningsforløb "Klassisk og kvanteberegning". Forelæsning 8: Definition af kvanteberegning. Eksempler // Intuit.ru, 03/15/2007

Kompleksitetsklasser af algoritmer
Betragtes som lys	DLOGTIME AC 0 ACC 0 TC0 [ da L SL RL NL NC SC CC P P-komplet ZPP RP BPP BQP EQP APX
Formodes at være svært	U.P. NP NP komplet co-NP co-NP-komplet AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplet
Anses for vanskelig	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLE

kvanteinformatik

Generelle begreber

kvantekommunikation

kvantekanal
- kvantenetværk
kvantekryptografi
- Kvantenøglefordeling
Teleportering af kvanteenergi
kvanteteleportation
Quantum ultra-tæt kodning
LOCC
kvantedestillation

Kvantealgoritmer

kvantesimulator
Deutsch-Yozhi algoritme
Bernstein-Wazirani algoritme
Grovers algoritme
Quantum Fourier transformation
Shors algoritme
Simons problem
Kvantefase-estimeringsalgoritme
Kvanteberegningsalgoritme
kvanteudglødning
Algoritmisk køling
Kvantealgoritme til løsning af et system af lineære ligninger
Amplitudeforstærkning

Kvantekompleksitetsteori

Turing kvantemaskine
EQP
BQP
QMA
PostBQP
QIP

Kvantecomputermodeller

kvantekredsløb
- kvanteport
Ensidet kvantecomputer
- klynge
Adiabatisk kvanteberegning
Topologisk kvantecomputer

Forebyggelse af dekohærens

Korrektion af kvantefejl
Stabiliseringskoder
Stabiliseringsformalisme
Kvante foldningskode

Fysiske implementeringer

kvanteoptik	Kavitationskvanteelektrodynamik Kontur kvanteelektrodynamik Kvanteberegning baseret på lineær optik KLM protokol Bosonisk prøvetagning
superkolde atomer	Absorberet ion kvantecomputer Optisk gitter
ryg baseret	Kvantecomputer baseret på kernemagnetisk resonans Kanes kvantecomputer Tabskvantecomputer - DiVincenzo NV center
Superledende kvantecomputere	opladningsqubit streaming qubit Fase qubit Transmon