Revised: August 23, 2007

Published: September 14, 2007

**Keywords:**quantum computing, QMA, black-box groups, oracles, hidden subgroup problem

**Categories:**quantum computing, complexity theory, complexity classes, QMA, lower bounds, query complexity, hidden subgroup problem

**ACM Classification:**F.1.2, F.1.3

**AMS Classification:**03F20, 68Q10, 68Q15, 81P68

**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}$.