QMA klass

Inom komplexitetsteori är QMA ( från engelska Quantum Merlin Arthur ) kvantanalogen av NP i klassisk komplexitetsteori och analogen till MA i probabilistisk. Det är relaterat till BQP på samma sätt som NP är relaterat till P , eller MA är relaterat till BPP .

Informellt är detta en uppsättning språk för vilka det finns ett polynomkvantbevis, accepterat av en tidspolynomisk kvantalgoritm med hög sannolikhet.

Definition

Ett språk L hör till om det finns ett kvantalgoritm V-polynom i tid och ett polynom p(x) så att: [1] [2] ${\mbox{QMA}}(c,s)$

$\forall x\in L$ , det finns ett kvanttillstånd så att sannolikheten att V tar mer än . $|\psi\rangle$ $(|x\rangle ,|\psi \rangle )$ $c$
$\forall x\notin L$ , för alla kvanttillstånd , sannolikheten att V tar mindre än . $|\psi\rangle$ $(|x\rangle ,|\psi \rangle )$ $s$

var är kvanttillståndet med p(x) kvantbitar. $|\psi\rangle$

Låt oss definiera en klass som en klass lika med . Faktum är att konstanterna inte är viktiga och klassen kommer inte att förändras om de godtyckliga konstanterna är större än . Även för alla polynom och , det är sant ${\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)})

Relaterade klasser

${\mbox{QCMA}}$ (eller [2] ) namnet läser som kvantklassisk Merlin Arthur (eller Merlin Quantum Arthur), är en analog till QMA, men beviset (sänt av Merlin) bör vara en vanlig sträng. Det är inte känt om QMA och QCMA är samma. ${\mbox{MQA))$

${\mbox{QIP}}(k)$ är en klass av språk som känns igen av kvantinteraktiva protokoll med polynomtid och k-rundor, är en generalisering av QMA där det är tillåtet att sända inte ett meddelande, utan k. Av definitionen följer att QMA sammanfaller med QIP(1). QIP(2) är känt för att finnas i PSPACE. [3]

${\mbox{QIP}}$ är en klass av språk från QIP(k), där k tillåts vara polynom i antalet qubits. Det är känt att QIP(3) = QIP. [4] Det är också känt att QIP = IP. [5]

${\mbox{QMA}}_{1}$ är en klass av språk som accepteras av kvantprotokoll Merlin Arthur med idealisk fullständighet.

Relationer med andra klasser

Det är känt om QMA att

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

Den första inbäddningen följer av definitionen av NP. De följande två inkluderingarna är korrekta eftersom verifierarna blir allt starkare. Påståendet att QMA finns i PP har bevisats av Alexei Kitaev och John Watrus. PP finns också i PSPACE .

Det är inte känt vilka av dessa inneslutningar som är strikta.

Anteckningar

↑ 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 runda kvantinteraktiva bevissystem // Teoretisk datavetenskap : 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. - P. 573-582. — ISBN 978-1-4503-0050-6 .

Litteratur

"Algoritmer för kvantberäkning: diskreta logaritmer och factoring" PW Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Länkar

A. Kh. Shen, M. N. Vyaly, Föreläsningskurs "Classical and quantum computing". Föreläsning 8: Definition av kvantberäkning. Exempel // Intuit.ru, 03/15/2007

Komplexitetsklasser av algoritmer
Anses som ljus	DLOGTIME AC 0 ACC 0 TC0 [ sv L SL RL NL NC SC CC P P-komplett ZPP RP BPP BQP EQP APX
Ska vara svårt	U.P. NP NP komplett co-NP co-NP-komplett AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplett
Anses vara svårt	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLA

kvantinformatik

Allmänna begrepp

kvantkommunikation

kvantkanal
- kvantnät
kvantkryptografi
- Kvantnyckeldistribution
Teleportering av kvantenergi
kvantteleportering
Quantum ultra-tät kodning
LOCC
kvantdestillation

Kvantalgoritmer

kvantsimulator
Deutsch-Yozhi algoritm
Bernstein-Wazirani Algoritm
Grovers algoritm
Quantum Fourier Transform
Shors algoritm
Simons problem
Quantum Phase Estimation Algoritm
Quantum Computing Algoritm
kvantglödgning
Algoritmisk kylning
Kvantalgoritm för att lösa ett system av linjära ekvationer
Amplitudförstärkning

Kvantkomplexitetsteori

Turing kvantmaskin
EQP
BQP
QMA
PostBQP
QIP

Quantum Computing Models

kvantkrets
- kvantport
Ensidig kvantdator
- klunga
Adiabatisk kvantberäkning
Topologisk kvantdator

Förebyggande av dekoherens

Korrigering av kvantfel
Stabiliseringskoder
Stabiliseringsformalism
Quantum faltningskod

Fysiska implementeringar

kvantoptik	Kavitationskvantelektrodynamik Kontur kvantelektrodynamik Kvantberäkning baserad på linjär optik KLM-protokoll Bosonisk provtagning
superkalla atomer	Absorberad jon kvantdator Optiskt galler
ryggbaserad _	Kvantdator baserad på kärnmagnetisk resonans Kanes kvantdator Förlust kvantdator - DiVincenzo NV centrum
Supraledande kvantdatorer	ladda qubit strömmande qubit Fas qubit Transmon