Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$

Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara

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…