<p>It's essentially the same thing. QMA has a quantum verifier A which gives you the bounded error bit plus an ability to process quantum states, and M gives you the ability to non-deterministically pick an accepting state if one exists. </p>

<p>A quantum analogue of MA is much more natural than NP, however, since any such analogue of NP would require that the machine be capable of non-deterministically writing a single state from an uncountable number of possible states. QMA only requires finite fidelity, and so you get rid of the infinities. Indeed, QMA is often treated as the quantum analogue of NP (see for example <a href="http://arxiv.org/abs/quant-ph/0210077">quant-ph/0210077</a>).</p>

CC BY-SA 2.5
2010-09-19T00:20:43.407Z
@Joe: Why is there no quantum analog of NP? Can we not define something like "When $x \in L$ there exists a state that is always accepted, and when $x \notin L$ there is no state that is accepted"?
Robin Kothari
CC BY-SA 2.5
2010-09-19T00:33:59.910Z
Yes, you are right, I made a bit of a mistake there. The non-deterministic thing becomes a bit weird though, since you are non-deterministically writing a quantum state and if you require zero error, then this means writing one of an uncountable number of possible states. This would seem to make it hard to properly account for resources.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-19T02:53:02.163Z
nice link to the survey.
Suresh Venkat
CC BY-SA 2.5
2010-09-19T18:08:43.147Z
@Joe, @Robin: What if you restrict your nondeterminism as follows? Given |x0> in the computational basis, a "nondeterministic guess" gate outputs either |x0> or |x1>, nondeterministically (rather than quantumly, of course). I believe this gives you the class QCMA, which might be closer to a quantum analog of NP in the sense Robin is asking about, but I'm not entirely sure I haven't missed something.
Joshua Grochow
CC BY-SA 2.5
2010-09-19T19:34:30.687Z
Well, it's then just a case of whether you want classical or quantum messages. Theissue only seems to arise for quantum messages.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-20T11:39:20.417Z
And in Robin's defence, I had made an incorrect statement in the original answer, which is presumably what triggered his comment, which I fixed once I realized what I had said.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-18T21:17:12.973Z
2010-09-19T01:13:23.820Z
2010-09-19T01:13:23.820Z
Joe Fitzsimons
<p>Most quantum classes that are studied (like QMA, BQP, QIP, and exotic ones like QMIP and QRG) have a classical counterpart and you get the quantum class by thinking quantumly and changing your definition of "efficient computation" to "polynomial time on a quantum computer."</p>

<p>Often there are two steps to be made to reach from a well-known class to a quantum class. The first step adds randomness and error, and the next step adds quantumness. So for NP, the chain of classes is $NP \subseteq MA \subseteq QMA$. In NP the verifier is deterministic, and the certificate or proof is a bitstring. In MA, we modify the verifier to be a BPP machine (give it access to randomness and allow it 1/3 probability of error), while the certificate remains a bitstring. In QMA, we allow the verifier to be quantum and the certificate to be a quantum state. Since a quantum verifier can simulate a probabilistic one, QMA contains MA.</p>

<p>The easy way to get a quantum class out of most natural classical classes is to change one's notion of "efficient computation" from P or BPP to BQP, and change one's notion of information exchange from bits to qubits. So, for example, QIP is the same as IP when the BPP verifier is made BQP and the communication allows qubits instead of bits. </p>

<p>Finally, to get back to QMA:  If you truly believed that BQP captures efficient computation in our universe, then QMA is the set of all problems that have an efficient verification procedure. That is, if you met an almighty prover, it would be able to convince you with high probability of $x \in L$ assuming you can handle qubits and do quantum computation. (And of course when $x \notin L$, there is almost nothing it could say to fool you.)</p>

CC BY-SA 2.5
2010-09-18T21:24:49.863Z
2010-09-18T21:24:49.863Z
Robin Kothari
<p>This question comes out of <a href="https://cstheory.stackexchange.com/questions/1425/intractability-of-np-complete-problems-as-a-principle-of-physics/1442#1442">an answer Joe Fitzsimons gave</a> to <a href="https://cstheory.stackexchange.com/questions/1425/intractability-of-np-complete-problems-as-a-principle-of-physics">a different question</a>. Most natural complexity classes have a one-line "intuitive description" that helps characterize core problems in that class. NP is "efficient verification", #P is about "enumerating solutions", PSPACE is about "game playing", and so on. </p>

<p>I've generally understood MA as BP(NP), where the M step gives you the NP guesser, and the A step is the BP part, and so questions about the relation between MA and NP are really derandomization questions. So my question is: </p>

