<p>Just one thing to add to John's answer:</p>

<p>Under a plausible derandomization hypothesis, AM = NP.  In that case, certainly we would have AM &sube; QMA.</p>

CC BY-SA 2.5
2010-12-22T22:17:44.153Z
2010-12-22T22:17:44.153Z
Scott Aaronson
<p>No relationship is known to hold between QMA and AM, and it is reasonable to conjecture they are incomparable.</p>

<p>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.</p>

<p>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.</p>

<p>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).</p>

CC BY-SA 2.5
2010-12-11T17:46:20.653Z
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"
Suresh Venkat
CC BY-SA 2.5
2010-12-11T19:35:14.870Z
@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."
Robin Kothari
CC BY-SA 2.5
2010-12-11T19:37:47.910Z
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: http://cstheory.stackexchange.com/questions/1443/understanding-qma)
Suresh Venkat
CC BY-SA 2.5
2010-12-10T14:28:25.010Z
2010-12-10T14:28:25.010Z
John Watrous
<p>I read in S. P. Jordan, D. Gosset, P. J. Love's "<a href="http://arxiv.org/abs/0905.4755">$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices</a>" that it is unlikely that $QMA \subseteq AM$.</p>

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

CC BY-SA 2.5
2010-12-12T05:09:16.143Z
@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 http://cstheory.stackexchange.com/questions/3161/oracle-relative-to-which-ma-does-not-have-a-complete-problem
Alessandro Cosentino
CC BY-SA 2.5
2010-12-12T06:48:26.270Z
@Alessandro Cosentino: I changed it back to stoquastic, thanks.
Kaveh
<cc.complexity-theory><complexity-classes><quantum-computing><interactive-proofs><qma>
What is the Relationship between QMA and AM?
Zelah 02
# What is the Relationship between QMA and AM?

(Asked by: username_0 on 2010-12-10)

I read in S. P. Jordan, D. Gosset, P. J. Love's "[$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices](http://arxiv.org/abs/0905.4755)" that it is unlikely that $QMA \subseteq AM$.

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

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, interactive-proofs, qma
> **Comments:**
> **username_1**: @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 http://cstheory.stackexchange.com/questions/3161/oracle-relative-to-which-ma-does-not-have-a-complete-problem  
> **username_2**: @Alessandro Cosentino: I changed it back to stoquastic, thanks.  

---

## 2 answers

### Answer by username_4 on 2010-12-10. Score: 23 | Accepted answer

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).

> **Comments:**
> **username_5**: 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"  
> **username_6**: @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."  
> **username_5**: 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: http://cstheory.stackexchange.com/questions/1443/understanding-qma)  

---

### Answer by username_3 on 2010-12-22. Score: 13

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.


---

