TR06-055 Authors: Scott Aaronson, Greg Kuperberg

Publication: 27th April 2006 04:34

Downloads: 2918

Keywords:

This 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.