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 Markowa $QMA$ ", że jest mało prawdopodobne, że . $QMA \subseteq AM$

Byłem zaskoczony tym stwierdzeniem. Więc co jest właściwe relacje między i ? $QMA$ $AM$

— 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,

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