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

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

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

<p>The connection between perfect soundness version of QMA (do not allow error for no-instances) and NQP was proved by <a href="http://arxiv.org/pdf/quant-ph/0306051.pdf" rel="noreferrer">Kobayashi, Matsumoto and Yamakami</a>. Now, I'm wondering about the relation between QMA and NQP.</p>

CC BY-SA 3.0
2014-01-18T07:53:40.380Z
@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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cocequalsp).
Alessandro Cosentino
<cc.complexity-theory><complexity-classes><quantum-computing>
Are NQP and QMA comparable?
Alex Grilo
# Are NQP and QMA comparable?

(Asked by: username_0 on 2014-01-17)

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](http://arxiv.org/pdf/quant-ph/0306051.pdf). Now, I'm wondering about the relation between QMA and NQP.

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing
> **Comments:**
> **username_1**: @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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cocequalsp).  

---

## 0 answers

