Pith. sign in

REVIEW 3 major objections 5 minor 18 references

Absence of quantum advantage for approximate spin glass optimization

T0 review · 3 major / 5 minor · reviewed 2026-07-10 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Quantum algorithm offers no edge over classical on spin glass

desk verdict Sels–Morone predicts log(p)/p convergence for QAOA on SK; the bound is heuristic, not rigorous, but the physical mechanism is concrete and the numerics are consistent. read the letter →

arxiv 2607.08708 v1 pith:J6SZMSRE submitted 2026-07-09 quant-ph cond-mat.dis-nn

Dries Sels , Flaviano Morone This is my paper · ORCID
classification quant-phcond-mat.dis-nn PACS 75.50.Lk03.67.Ac05.30.-d
keywords qaoaapproximateconvergenceenergyfinalinitialnoiseoptimal
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The authors apply the Truncated Wigner Approximation — a semiclassical method where the effective spin S controls the level of quantum noise — to simulate QAOA on the Sherrington-Kirkpatrick spin glass, a benchmark optimization problem with a known optimal energy (the Parisi value). They find that the final energy depends non-monotonically on S: at small S, excessive initial noise prevents spins from correlating with the couplings; at large S, the near-zero-noise initial state is an unstable fixed point of the classical dynamics, so tiny fluctuations grow exponentially at a rate set by the Lyapunov exponent, saturating only after the Ehrenfest time t_E ~ log(S). The optimal balance occurs at S* proportional to p (the circuit depth), yielding a residual energy above the Parisi value that scales as log(p)/p. Crucially, the semiclassical simulation slightly outperforms the exact quantum spin-1/2 QAOA across all depths studied (p = 10 to 80). The authors infer from this that the quantum algorithm converges to the Parisi value no faster than log(p)/p, matching the classical rate and implying no quantum advantage. They further show that the logarithmic correction is caused by entropy in the quantum initial state: removing all initial noise and re-optimizing the rotation angles (going fully classical) eliminates it, achieving 1/p convergence.

What carries the argument

The Truncated Wigner Approximation (TWA): a semiclassical method that replaces quantum dynamics with classical rotation of spin vectors, sampling initial conditions from the Wigner distribution of the initial quantum state. The effective spin S controls the width of this distribution (the quantum noise), with variance 1/(2S). The classical map alternates z-rotations (set by instantaneous local fields) with uniform x-rotations, mirroring the QAOA circuit. Two competing effects — entropy at small S and exponential growth of fluctuations at large S via the Lyapunov instability of the initial state — produce a non-monotonic energy landscape with an optimum at S* ~ p.

What would settle it

If exact quantum QAOA at depths well beyond p = 80 were found to converge faster than log(p)/p — for instance, as 1/p — the central claim of no quantum advantage would be directly undermined, since the semiclassical upper bound would no longer be tight.

Watch

Extended reading notes

Core claim

A semiclassical simulation of QAOA on the SK spin glass, where the effective spin S tunes the quantum noise level, slightly outperforms the exact quantum spin-1/2 QAOA at every depth studied. The optimal noise level scales linearly with depth p, and the resulting convergence to the Parisi optimum goes as log(p)/p. Since the semiclassical method is an upper bound on quantum performance, the quantum algorithm can do no better — it converges at the same log(p)/p rate, offering no advantage over classical approaches. The logarithmic penalty traces to quantum entropy in the initial superposition state and can be removed entirely by going noiseless with re-optimized parameters.

Load-bearing premise

The claim that the exact quantum QAOA converges as log(p)/p rests on the observation that the semiclassical simulation slightly outperforms it over the finite range p = 10 to 80, with no theoretical proof that this relationship persists at arbitrarily large depth. The log(p)/p scaling itself is inferred from fitting this limited data rather than derived from first principles.

Editorial extensions

If this is right

  • If the log(p)/p scaling holds asymptotically, achieving a (1-ε) approximation to the SK ground state via QAOA requires depth p = log(1/ε)/ε, giving total complexity O(N² log(1/ε)/ε) — the same order as classical message-passing algorithms up to logarithmic factors.
  • The quantum circuit's apparent O(N) per-layer advantage over the classical O(N²) comes only from parallelizing spin-spin interactions, which classical computation can also parallelize, neutralizing the quantum speedup in wall-clock terms.
  • The logarithmic slowdown is specifically caused by quantum entropy in the initial superposition; a fully classical noiseless protocol with re-optimized parameters achieves 1/p convergence, suggesting the quantum initial state is actively harmful for this problem class.
  • The TWA-as-upper-bound technique may extend to other combinatorial optimization problems where QAOA is applied, potentially revealing whether the absence of quantum advantage is generic to mean-field spin glasses.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The manuscript studies the Quantum Approximate Optimization Algorithm (QAOA) applied to the Sherrington-Kirkpatrick (SK) spin glass using the Truncated Wigner Approximation (TWA). By treating the spin magnitude S as a tunable parameter controlling initial quantum noise, the authors identify two competing effects: at small S, excessive initial noise degrades performance; at large S, exponential growth of fluctuations (governed by the Ehrenfest time) limits the dynamics. The optimal balance occurs at S* ~ p, yielding a residual energy scaling of log(p)/p above the Parisi value. The key claim is that the semiclassical simulation slightly outperforms the exact S=1/2 QAOA for p=10 to 80, from which the authors infer that the exact QAOA also converges as log(p)/p, implying no quantum advantage. They further show that removing initial noise and re-optimizing parameters yields 1/p convergence.

