<p>I haven't looked at the paper carefully, but one thing I noticed is that their proof that BQP <span class="math-container">$\subsetneqq$</span> QMA works by their claiming that &quot;bit commitment <span class="math-container">$\not \in$</span> BQP&quot; but &quot;bit commitment <span class="math-container">$\in$</span> QMA&quot;. However, bit commitment is not a decision problem but a protocol, and BQP and QMA are classes of decision problems.</p>
<p>So unless you can define new complexity classes BQP<span class="math-container">$^*$</span> and QMA<span class="math-container">$^*$</span> to encompass protocols, and show that BQP<span class="math-container">$^*$</span> <span class="math-container">$\neq$</span> QMA<span class="math-container">$^*$</span> implies BQP <span class="math-container">$\neq$</span> QMA (which this paper doesn't do), I don't see how you can derive any conclusions about the standard complexity classes BQP and QMA from this paper.</p>
<p>The fact that bit commitment cannot be done by a quantum protocol is a well-known result. Note that I have not checked their proof of bit commitment <span class="math-container">$\in$</span> QMA, in part because I don't understand how they have implicitly expanded QMA to encompass protocols.</p>

CC BY-SA 4.0
2024-01-17T13:29:24.683Z
2024-01-17T13:29:24.683Z
Peter Shor 
<p>BQP vs QMA is a Quantum analogy of P vs NP.</p>
<p>I recently went through the below pre-print on the IACR (International Association for Cryptologic Research) webpage.</p>
<blockquote>
<blockquote>
<p><a href="https://eprint.iacr.org/2023/703.pdf" rel="nofollow noreferrer"><span class="math-container">$BQP\neq QMA$</span> [link] </a></p>
</blockquote>
</blockquote>
<p>I find it rather surprising as this would imply resolving several conjectures such as <span class="math-container">$P\neq PP$</span> and <span class="math-container">$P\neq PSPACE$</span>.</p>
<p>Reason: As <span class="math-container">$P\subseteq BQP$</span> (trivial consequence due to their definition), <span class="math-container">$QMA\subseteq PP$</span> (due to Kitaev-Waltrous, 2005) and <span class="math-container">$QMA \subseteq PSPACE$</span>.</p>
<p>Has someone reviewed the paper? How plausible is their argument?</p>

<cc.complexity-theory><quantum-computing>
Is relation between BQP and QMA resolved?
Manish Kumar
# Is relation between BQP and QMA resolved?

(Asked by: username_0 on 2024-01-16)

BQP vs QMA is a Quantum analogy of P vs NP.

I recently went through the below pre-print on the IACR (International Association for Cryptologic Research) webpage.

> > [$BQP\neq QMA$ [link]](https://eprint.iacr.org/2023/703.pdf)

I find it rather surprising as this would imply resolving several conjectures such as $P\neq PP$ and $P\neq PSPACE$.

Reason: As $P\subseteq BQP$ (trivial consequence due to their definition), $QMA\subseteq PP$ (due to Kitaev-Waltrous, 2005) and $QMA \subseteq PSPACE$.

Has someone reviewed the paper? How plausible is their argument?

**Tags:** cc.complexity-theory, quantum-computing

---

## 1 answers

### Answer by username_1 on 2024-01-17. Score: 18 | Accepted answer

I haven't looked at the paper carefully, but one thing I noticed is that their proof that BQP $\subsetneqq$ QMA works by their claiming that "bit commitment $\not \in$ BQP" but "bit commitment $\in$ QMA". However, bit commitment is not a decision problem but a protocol, and BQP and QMA are classes of decision problems.

So unless you can define new complexity classes BQP$^\*$ and QMA$^\*$ to encompass protocols, and show that BQP$^\*$ $\neq$ QMA$^\*$ implies BQP $\neq$ QMA (which this paper doesn't do), I don't see how you can derive any conclusions about the standard complexity classes BQP and QMA from this paper.

The fact that bit commitment cannot be done by a quantum protocol is a well-known result. Note that I have not checked their proof of bit commitment $\in$ QMA, in part because I don't understand how they have implicitly expanded QMA to encompass protocols.


---