<blockquote>
  <p>Is there some natural way of
  understanding what QMA captures ?</p>
</blockquote>

<cc.complexity-theory><quantum-computing><big-picture><qma>
Understanding QMA
Suresh Venkat
# Understanding QMA

(Asked by: username_0 on 2010-09-18)

This question comes out of [an answer username_1 gave](https://cstheory.stackexchange.com/questions/1425/intractability-of-np-complete-problems-as-a-principle-of-physics/1442#1442) to [a different question](https://cstheory.stackexchange.com/questions/1425/intractability-of-np-complete-problems-as-a-principle-of-physics). Most natural complexity classes have a one-line "intuitive description" that helps characterize core problems in that class. NP is "efficient verification", #P is about "enumerating solutions", PSPACE is about "game playing", and so on.

I've generally understood MA as BP(NP), where the M step gives you the NP guesser, and the A step is the BP part, and so questions about the relation between MA and NP are really derandomization questions. So my question is:

> Is there some natural way of
> understanding what QMA captures ?

**Tags:** cc.complexity-theory, quantum-computing, big-picture, qma


---

## 2 answers

### Answer by username_1 on 2010-09-18. Score: 8 | Accepted answer

It's essentially the same thing. QMA has a quantum verifier A which gives you the bounded error bit plus an ability to process quantum states, and M gives you the ability to non-deterministically pick an accepting state if one exists.

A quantum analogue of MA is much more natural than NP, however, since any such analogue of NP would require that the machine be capable of non-deterministically writing a single state from an uncountable number of possible states. QMA only requires finite fidelity, and so you get rid of the infinities. Indeed, QMA is often treated as the quantum analogue of NP (see for example [quant-ph/0210077](http://arxiv.org/abs/quant-ph/0210077)).

> **Comments:**
> **username_2**: @Joe: Why is there no quantum analog of NP? Can we not define something like "When $x \in L$ there exists a state that is always accepted, and when $x \notin L$ there is no state that is accepted"?  
> **username_1**: Yes, you are right, I made a bit of a mistake there. The non-deterministic thing becomes a bit weird though, since you are non-deterministically writing a quantum state and if you require zero error, then this means writing one of an uncountable number of possible states. This would seem to make it hard to properly account for resources.  
> **username_0**: nice link to the survey.  
> **username_3**: @Joe, @Robin: What if you restrict your nondeterminism as follows? Given |x0> in the computational basis, a "nondeterministic guess" gate outputs either |x0> or |x1>, nondeterministically (rather than quantumly, of course). I believe this gives you the class QCMA, which might be closer to a quantum analog of NP in the sense Robin is asking about, but I'm not entirely sure I haven't missed something.  
> **username_1**: Well, it's then just a case of whether you want classical or quantum messages. Theissue only seems to arise for quantum messages.  
> **username_1**: And in Robin's defence, I had made an incorrect statement in the original answer, which is presumably what triggered his comment, which I fixed once I realized what I had said.  

---

### Answer by username_2 on 2010-09-18. Score: 12

Most quantum classes that are studied (like QMA, BQP, QIP, and exotic ones like QMIP and QRG) have a classical counterpart and you get the quantum class by thinking quantumly and changing your definition of "efficient computation" to "polynomial time on a quantum computer."

Often there are two steps to be made to reach from a well-known class to a quantum class. The first step adds randomness and error, and the next step adds quantumness. So for NP, the chain of classes is $NP \subseteq MA \subseteq QMA$. In NP the verifier is deterministic, and the certificate or proof is a bitstring. In MA, we modify the verifier to be a BPP machine (give it access to randomness and allow it 1/3 probability of error), while the certificate remains a bitstring. In QMA, we allow the verifier to be quantum and the certificate to be a quantum state. Since a quantum verifier can simulate a probabilistic one, QMA contains MA.

The easy way to get a quantum class out of most natural classical classes is to change one's notion of "efficient computation" from P or BPP to BQP, and change one's notion of information exchange from bits to qubits. So, for example, QIP is the same as IP when the BPP verifier is made BQP and the communication allows qubits instead of bits.

Finally, to get back to QMA: If you truly believed that BQP captures efficient computation in our universe, then QMA is the set of all problems that have an efficient verification procedure. That is, if you met an almighty prover, it would be able to convince you with high probability of $x \in L$ assuming you can handle qubits and do quantum computation. (And of course when $x \notin L$, there is almost nothing it could say to fool you.)


---

