ECCC-Report TR06-055https://eccc.weizmann.ac.il/report/2006/055Comments and Revisions published for TR06-055en-usThu, 27 Apr 2006 04:34:40 +0300
Paper TR06-055
| Quantum Versus Classical Proofs and Advice |
Scott Aaronson,
Greg Kuperberg
https://eccc.weizmann.ac.il/report/2006/055This paper studies whether quantum proofs are more powerful than
classical proofs, or in complexity terms, whether QMA=QCMA. We prove
two results about this question. First, we give a "quantum oracle
separation" between QMA and QCMA. More concretely, we show that any
quantum algorithm needs order 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>. We also prove a matching upper bound. Second, we show that, in
the one previously-known case where quantum proofs seemed to help,
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. Both of our
results apply equally to the problem of quantum versus classical
advice -- that is, of whether BQP/qpoly equals BQP/poly. We end with
some conjectures about quantum versus classical oracles, and about the
problem of achieving a classical oracle separation between QMA and
QCMA.
Thu, 27 Apr 2006 04:34:40 +0300https://eccc.weizmann.ac.il/report/2006/055