En Route to a Standard QMA1 vs. QCMA Oracle Separation
2026-04-29 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors explore how powerful quantum proofs (witnesses) are when they must be perfectly convincing (perfect completeness). They create a special classical oracle that shows a problem can be solved with quantum proofs but not with classical ones under certain limits on the verifier's queries. They also improve earlier results by removing randomness from a known separation between two quantum proof classes and study differences when the acceptance probability gap is very small. Finally, they apply their findings to preparing approximate ground states of quantum systems using specific oracle access.
QMA_1QCMAquantum witnessesoracle separationperfect completenesspermutation-oracleexponentially small gapground-state preparationsparse Hamiltonianfrustration-free
Authors
David Miloschewsky, Supartha Podder, Dorian Rudolph
Abstract
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.