Wie ist die Beziehung zwischen QMA und AM?

12

Ich habe in SP Jordan, D. Gosset, PJ Loves " -Vollständige Probleme für stoquastische Hamiltonianer und Markov-MatrizenQ.MEIN " gelesen, dass es unwahrscheinlich ist, dass .Q.MEIN⊆EINM

Ich war überrascht über diese Behauptung. Also, was ist die richtige Beziehung zwischen und A M ?Q.MEINEINM

cc.complexity-theory complexity-classes quantum-computing interactive-proofs qma Zelah 02
quelle
@Kaveh, deine Bearbeitung des Titels ist falsch. Das Wort "stoquastisch" wurde richtig geschrieben. Die gleiche Verwirrung geschah in den Kommentaren von cstheory.stackexchange.com/questions/3161/…
Alessandro Cosentino
1
@Alessandro Cosentino: Ich habe es wieder in stoquastic geändert, danke.
Kaveh

Antworten:

22

Es ist keine Beziehung zwischen QMA und AM bekannt, und es ist vernünftig anzunehmen, dass sie unvergleichbar sind.

Wenn sich herausstellen würde, dass QMA in AM enthalten ist, wäre dies ein absolut enormes Ergebnis für die Quantenkomplexität. Natürlich würde dies bedeuten, dass sich BQP in der PH befindet, was selbst riesig wäre, aber es würde darüber hinausgehen - es würde sicherlich wichtige Enthüllungen über die Struktur von Quantenalgorithmen und Quantenzertifikaten erfordern.

Allerdings sind die Beweise dafür nicht sehr überzeugend. Ein Orakel, zu dem QMA nicht in AM enthalten ist, würde helfen, und es scheint, dass ein solches Ergebnis nicht weit entfernt ist - aber wir haben es noch nicht einmal.

Ein Beweis für die umgekehrte Eindämmung, AM in QMA, wäre ebenfalls enorm. Zumindest haben wir hier ein Orakel, zu dem AM nicht in QMA enthalten ist (und in der Tat nicht einmal in PP enthalten ist).

John Watrous
quelle
Ist BQP in QMA enthalten? Ich frage, weil das "klassische" Äquivalent (BPP vs NP) überhaupt nicht bekannt ist. (Dies ist aus meiner Lektüre Ihres Kommentars "es würde bedeuten, dass BQP in PH ist"
Suresh Venkat
5
@ Suresh: Ja, das ist es. BQP und QMA haben die gleiche Beziehung wie P und NP oder BPP und MA. In diesen drei Beispielen ist die erste Klasse trivial in der zweiten, da die zweite Klasse als die erste Klasse mit Zugriff auf ein polynomgroßes "Zertifikat" oder "Proof" definiert ist.
Robin Kothari
Ah richtig. weil BQP und QMA im Gegensatz zu BPP und NP beide ein randomisiertes Element haben (vgl. diese andere Frage zur Beziehung zwischen QMA und NP: cstheory.stackexchange.com/questions/1443/understanding-qma )
Suresh Venkat
12

Nur eine Sache, um Johns Antwort zu ergänzen:

Unter einer plausiblen Derandomisierungshypothese ist AM = NP. In diesem Fall hätten wir sicherlich AM ⊆ QMA.

Scott Aaronson
quelle