¿Cuál es la relación entre QMA y AM?

12

He leído en SP Jordan, D. Gosset, "Amor del PJ problemas -Complete para hamiltonianas stoquastic y matrices de MarkovQMA " que es poco probable que .QMA⊆AM

Me sorprendió esta afirmación. Entonces, ¿cuál es la relación adecuada entre y A M ?QMAAM

cc.complexity-theory complexity-classes quantum-computing interactive-proofs qma Zelah 02
fuente
@Kaveh, su edición del título es incorrecta. La palabra "estoquástica" se deletreaba de la manera correcta. La misma confusión ocurrió en los comentarios de cstheory.stackexchange.com/questions/3161/…
Alessandro Cosentino
1
@Alessandro Cosentino: lo cambié a estoquástico, gracias.
Kaveh

Respuestas:

22

No se conoce ninguna relación entre QMA y AM, y es razonable conjeturar que son incomparables.

Si se demuestra que QMA está contenido en AM, sería un resultado absolutamente enorme en la complejidad cuántica. Por supuesto, implicaría que BQP está en PH, que en sí mismo sería enorme, pero iría más allá de eso: seguramente requeriría revelaciones importantes sobre la estructura de los algoritmos cuánticos y los certificados cuánticos.

Dicho esto, la evidencia en contra no es muy convincente. Un oráculo en relación con el cual QMA no está contenido en AM ayudaría, y parece que tal resultado puede no estar muy lejos, pero aún no tenemos esto.

Una prueba de la contención inversa, AM en QMA, también sería enorme. Al menos aquí tenemos un oráculo con respecto al cual AM no está contenido en QMA (y de hecho ni siquiera está contenido en PP).

John Watrous
fuente
¿BQP está contenido en QMA? Pregunto porque el equivalente "clásico" (BPP vs NP) no se conoce en absoluto. (Esto es de mi lectura de su comentario "implicaría que BQP está en PH"
Suresh Venkat
55
@Suresh: Sí, lo es. BQP y QMA comparten la misma relación que P y NP, o BPP y MA. En estos tres ejemplos, la primera clase es trivial en la segunda, porque la segunda clase se define como la primera clase con acceso a un "certificado" o "prueba" de tamaño polinómico.
Robin Kothari
Ah bien. porque BQP y QMA tienen un elemento aleatorio, a diferencia de BPP y NP (cf: esta otra pregunta sobre la relación entre QMA y NP: cstheory.stackexchange.com/questions/1443/understanding-qma )
Suresh Venkat
12

Solo una cosa para agregar a la respuesta de John:

Bajo una hipótesis de desrandomización plausible, AM = NP. En ese caso, ciertamente tendríamos AM ⊆ QMA.

Scott Aaronson
fuente