Quelle est la relation entre l'AMQ et l'AM?

12

Je lis dans SP Jordan, D. Gosset, "PJ amour des problèmes COMPLETES pour Hamiltonians stoquastic et matrices de MarkovQMA " qu'il est peu probable que .QMA⊆AM

J'ai été surpris de cette affirmation. Quelle est donc la bonne relation entre et A M ?QMAAM

cc.complexity-theory complexity-classes quantum-computing interactive-proofs qma Zelah 02
la source
@Kaveh, votre modification du titre est incorrecte. Le mot "stoquastic" était orthographié de la bonne façon. La même confusion s'est produite dans les commentaires de cstheory.stackexchange.com/questions/3161/…
Alessandro Cosentino
1
@Alessandro Cosentino: Je l'ai changé en stoquastic, merci.
Kaveh

Réponses:

22

Aucune relation n'est connue entre l'AMQ et l'AM, et il est raisonnable de supposer qu'ils sont incomparables.

S'il était prouvé que l'AMQ était contenue dans la MA, ce serait un résultat absolument énorme en termes de complexité quantique. Bien sûr, cela impliquerait que BQP est en PH, ce qui serait lui-même énorme, mais cela irait au-delà - cela nécessiterait sûrement des révélations majeures sur la structure des algorithmes quantiques et des certificats quantiques.

Cela dit, les preuves contre ne sont pas très convaincantes. Un oracle par rapport auquel QMA n'est pas contenu dans AM aiderait, et il semble qu'un tel résultat ne soit pas loin - mais nous ne l'avons même pas encore.

Une preuve du confinement inverse, AM dans QMA, serait également énorme. Au moins ici, nous avons un oracle par rapport auquel AM n'est pas contenu dans QMA (et en fait n'est même pas contenu dans PP).

John Watrous
la source
Le BQP est-il contenu dans l'AMQ? Je pose la question car l'équivalent "classique" (BPP vs NP) n'est pas du tout connu. (cela vient de ma lecture de votre commentaire "cela impliquerait que BQP est en PH"
Suresh Venkat
5
@Suresh: Oui, ça l'est. BQP et QMA partagent la même relation que P et NP, ou BPP et MA. Dans ces trois exemples, la première classe est trivialement dans la seconde, parce que la deuxième classe est définie comme la première classe avec accès à un "certificat" ou "preuve" de taille polynomiale.
Robin Kothari
ah oui. parce que BQP et QMA ont tous deux un élément aléatoire, contrairement à BPP et NP (cf: cette autre question sur la relation entre QMA et NP: cstheory.stackexchange.com/questions/1443/understanding-qma )
Suresh Venkat
12

Juste une chose à ajouter à la réponse de John:

Sous une hypothèse de dérandomisation plausible, AM = NP. Dans ce cas, nous aurions certainement AM ⊆ QMA.

Scott Aaronson
la source