REVIEW
Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$
Quantum Physics · Submitted 5 Nov 2026 · 75 references
Pith's verdict: A genuinely new oracle separation with a clean StoqMA side, but the MA lower bound currently rests on an unproved, likely stronger version of an unpublished lemma.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Relative to a classical oracle, the minimal quantum verifier class StoqMA is strictly more powerful than MA: one Hadamard-basis measurement on top of classical reversible gates already separates them.
The reading
What carries the argument
Two coupled mechanisms carry the argument. The quantum mechanism is the stoquastic Hadamard test: the unitary $U_{G,\pi}$ built from the adjacency-list oracle satisfies the block-encoding identity $\langle u_d|\langle 0|\,U_{G,\pi}\,|u_d\rangle|0\rangle = A_{G,\pi}/d$, where $|u_d\rangle$ is the uniform superposition over the $d$ neighbour slots, so the verifier accepts witness $|\psi\rangle$ with probability $1/2 + \langle\psi|A_{G,\pi}|\psi\rangle/(2d)$; this single identity places every sparse-graph eigenvalue promise problem in StoqMA and is the whole of the quantum side. The classical-side mechanism is the NO-instance construction: the closure operation of Definition 2.7 enlarges a seed set $U$ until every short path between its vertices lies inside it, and the decorated closure graph $F_n(U)$ keeps everything within base distance $\ell_{n,K}+1$ of the closure; the closure graphs are 2-degenerate (every subgraph has a vertex of degree at most 2), and the spectral-norm bound for $c$-degenerate graphs, at most $2\sqrt{cd}$ for maximum degree $d$, converts degeneracy into the eigenvalue gap. Hidden in the decoration are the self-similar trees, whose 0-level leaves are the only places where $F_n(U)$ and $G_n$ differ: a classical explorer starting from the closure must walk down to such a leaf to detect a difference, and Lemma 4.3, quoted from [HBS26], asserts that fewer than $2^{\sqrt{n}}$ queries reach a 0-level leaf with probability at most $2^{-2n\log n}$, which is what makes the $\mathsf{MA}$ lower bound hold.
Extended reading notes
Core claim
Theorem 1.1 states the central result: there exists a classical oracle $O$ such that $\mathsf{StoqMA}^O \neq \mathsf{MA}^O$. The separating language is GPE, defined on graphs with $2^m$ vertices of maximum degree $d \le 2n$, with the promise $\lambda_{\max} \ge n$ (YES) or $\lambda_{\max} \le 4\sqrt{n}$ (NO). The YES instance $G_n$ is built by decorating an $n$-regular base graph of girth at least $100\,n^{5/2}\log n$ (Lemma 3.5) with copies of self-similar trees, then diluting with exponentially many isolated vertices so that classical algorithms must physically walk to see anything; since $G_n$ contains the regular base graph, $\lambda_{\max}(G_n) \ge n$. The NO instance $F_n(U)$, for a seed set $U$ of at most $2^{\sqrt{n}}$ vertices, is obtained by closing $U$ under short paths in the base graph and keeping only what lies within a large base distance of that closure; the result is 2-degenerate (Lemma 3.11), and the spectral-norm bound for degenerate graphs (Lemma 2.4) gives $\lambda_{\max}(F_n(U)) \le 4\sqrt{n}$. On the quantum side a block-encoding identity makes the Hadamard test accept a witness $|\psi\rangle$ with probability $1/2 + \langle\psi|A_{G,\pi}|\psi\rangle/(2d)$, so a stoquastic verifier certifies the YES case with the top eigenvector as witness and rejects every witness on the NO case (Proposition 3.4). The classical lower bound shows that no polynomial-query algorithm, even when given the witness, can distinguish the two families: a presampling lemma (Lemma 5.1) converts any witness into revealed labels of at most $2^{\sqrt{n}}$ vertices, after which the algorithm can only explore locally and must reach a boundary leaf to see a difference, an event whose probability is bounded by Lemma 4.3, quoted from the authors' preceding paper [HBS26] rather than proved here. A diagonalization argument (as in [Zha25]) lifts the query separation to the relativized class separation.
Load-bearing premise
The whole classical lower bound rests on Lemma 4.3, quoted from the authors' own earlier work [HBS26] rather than proved here, that a classical algorithm exploring a randomly labelled self-similar tree from its root with fewer than $2^{\sqrt{n}}$ queries reaches a 0-level leaf with probability at most $2^{-2n\log n}$, together with the similarly quoted local-exploration claim of Lemma 4.2; if either bound fails, or does not survive the adaptive, interleaved queries and independent re-labellings across the many tree copies used in Theorem 4.4, the $\mathsf{MA}$ hardness collapses.
Editorial extensions
If this is right
- Relative to some classical XOR oracle $O$, the inclusion $\mathsf{MA}^O \subsetneq \mathsf{StoqMA}^O$ holds: the diagonalization in Theorem 1.1 yields a fixed oracle, not merely a family of hard instances.
- Because GPE is ground-energy estimation for the stoquastic Hamiltonian $-A_{G,\pi}$, the separation transfers to sparse stoquastic Hamiltonian ground-energy estimation: that StoqMA-complete problem is not in MA relative to the same oracle, despite the sign-problem-free structure that quantum Monte Carlo heuristics exploit.
- The resource doing the separating work is a single Hadamard-basis measurement appended to a classical reversible computation; no quantum Fourier transform or other large coherent computation is used, in contrast with the earlier MA/QCMA/QMA oracle separations.
- The gap-amplification barrier is preserved: the protocol has an inverse-polynomial completeness-soundness gap, and since error reduction for StoqMA is open, the construction cannot be strengthened by the usual amplification; the authors note that the unrelativized collapse $\mathsf{MA} = \mathsf{StoqMA}$ would follow if error reduction held [AGL25].
- The same Hadamard-test verifier is reusable elsewhere in the paper: it gives a one-query stoquastic protocol for Preimage Checking and a $\mathsf{StoqMA}_1$ vs QCMA separation under an in-place permutation oracle (Appendix A), and the authors show that the earlier guided-stoquastic problem of [HBS26] actually lies in NP (Appendix B).
Reading between the lines
- If the tree-exploration lemma is the true bottleneck, the same closure-plus-truncation recipe should separate $\mathsf{MA}^O$ from $\mathsf{StoqMA}^O$ for other spectral promises, such as distinguishing the top eigenvalue from the second eigenvalue or testing the spectral gap of a related operator, because the 2-degeneracy bound is what supplies every eigenvalue gap.
- The construction suggests a concrete finite-size check: simulate classical exploration of the self-similar tree for the smallest admissible parameter $n$ and measure the probability of reaching a 0-level leaf within $2^{\sqrt{n}}$ queries; a value far above $2^{-2n\log n}$ would point to a flaw in the lemma's hypotheses rather than in the diagonalization, while a value near it would corroborate th
- One could try to weaken the quantum side further: the Hadamard-test verifier only needs a block-encoding identity, so a verifier that measures in the computational basis after a single Hadamard gate on one qubit, an even more minimal model, plausibly inherits the same separation and would move the minimal-resource question one step further.
- The paper claims no unrelativized consequence, but the oracle separation does rule out any relativizing proof of $\mathsf{MA} = \mathsf{StoqMA}$; a natural reading is that the open question has shifted from measurement power to the missing error-reduction property of StoqMA.
Original 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).
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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).
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s1 | These separations, however, use substantial coherent quantum computation, often through the quantum Fourier transform. | background 0.51 | 0.04 | 0.02 | asserted 0.94 |
| s2 | We prove that a minimal quantum resource already suffices to outperform every classical verifier. | contribution 0.63 | 0.88 | 0.57 | asserted 1.00 |
| s3 | Namely, we show the separation $$\mathsf{MA} \subsetneq \mathsf{StoqMA}$$ relative to a classical oracle. | result 0.92 | 0.95 | 0.93 | asserted 1.00 |
| s4 | 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. | background 1.00 | 0.05 | 0.03 | asserted 1.00 |
| s5 | Its power is closely tied to the complexity of stoquastic Hamiltonians, a sign-problem-free and seemingly more tractable class of quantum Hamiltonians. | background 0.99 | 0.06 | 0.02 | asserted 0.86 |
| s6 | 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. | contribution 0.76 | 0.79 | 0.04 | asserted 0.99 |
| s7 | This amounts to a ground-energy estimation task for a related stoquastic Hamiltonian. | interpretation 0.74 | 0.71 | 0.03 | asserted 1.00 |
| s8 | 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). | background 0.76 | 0.08 | 0.02 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2611.08180 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.