I'm reading about the complexity classes related to quantum computation, currently I'm studying QMA class. A language is in QMA(c,s) if there exists a polynomial time verifier and polynomial $p(n)$ such that

if $x\in L \implies$ there exists quantum state $\psi$ such that the probability V accepts is greater than $c$

if $x \notin L \implies$ For all quantum states $\psi$ the probability that V accepts is less than $s$.

Usually it is remarked that $c$ and $s$ have the following property $c-s = \frac{1}{poly(n)}$. This last condition is what confuses me. What is the intuition behind imposing this condition on the difference of $c$ and $s$? Not understanding this makes me feel I haven't fully understood QMA class definition.

Something similar happens with the problem called Local Hamiltonian problem. Here two constants are defined such that $a-b = \frac{1}{poly(n)}$. If someone could explain the intuition behind this and if it is related to the previous question that would be great. Thanks!


1 Answer 1


While this question deals with the difference between $\mathsf{BPP}$ and $\mathsf{PP}$, it should still be useful for you to read through. The "short answer" is that the "gap" between $c$ and $s$ allows for standard amplification techniques to be used, which end up showing that $\mathsf{QMA}(c,s) = \mathsf{QMA}(2^{-n},1-2^{-n})$ (provided $c - s$ meets the condition you wrote down).

The "case study" of $\mathsf{BPP}$ vs $\mathsf{PP}$ should be interesting overall for your question, as the only difference between them is the presence / lack of the $c - s \geq 1 / \mathsf{poly}(n)$ condition. It's known that: $$\mathsf{BQP}\subseteq\mathsf{QMA}\subseteq \mathsf{PP}\subseteq\mathsf{PSPACE}$$ But: $$\mathsf{BPP}\subseteq\mathsf{BQP}$$ This is quite a large difference. I'm unsure of what is known about $\mathsf{QMA}(c,s)$ where $c - s$ is negligible (meaning $n^{-\omega(1)}$), where amplification techniques can't be used.

  • $\begingroup$ Thanks! The same argument you have provided here applies for the Local Hamiltonian Problem, right? $\endgroup$
    – Apo
    Dec 23, 2018 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.