Significance. The question of whether QAOA offers a quantum advantage for spin glass optimization is of considerable interest. The paper provides a concrete, falsifiable prediction for the scaling of QAOA performance on the SK model (log(p)/p) and a physical mechanism (Ehrenfest-time competition) explaining the logarithmic correction. The observation that a noiseless classical variant achieves 1/p convergence is a notable result. However, the central claim regarding the exact quantum QAOA's asymptotic scaling rests on an extrapolation from finite p, which limits the significance of the strongest conclusions.

major comments (3)
  1. The central claim that the exact quantum S=1/2 QAOA converges as log(p)/p rests on the empirical observation that the TWA simulation at optimal S* slightly outperforms the exact QAOA for p=10 to 80 (Fig. 3). The authors state: 'We have no reason to believe this does not persist to asymptotically large p.' This is the load-bearing assumption of the paper's main conclusion, and it is not supported by a rigorous bound or a theoretical argument. The TWA at S*~p is a classical dynamical system with tunable Gaussian noise, not an approximation of the quantum S=1/2 dynamics (the TWA is controlled at large S and the paper itself notes it fails at small S). There is no established inequality relating the performance of the two systems. A crossover at larger p is physically plausible, as the quantum QAOA has fixed fluctuation strength and does not face the same noise-localization tradeoff. The log
  2. The log(p)/p scaling for the semiclassical simulation is derived from the heuristic model in Eq. (7): delta(S,p) ~ a/S + c*log(S)/p. While this fits the data well (Fig. 1), the model itself is an ansatz, not derived from first principles. The two terms correspond to two distinct mechanisms (initial noise and Ehrenfest-time growth), but their additive combination and the specific functional forms are assumed. The claim that 'the QAOA can at best converge to the Parisi value like log(p)/p' (page 4) is presented with more certainty than the heuristic derivation supports. The authors should more clearly distinguish between the empirically observed scaling of the TWA simulation and the inferred scaling of the exact QAOA, and should acknowledge that the latter is a conjecture supported by finite-size evidence rather than a proven bound.
  3. The complexity argument on page 4 states that achieving a 1-epsilon approximation requires depth p = log(1/epsilon)/epsilon, yielding O(N^2 log(1/epsilon)/epsilon) complexity. However, this complexity is derived from the log(p)/p scaling, which is itself the extrapolated result. If the exact QAOA were to eventually outperform the TWA at larger p (as raised in comment 1), the complexity could be better. The complexity claim is only as strong as the scaling claim, and this dependency should be stated explicitly.
minor comments (5)
  1. In Eq. (7), the constant is labeled 'c' in the equation but referred to as 'b' in the text on page 3 ('delta ~ b*log(S)'). The fit function in Fig. 1 caption uses 'b' as well. Please make the notation consistent.
  2. The abstract states 'convergence of the final energy to the Parisi value like log(p)/p' without qualification. Given that this is an extrapolation for the exact QAOA (see major comments), the abstract should reflect the inferential nature of this claim.
  3. On page 2, the text states 'the QAOA parameters {gamma},{beta} are taken directly from Ref. [9].' It would be helpful to briefly state what system size N was used for the TWA simulations (the figure caption of Fig. 3 mentions N=16384, but this should be stated in the main text for clarity).
  4. The reference to 'Ref. [18]' for the noiseless classical results and the re-optimized parameters is cited as a companion paper. Since the 1/p convergence result for the noiseless case is a significant part of the paper's narrative, a brief summary of the method used in Ref. [18] would help the reader assess this claim within the present manuscript.
  5. Fig. 2: The caption mentions 'Different curves show different spin-S, which can be identified from the initial variance.' It would be clearer to explicitly state the range of S values shown or add a legend.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; the log(p)/p scaling is derived from a heuristic model fit to simulation data, and the extrapolation to quantum QAOA is an empirical argument, not a circular definition.

full rationale

