<p>While <a href="https://cs.stackexchange.com/questions/7848/concrete-understanding-of-difference-between-pp-and-bpp-definitions">this question</a> deals with the difference between <span class="math-container">$\mathsf{BPP}$</span> and <span class="math-container">$\mathsf{PP}$</span>, it should still be useful for you to read through. The "short answer" is that the "gap" between <span class="math-container">$c$</span> and <span class="math-container">$s$</span> allows for standard amplification techniques to be used, which end up showing that <span class="math-container">$\mathsf{QMA}(c,s) = \mathsf{QMA}(2^{-n},1-2^{-n})$</span> (provided <span class="math-container">$c - s$</span> meets the condition you wrote down).</p>

<p>The "case study" of <a href="https://en.wikipedia.org/wiki/PP_(complexity)#PP_vs_BPP" rel="nofollow noreferrer"><span class="math-container">$\mathsf{BPP}$</span> vs <span class="math-container">$\mathsf{PP}$</span></a> should be interesting overall for your question, as the only difference between them is the presence / lack of the <span class="math-container">$c - s \geq 1 / \mathsf{poly}(n)$</span> condition. It's known that:
<span class="math-container">$$\mathsf{BQP}\subseteq\mathsf{QMA}\subseteq \mathsf{PP}\subseteq\mathsf{PSPACE}$$</span>
But:
<span class="math-container">$$\mathsf{BPP}\subseteq\mathsf{BQP}$$</span>
This is quite a large difference. I'm unsure of what is known about <span class="math-container">$\mathsf{QMA}(c,s)$</span> where <span class="math-container">$c - s$</span> is negligible (meaning <span class="math-container">$n^{-\omega(1)}$</span>), where amplification techniques can't be used.</p>

CC BY-SA 4.0
2018-12-23T10:34:58.100Z
Thanks! The same argument you have provided here applies for the Local Hamiltonian Problem, right?
Apo
CC BY-SA 4.0
2018-12-23T00:59:05.220Z
2018-12-23T00:59:05.220Z
Mark Schultz-Wu
<p>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 <span class="math-container">$p(n)$</span> such that</p>

<p>if <span class="math-container">$x\in L \implies$</span> there exists quantum state <span class="math-container">$\psi$</span> such that the probability V accepts is greater than <span class="math-container">$c$</span> </p>

<p>if <span class="math-container">$x \notin L \implies$</span> For all quantum states <span class="math-container">$\psi$</span> the probability that V accepts is less than <span class="math-container">$s$</span>.</p>

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

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

<quantum-computing>
QMA definition of difference between probabilities intuition
Apo
# QMA definition of difference between probabilities intuition

(Asked by: username_0 on 2018-12-22)

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!

**Tags:** quantum-computing

---

## 1 answers

### Answer by username_1 on 2018-12-23. Score: 1 | Accepted answer

While [this question](https://cs.stackexchange.com/questions/7848/concrete-understanding-of-difference-between-pp-and-bpp-definitions) 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}$](https://en.wikipedia.org/wiki/PP_(complexity)#PP_vs_BPP) 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.

> **Comments:**
> **username_0**: Thanks! The same argument you have provided here applies for the Local Hamiltonian Problem, right?  

---

