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.