Revised: August 23, 2007
Published: September 14, 2007
Abstract: [Plain Text Version]
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether $\mathsf{QMA}=\mathsf{QCMA}$. We prove three results about this question. First, we give a “quantum oracle separation” between $\mathsf{QMA}$ and $\mathsf{QCMA}$. More concretely, we show that any quantum algorithm needs $\Omega\left( \sqrt{\frac{2^{n}}{m+1}}\right) $ queries to find an $n$-qubit “marked state” $\left\vert \psi \right\rangle $, even if given an $m$-bit classical description of $\left\vert \psi\right\rangle $ together with a quantum black box that recognizes $\left\vert \psi\right\rangle $. Second, we give an explicit $\mathsf{QCMA}$ protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a $\mathsf{QMA}$ protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a $\mathsf{QCMA}$ protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$.
Licensed under a Creative Commons License