Scott Aaronson, Greg Kuperberg

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

Scott Aaronson, DeVon Ingram, William Kretschmer

We show that, in the black-box setting, the behavior of quantum polynomial-time (${BQP}$) can be remarkably decoupled from that of classical complexity classes like ${NP}$. Specifically:

-There exists an oracle relative to which ${NP}^{{BQP}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits ... more >>>