Both definitions try to create a quantum analog for NP. NQP's definition comes from non-deterministic algorithms: it contains languages for which a Quantum Algorithm accepts with non-zero probability the strings in the language and always rejects strings not in the language.

QMA's definition is based on verification algorithms: it contains language for which there is a quantum verifier algorithm that, for yes-instances, there is a quantum proof that makes the verifier accept with probability at least $\frac{2}{3}$ and for no-instances, all proofs make the verifier accept with probability at most $\frac{1}{3}$.

Each of them seems to have a property that makes it accept some language that seem hard for the other. NQP can recognize languages for which the acceptance probability is exponentially small. However, QMA allows some error for no-instances.

The connection between perfect soundness version of QMA (do not allow error for no-instances) and NQP was proved by Kobayashi, Matsumoto and Yamakami. Now, I'm wondering about the relation between QMA and NQP.

  • $\begingroup$ It seems to me like there may be definitional ambiguities for NQP. $\;$ $\endgroup$ – user6973 Jan 17 '14 at 18:20
  • 6
    $\begingroup$ @RickyDemer The question you linked is about EQP, not NQP. According to the zoo, those ambiguities don't hold for NQP, since it turns out to be equal to the classical coC=P. $\endgroup$ – Alessandro Cosentino Jan 18 '14 at 7:53

Your Answer

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

Browse other questions tagged or ask your own question.