Třída QMA

V teorii složitosti je QMA (z angličtiny  Quantum Merlin Arthur ) kvantovým analogem NP v klasické teorii složitosti a analogem MA v pravděpodobnostním. Souvisí s BQP stejným způsobem jako NP s P nebo MA s BPP .

Neformálně se jedná o sadu jazyků, pro které existuje polynomiální kvantový důkaz, akceptovaný časově polynomiálním kvantovým algoritmem s vysokou pravděpodobností.

Definice

Jazyk L patří , pokud existuje kvantový algoritmus V polynom v čase a polynom p(x) takový, že: [1] [2]

• , existuje kvantový stav takový, že pravděpodobnost, že V bude trvat více než .
• , pro jakýkoli kvantový stav pravděpodobnost , že V bude trvat méně než .

kde je kvantový stav s p(x) qubity.

Definujme třídu jako třídu rovnou . Ve skutečnosti konstanty nejsou důležité a třída se nezmění, pokud jsou libovolné konstanty větší než . Platí to i pro všechny polynomy a

Související třídy

(nebo [2] ) název se čte jako kvantový klasický Merlin Arthur (nebo Merlin Quantum Arthur), je analogem QMA, ale důkaz (zaslaný Merlinem) by měl být běžný řetězec. Není známo, zda jsou QMA a QCMA stejné.

 je třída jazyků uznávaná kvantovými interaktivními protokoly s polynomiálním časem a k koly, je zobecněním QMA, ve kterém je povoleno přenášet ne jednu zprávu, ale k. Z definice vyplývá, že QMA se shoduje s QIP(1). Je známo, že QIP(2) je obsažen v PSPACE. [3]

 je třída jazyků z QIP(k), kde k může být polynomiální v počtu qubitů. Je známo, že QIP(3) = QIP. [4] Je také známo, že QIP = IP. [5]

 je třída jazyků akceptovaná kvantovými protokoly Merlin Arthur s ideální úplností.

Vztahy s jinými třídami

O QMA je známo, že

První vložení vyplývá z definice NP. Následující dvě zahrnutí jsou správná, protože ověřovatelé jsou stále silnější. Tvrzení, že QMA je obsaženo v PP , dokázali Alexej Kitaev a John Watrus. PP je také obsažen v PSPACE .

Není známo, které z těchto inkluzí jsou přísné.

Poznámky

1. ↑ Dorit Aharonov & Tomer Naveh (2002), Quantum NP - A Survey, arΧiv : quant-ph/0210077v1 [quant-ph]. 
2. ↑ 1 2 John Watrous (2008), Quantum Computational Complexity, arΧiv : 0804.3401v1 [quant-ph]. 
3. ↑ Jain, Rahul; Upadhyay, Sarvagya; Watrous, Johne Kvantové interaktivní důkazy dvou zpráv jsou v PSPACE // FOCS '09: Sborník z 50. výročního sympozia IEEE o základech informatiky v roce 2009 . - IEEE Computer Society , 2009. - S. 534-543. — ISBN 978-0-7695-3850-1 .
4. ↑ Watrous, JohnPSPACE má konstantní kvantové interaktivní důkazové systémy  //  Teoretická informatika : deník. - Essex, Spojené království: Elsevier Science Publishers Ltd., 2003. - Sv. 292 , č.p. 3 . - str. 575-588 . — ISSN 0304-3975 . - doi : 10.1016/S0304-3975(01)00375-9 .
5. ↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, Johne QIP = PSPACE // STOC '10: Sborník příspěvků ze 42. sympozia ACM na téma Theory of computing . - ACM, 2010. - S. 573-582. — ISBN 978-1-4503-0050-6 .

Literatura

• "Algoritmy pro kvantové výpočty: diskrétní logaritmy a faktoring" PW Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Odkazy

• A. Kh. Shen, M. N. Vyaly, Kurz přednášek "Klasické a kvantové výpočty". Přednáška 8: Definice kvantového počítání. Příklady // Intuit.ru, 03/15/2007