[AK07] Quantum versus Classical Proofs and Advice

Authors: Scott Aaronson, Greg Kuperberg | Venue: CCC 2007 | Source

Abstract

This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA. We give three results. First, we give a quantum oracle separation between QMA and QCMA. More concretely, we show that there exists a quantum unitary oracle relative to which QMA ≠ QCMA. This gives the first evidence that quantum proofs are more powerful than classical proofs. Second, we show that any quantum oracle separation between QMA and QCMA requires Ω(√N) quantum oracle queries, which means that “black-box” lower bound techniques cannot yield a super-polynomial separation. Third, we show that if a quantum oracle U is drawn at random, then with probability 1, relative to U, QCMA does not contain a particular problem in QMA. We also study the analogous question for advice: is BQP/qpoly strictly more powerful than BQP/poly? We show that there exists a quantum oracle relative to which BQP/qpoly ≠ BQP/poly.