Id: arxiv/2611.08180 Url: https://arxiv.org/abs/2611.08180 Tags: quant-ph, cs.CC, cs.DS Score: 0 Title: Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$ Domain: quant-ph Source: arxiv Authors: Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-05 Page: https://delphi.science/r/arxiv/2611.08180 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…