Quantum Advantage with Sign-Free Proofs: An Oracle Separation between StoqMA and MA
Abstract
Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain MA ⊆ QCMA ⊆ 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 MA subsetneq StoqMA relative to a classical oracle. The class 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).
Related
- A quantum oracle separation between QMA(2) and QMA
- A Quantum/Classical Example Oracle Separation for Making Things Up
- A Separation Between Types of Quantum Oracle Separations
- A classical oracle separation between QMA and QMA(2)
- Elementary proofs of quantum lower bounds for element distinctness and k-sum
BibTeX
@misc{hamoudi2026quantum,
title = {{Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsfStoqMA$ and $\mathsfMA$}},
author = {Yassine Hamoudi and Yvan Le Borgne and Shrinidhi Teganahally Sridhara},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08180},
eprint = {2611.08180},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08180},
}
RIS
TY - UNPB
TI - Quantum Advantage with Sign-Free Proofs: An Oracle Separation between StoqMA and MA
AU - Yassine Hamoudi
AU - Yvan Le Borgne
AU - Shrinidhi Teganahally Sridhara
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08180
UR - https://arxiv.org/abs/2611.08180
AB - Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain MA ⊆ QCMA ⊆ 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 MA subsetneq StoqMA relative to a classical oracle. The class 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).
ER -