Quantum vs Classical Proofs and Subset Verification

Understand

We study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness.

• We develop a general framework that can be used to prove that QCMA machines, with only classical witnesses, cannot verify certain properties of subsets given implicitly via an oracle.
• We use this framework to prove an oracle separation between QCMA and QMA using an "in-place" permutation oracle, making the first progress on this question since Aaronson and Kuperberg in 2007.
• We also use the framework to prove a particularly simple standard oracle separation between QCMA and AM.