Qual é a relação entre QMA e AM?

12

Eu li em SP Jordan, D. Gosset, "PJ Amor -Complete problemas para Hamiltonians stoquastic e matrizes de MarkovQMA " que é improvável que .QMAAM

Fiquei surpreso com essa afirmação. Então, qual é a relação adequada entre e A M ?QMAAM

Zelah 02
fonte
@ Kaveh, sua edição do título está incorreta. A palavra "estocástico" foi escrita da maneira correta. A mesma confusão aconteceu nos comentários de cstheory.stackexchange.com/questions/3161/…
Alessandro Cosentino
1
@ Alessandro Cosentino: mudei de volta para estocástico, obrigado.
Kaveh

Respostas:

22

Sabe-se que não há relação entre QMA e AM, e é razoável supor que eles são incomparáveis.

Se o QMA for provado estar contido no AM, seria um resultado absolutamente enorme na complexidade quântica. É claro que isso implicaria que o BQP está no PH, o que seria enorme, mas iria além disso - certamente exigiria grandes revelações sobre a estrutura dos algoritmos e certificados quânticos.

Dito isto, a evidência contra não é muito convincente. Um oráculo em relação ao qual o QMA não está contido no AM ajudaria, e parece que esse resultado pode não estar muito distante - mas ainda nem o temos.

Uma prova da contenção reversa, AM no QMA, também seria enorme. Pelo menos aqui temos um oráculo em relação ao qual AM não está contido no QMA (e, de fato, nem mesmo está contido no PP).

John Watrous
fonte
O BQP está contido no QMA? Eu pergunto porque o equivalente "clássico" (BPP vs NP) não é conhecido. (isto é de minha leitura do seu comentário "isso implicaria que BQP está em PH"
Suresh Venkat
5
@ Suresh: Sim, é. BQP e QMA compartilham o mesmo relacionamento que P e NP, ou BPP e MA. Nestes três exemplos, a primeira classe é trivialmente na segunda, porque a segunda classe é definida como a primeira classe com acesso a um "certificado" ou "prova" de tamanho polinomial.
Robin Kothari
Ah, certo. porque BQP e QMA têm um elemento aleatório, diferente de BPP e NP (cf: esta outra questão sobre a relação entre QMA e NP: cstheory.stackexchange.com/questions/1443/understanding-qma )
Suresh Venkat
12

Apenas uma coisa a acrescentar à resposta de John:

Sob uma hipótese plausível de derandomização, AM = NP. Nesse caso, certamente teríamos AM ⊆ QMA.

Scott Aaronson
fonte