Volume 3 (2007)
Article 7 pp. 129-157
Quantum Versus Classical Proofs and Advice
by Scott Aaronson and Greg Kuperberg
Received: July 27, 2006
Revised: August 23, 2007
Published: September 14, 2007
DOI: 10.4086/toc.2007.v003a007
Keywords: quantum computing, QMA, black-box groups, oracles, 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
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
Ω(√(2n/(m+1)))
queries to find an
n-qubit
marked state
|ψ>, even if given an
m-bit
classical description of
|ψ> together with a quantum black
box that
recognizes
|ψ>. 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.
