Quantum proofs without signs surpass classical verification power
Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$
Computational ComplexityData Structures and Algorithms
Summary
This paper shows that even a very limited kind of quantum verification, which avoids complex quantum operations, can solve problems that classical methods cannot. The authors focus on a task involving special types of graphs and related quantum models that are simpler to analyze than fully general quantum systems. Their result clarifies how a small quantum advantage appears between classical and quantum proof systems, using an oracle-based theoretical model. This helps understand where quantum verification gains power without relying on heavy quantum computing resources.
What this means in practice
- •For quantum algorithm designers: Identify problems where minimal quantum resources enable verifiers to outperform classical ones, guiding algorithm focus on stoquastic Hamiltonians.
- •For complexity theory researchers: Use the oracle separation as a foundation to explore computational boundaries between classical and restricted quantum proof systems.
A theory result. No direct application yet.
Authors
Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
Abstract
Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum verification and quantum witnesses can each provide additional power over classical proof systems. These separations, however, use substantial coherent quantum computation, often through the quantum Fourier transform. We prove that a minimal quantum resource already suffices to outperform every classical verifier. Namely, we show the separation $$\mathsf{MA} \subsetneq \mathsf{StoqMA}$$ relative to a classical oracle. The class $\mathsf{StoqMA}$, introduced by Bravyi, Bessen, and Terhal (arXiv 2006), restricts the verifier to classical reversible computation, followed by a single Hadamard-basis measurement. Its power is closely tied to the complexity of stoquastic Hamiltonians, a sign-problem-free and seemingly more tractable class of quantum Hamiltonians. Our separating problem is to determine whether a sparse high-girth graph, given via an adjacency-list oracle, has a large or small Perron--Frobenius eigenvalue. This amounts to a ground-energy estimation task for a related stoquastic Hamiltonian. Our construction builds on a line of work on graph exploration problems with exponential quantum speedups, from welded trees (STOC 2003) to recent constructions (STOC 2021, arXiv 2026).