The paper's central claim — that QAOA on the SK model converges as log(p)/p — is not circularly derived. The QAOA angles are taken from an external source (Ref. [9], Boulebnane et al.), the Parisi value is an external benchmark (Refs. [10,11]), and the log(p)/p scaling emerges from a heuristic model δ(S,p) ~ a/S + c·log(S)/p (Eq. 7) that is fit to TWA simulation data and then minimized over S. The resulting prediction δ ~ log(p)/p at S* ~ p is a genuine consequence of the model, not a tautology. The extrapolation from semiclassical to quantum QAOA performance ('We have no reason to believe this does not persist to asymptotically large p') is an empirical inference from finite-p data, which is a robustness/correctness concern but not circularity. The self-citation to Ref. [18] (co-authored by the present authors) provides the binarization scheme (Eq. 6), supporting physical analysis of the classical map, and the supplementary 1/p no-noise result — none of which are load-bearing for the main log(p)/p claim in a way that reduces to the paper's own inputs by construction. Score 2 reflects the minor self-citation to Ref. [18] for methodological details and a supplementary result, without which the central argument still stands on its own simulation data and external benchmarks.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new physical entities or forces. The free parameters are fitting constants in the heuristic scaling model. The key axioms are domain assumptions about the validity of TWA and the form of the scaling ansatz.

free parameters (3)
  • a (in Eq. 7)
    Constant in the heuristic fit δ ~ a/S + c·log(S)/p; fitted to numerical data for fixed p.
  • b (in Eq. 7, labeled c in text)
    Constant in the heuristic fit; scales the Lyapunov growth contribution. The text uses both b and c for this role.
  • d (in Fig. 1 fit)
    Offset parameter in the heuristic fitting function a/S + b·log(S) + d used in Figure 1.
assumptions (3)
  • domain assumption The truncated Wigner approximation (TWA) accurately captures the dynamics of QAOA on the SK model, particularly that the semiclassical result upper-bounds the exact quantum result.
    The entire argument that the log(p)/p scaling applies to the exact QAOA rests on the TWA being a faithful upper bound. This is observed for p=10-80 but assumed asymptotically.
  • domain assumption The large-S Gaussian Wigner function (Eq. 3) is sufficient and non-Gaussian corrections are subleading.
    Stated in the text: 'non-Gaussian corrections are subleading in 1/S as compared to the error made by replacing the quantum dynamics with classical dynamics.' This justifies the specific noise model used.
  • ad hoc to paper The heuristic model δ(S,p) ~ a/S + c·log(S)/p captures the scaling of the residual energy.
    Equation (7) is a heuristic combination of the two limiting behaviors, not derived from first principles. It is used to extract the optimal S* and the resulting scaling.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Absence of quantum advantage for approximate spin glass optimization." pith.science (2026). https://pith.science/paper/J6SZMSRE

@misc{pith2026260708708,
  author       = {Pith},
  title        = {Pith review of: Absence of quantum advantage for approximate spin glass optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J6SZMSRE}},
  note         = {Machine review of arXiv:2607.08708}
}
read the original abstract

We perform a semiclassical, large-spin S, analysis of the quantum approximate optimization algorithm (QAOA) on the Sherrington-Kirkpatrick (SK) model, using the truncated Wigner approximation. Fixing the QAOA angles to their previously determined optimal S=1/2 values, we observe a non-monotonic dependence of the final energy on the spin. At small S the semiclassics is dominated by noise, while the large-S limit is constrained by the exponential growth of the initial fluctuations. For a depth-p QAOA one achieves the optimal balance at S of order p, resulting in a convergence of the final energy to the Parisi value like log(p)/p. We find that the semiclassics slightly outperforms the true spin-1/2 QAOA, and thus suggest they both converge to the Parisi value in the same way. Finally, removing all the initial noise, and re-optimizing the parameters to account for that change, results in superior performance with 1/p convergence.

Figures

Figures reproduced from arXiv: 2607.08708 by the authors.

