Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$
Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
AI 速读 基于摘要
作者报告在经典预言机下证明了 MA 严格包含于 StoqMA，即仅用经典可逆计算加一次 Hadamard 基测量这类极小量子资源即可超越所有经典验证者。
quant-ph · cs.CC · cs.DS
查看原文摘要
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).
Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
原文摘要
We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, that cannot be efficiently sampled by any classical algorithm, even when given the best-possible warm-start distribution. In the quantum setting, this problem can be viewed as preparing the ground state of a stoquastic Hamiltonian given a guiding state as input, and is known to be efficiently solvable on a quantum computer. We further show that even estimating the ground-state energy of that Hamiltonian remains classically hard. Our results suggest that no efficient classical algorithm can solve a broad class of stoquastic ground-state problems. Our graph is constructed from a class of high-degree, high-girth spectral expanders (such as the LPS Ramanujan graphs) to which self-similar trees are attached. This builds on and extends prior work of Gilyén, Hastings, and Vazirani (Quantum 2021, STOC 2021), which ruled out dequantization for a specific stoquastic adiabatic path algorithm. We strengthen their result by ruling out any classical algorithm for guided ground-state preparation or energy estimation, while also providing a derandomized construction.