12
$\begingroup$

I read in S. P. Jordan, D. Gosset, P. J. Love's "$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices" that it is unlikely that $QMA \subseteq AM$.

I was surprised about this assertion. So what is the proper relationship between $QMA$ and $AM$?

Improve this question
$\endgroup$
2
  • $\begingroup$ @Kaveh, your edit of the title is incorrect. The word "stoquastic" was spelled in the right way. The same confusion happened in the comments of cstheory.stackexchange.com/questions/3161/… $\endgroup$
    – Alessandro Cosentino
    Dec 12, 2010 at 5:09
  • 1
    $\begingroup$ @Alessandro Cosentino: I changed it back to stoquastic, thanks. $\endgroup$
    – Kaveh
    Dec 12, 2010 at 6:48

2 Answers 2

Reset to default
22
$\begingroup$

No relationship is known to hold between QMA and AM, and it is reasonable to conjecture they are incomparable.

If QMA were proved to be contained in AM, it would be an absolutely enormous result in quantum complexity. Of course it would imply that BQP is in PH, which itself would be huge, but it would go beyond that -- it would surely require major revelations about the structure of quantum algorithms and quantum certificates.

Having said that, the evidence against is not very convincing. An oracle relative to which QMA is not contained in AM would help, and it seems like such a result may not be far off -- but we don't even have this yet.

A proof of the reverse containment, AM in QMA, would also be huge. At least here we have an oracle relative to which AM is not contained in QMA (and in fact is not even contained in PP).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is BQP contained in QMA ? I ask because the "classical" equivalent (BPP vs NP) is not known at all. (this is from my reading of your comment "it would imply that BQP is in PH" $\endgroup$
    – Suresh Venkat
    Dec 11, 2010 at 17:46
  • 5
    $\begingroup$ @Suresh: Yes, it is. BQP and QMA share the same relationship as P and NP, or BPP and MA. In these three examples, the first class is trivially in the second, because the second class is defined as the first class with access to a polynomial-size "certificate" or "proof." $\endgroup$
    – Robin Kothari
    Dec 11, 2010 at 19:35
  • $\begingroup$ ah right. because BQP and QMA both have a randomized element, unlike BPP and NP (cf: this other question on the relation between QMA and NP: cstheory.stackexchange.com/questions/1443/understanding-qma) $\endgroup$
    – Suresh Venkat
    Dec 11, 2010 at 19:37
12
$\begingroup$

Just one thing to add to John's answer:

Under a plausible derandomization hypothesis, AM = NP. In that case, certainly we would have AM ⊆ QMA.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.