Theory of Computing
-------------------
Title     : Quantum Versus Classical Proofs and Advice
Authors   : Scott Aaronson and Greg Kuperberg
Volume    : 3
Number    : 7
Pages     : 129-157
URL       : https://theoryofcomputing.org/articles/v003a007

Abstract
--------

This paper studies whether quantum proofs are more powerful 
than classical proofs, or in complexity terms, whether 
QMA = QCMA.   We prove three results about this question.  
First, we give a  *quantum oracle separation*   between  
QMA  and  QCMA.  More concretely, we show that any quantum
algorithm needs   Omega(sqrt{2^n/m+1}) queries to find an
n-qubit   *marked state*  |psi>, even if given an  m-bit 
classical description of  |psi>  together with a quantum
black box that recognizes  |psi>.   Second, we give an
explicit 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  QMA  protocol for verifying
non-membership in finite groups.  Under plausible group-theoretic
assumptions, we give a  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
QMA and QCMA.