Figure 1
Figure 1. FIG. 1. Final energy reached by the semiclassical QAOA [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Variance of the semiclassical [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Adiabatic quan- tum computation,

    Tameem Albash and Daniel A. Lidar, “Adiabatic quan- tum computation,” Rev. Mod. Phys.90, 015002 (2018)

    work page 2018

  2. [2]

    Exponential algorithmic speedup by a quantum walk,

    Andrew M. Childs, Richard Cleve, Enrico Deotto, Ed- ward Farhi, Sam Gutmann, and Daniel A. Spielman, “Exponential algorithmic speedup by a quantum walk,” inProceedings of the Thirty-Fifth Annual ACM Sympo- sium on Theory of Computing, STOC ’03 (Association for Computing Machinery, New York, NY, USA, 2003) p. 59–68

    work page 2003

  3. [3]

    Optimization by decoded quantum interferometry,

    Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush, “Optimization by decoded quantum interferometry,” Na- ture646, 831–836 (2025)

    work page 2025

  4. [4]

    A Quantum Approximate Optimization Algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “A quantum approximate optimization algorithm,” (2014), arXiv:1411.4028 [quant-ph]

    work page Pith review arXiv 2014

  5. [5]

    Noisy intermediate-scale quantum algorithms,

    Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, “Noisy intermediate-scale quantum algorithms,” Rev. Mod. Phys.94, 015004 (2022)

    work page 2022

  6. [6]

    Performance and limitations of the qaoa at constant lev- els on large sparse hypergraphs and spin glass models,

    Joao Basso, David Gamarnik, Song Mei, and Leo Zhou, “Performance and limitations of the qaoa at constant lev- els on large sparse hypergraphs and spin glass models,” in2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2022) pp. 335–343

    work page 2022

  7. [7]

    The QuantumApproximate OptimizationAl- gorithm and the Sherrington-Kirkpatrick Model at Infi- nite Size,

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou, “The QuantumApproximate OptimizationAl- gorithm and the Sherrington-Kirkpatrick Model at Infi- nite Size,” Quantum6, 759 (2022)

    work page 2022

  8. [8]

    The Quantum Approxi- mate Optimization Algorithm at High Depth for Max- CutonLarge-GirthRegularGraphsandtheSherrington- Kirkpatrick Model,

    Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou, “The Quantum Approxi- mate Optimization Algorithm at High Depth for Max- CutonLarge-GirthRegularGraphsandtheSherrington- Kirkpatrick Model,” in17th Conference on the Theory of Quantum Computation, Communication and Cryptog- raphy (TQC 2022), Leibniz International Proceedings in In...

    work page 2022

Show all 18 references
  1. [9]

    Spin-boson mapping of the quantum approximate optimization algorithm,

    Sami Boulebnane, Abid Khan, Minzhao Liu, Jeffrey Lar- son, Dylan Herman, Ruslan Shaydulin, and Marco Pis- toia, “Spin-boson mapping of the quantum approximate optimization algorithm,” Phys. Rev. Lett.136, 240601 (2026)

    2026

  2. [10]

    Infinite number of order parameters for spin- glasses,

    G. Parisi, “Infinite number of order parameters for spin- glasses,” Phys. Rev. Lett.43, 1754–1756 (1979)

    1979

  3. [11]

    Analysis of the ∞-replicasymmetrybreakingsolutionofthesherrington- kirkpatrick model,

    Andrea Crisanti and Tommaso Rizzo, “Analysis of the ∞-replicasymmetrybreakingsolutionofthesherrington- kirkpatrick model,” Physical Review E65, 046137 (2002)

    2002

  4. [12]

    Optimization of the sherrington- kirkpatrick hamiltonian,

    Andrea Montanari, “Optimization of the sherrington- kirkpatrick hamiltonian,” (2019), arXiv:1812.10897 [math.PR]

    2019 arXiv

  5. [13]

    Algorithmic thresholds in mean field spin glasses,

    Ahmed El Alaoui and Andrea Montanari, “Algorithmic thresholds in mean field spin glasses,” arXiv preprint arXiv:2009.11481 (2020)

    2009 arXiv

  6. [14]

    Truncated wigner dynamics of biclique quan- tum spin glasses,

    Dries Sels, “Truncated wigner dynamics of biclique quan- tum spin glasses,” (2026), arXiv:2606.20187 [cond- mat.dis-nn]

    2026 arXiv

  7. [15]

    Distribution functions in physics: Fundamen- tals,

    M. Hillery, R.F. O’Connell, M.O. Scully, and E.P. Wigner, “Distribution functions in physics: Fundamen- tals,” Physics Reports106, 121–167 (1984)

    1984

  8. [16]

    Phase space representation of quantum dynamics,

    Anatoli Polkovnikov, “Phase space representation of quantum dynamics,” Annals of Physics325, 1790–1852 (2010)

    2010

  9. [17]

    Cluster truncated wigner approximation in strongly interacting systems,

    Jonathan Wurtz, Anatoli Polkovnikov, and Dries Sels, “Cluster truncated wigner approximation in strongly interacting systems,” Annals of Physics395, 341–365 (2018)

    2018

  10. [18]

    Variational iterative rotation algorithm: Combinato- rial optimization with classical kicked tops,

    Flaviano Morone, Andrew D. Kent, and Dries Sels, “Variational iterative rotation algorithm: Combinato- rial optimization with classical kicked tops,” (2026), arXiv:2604.01512 [cond-mat.dis-nn]

    2026

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.