8
$\begingroup$

This question comes out of an answer Joe Fitzsimons gave to a different question. 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 ?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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"? $\endgroup$ – Robin Kothari Sep 19 '10 at 0:20
  • $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Sep 19 '10 at 0:33
  • $\begingroup$ nice link to the survey. $\endgroup$ – Suresh Venkat Sep 19 '10 at 2:53
  • $\begingroup$ @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. $\endgroup$ – Joshua Grochow Sep 19 '10 at 18:08
  • $\begingroup$ Well, it's then just a case of whether you want classical or quantum messages. Theissue only seems to arise for quantum messages. $\endgroup$ – Joe Fitzsimons Sep 19 '10 at 19:34
10
$\begingroup$

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

$\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.