[NN23] A Distribution Testing Oracle Separation between QMA and QCMA

Authors: Anand Natarajan, Chinmay Nirkhe | Venue: CCC 2023 (Quantum 2024) | Source

Abstract

We give a distribution testing oracle separation between QMA and QCMA — the first separation using a classical (rather than quantum unitary) oracle. The separating problem tests connectivity of a random graph encoded by a distributional classical oracle. The key restriction is that the honest prover’s quantum witness depends only on the distribution over oracles, not the specific oracle sample, preventing a classical witness from working. This represents an important step toward a fully standard classical oracle separation between QMA and QCMA.