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$?

$\endgroup$
  • $\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 '10 at 5:09
  • 1
    $\begingroup$ @Alessandro Cosentino: I changed it back to stoquastic, thanks. $\endgroup$ – Kaveh Dec 12 '10 at 6:48
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).

$\endgroup$
  • $\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 '10 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 '10 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 '10 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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