En Route to a Standard QMA1 vs. QCMA Oracle Separation
This work advances the understanding of quantum versus classical witnesses in complexity theory, providing oracle separations that clarify the power of quantum proofs.
The authors construct a classical oracle separating QMA1 from QCMA under bounded-adaptive queries, and derandomize a prior permutation-oracle separation. They also show a separation for QCMA vs QMA with an exponentially small fixed gap, and derive implications for ground-state preparation.
We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in $\mathsf{QMA}_1$ but not in $\mathsf{QCMA}$ when the $\mathsf{QCMA}$ verifier is only allowed polynomially many adaptive rounds and exponentially many parallel queries per round. Additionally, we derandomize the permutation-oracle separation of Fefferman and Kimmel, obtaining an in-place oracle separation between $\mathsf{QMA}_1$ and $\mathsf{QCMA}$. Furthermore, we focus on $\mathsf{QCMA}$ and $\mathsf{QMA}$ with an exponentially small gap, where we show a separation assuming the gap is fixed, but not when it may be arbitrarily small. Finally, we derive consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded-adaptivity frustration-free variant.