Jaki jest związek między QMA a AM?

12

Czytałem w SP Jordan D. Gosset "PJ Love -Complete problemów stoquastic Hamiltonians i macierzy MarkowaQMA ", że jest mało prawdopodobne, że .QMA⊆AM

Byłem zaskoczony tym stwierdzeniem. Więc co jest właściwe relacje między i A M ?QMAAM

cc.complexity-theory complexity-classes quantum-computing interactive-proofs qma Zelah 02
źródło
@Kaveh, edycja tytułu jest nieprawidłowa. Słowo „stoquastic” zostało napisane we właściwy sposób. To samo zamieszanie wydarzyło się w komentarzach cstheory.stackexchange.com/questions/3161/…
Alessandro Cosentino,
1
@Alessandro Cosentino: Dzięki, zmieniłem to z powrotem na stoquastic.
Kaveh,

Odpowiedzi:

22

Nie wiadomo, by istniał związek między QMA a AM, i można przypuszczać, że są one nieporównywalne.

Gdyby udowodniono, że QMA jest zawarty w AM, byłby to absolutnie ogromny wynik w kwantowej złożoności. Oczywiście oznaczałoby to, że BQP jest w PH, co samo w sobie byłoby ogromne, ale wykraczałoby poza to - z pewnością wymagałoby poważnych rewelacji na temat struktury algorytmów kwantowych i certyfikatów kwantowych.

Powiedziawszy to, dowody przeciwko nie są zbyt przekonujące. Wyrocznia, w stosunku do której QMA nie jest zawarta w AM, pomógłaby i wydaje się, że taki wynik może nie być daleko - ale jeszcze tego nie mamy.

Ogromny byłby również dowód odwrotnego zabezpieczenia, AM w QMA. Przynajmniej tutaj mamy wyrocznię, w stosunku do której AM nie jest zawarty w QMA (i w rzeczywistości nie jest nawet zawarty w PP).

John Watrous
źródło
Czy BQP jest zawarty w QMA? Pytam, ponieważ „klasyczny” odpowiednik (BPP vs NP) wcale nie jest znany. (pochodzi z mojego czytania twojego komentarza „oznaczałoby to, że BQP jest w PH”
Suresh Venkat,
5
@Suresh: Tak jest. BQP i QMA mają takie same relacje jak P i NP lub BPP i MA. W tych trzech przykładach pierwsza klasa jest trywialnie w drugiej, ponieważ druga klasa jest zdefiniowana jako pierwsza klasa z dostępem do wielomianowego „certyfikatu” lub „dowodu”.
Robin Kothari,
Ah, tak. ponieważ oba BQP i QMA mają element losowy, w przeciwieństwie do BPP i NP (por. to inne pytanie dotyczące relacji między QMA i NP: cstheory.stackexchange.com/questions/1443/understanding-qma )
Suresh Venkat
12

Tylko jedna rzecz do dodania do odpowiedzi Johna:

Zgodnie z prawdopodobną hipotezą derandomizacji AM = NP. W takim przypadku z pewnością mielibyśmy AM ⊆ QMA.

Scott Aaronson
źródło