Physics – Quantum Physics
Scientific paper
2006-04-10
Physics
Quantum Physics
20 pages, added an explicit search algorithm
Scientific paper
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 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>. 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.
Aaronson Scott
Kuperberg Greg
No associations
LandOfFree
Quantum Versus Classical Proofs and Advice does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Versus Classical Proofs and Advice, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Versus Classical Proofs and Advice will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-702016