6
$\begingroup$

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]

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?

$\endgroup$
0

1 Answer 1

18
$\begingroup$

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.

$\endgroup$

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.