pith. sign in

arxiv: 2505.07929 · v2 · submitted 2025-05-12 · 🪐 quant-ph

Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm

Sami Boulebnane , Abid Khan , Minzhao Liu , Jeffrey Larson , Dylan Herman , Ruslan Shaydulin , Marco Pistoia This is my paper

Pith reviewed 2026-05-22 15:10 UTC · model grok-4.3

classification 🪐 quant-ph
keywords QAOASherrington-Kirkpatrick modelspin-boson mappingmatrix product statesquantum optimizationthermodynamic limitvariational quantum algorithms
0
0 comments X

The pith

In the infinite-size limit, the depth-p QAOA state for the Sherrington-Kirkpatrick model converges to the state of a spin coupled to p bosonic modes.

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

The paper proves that, when the number of spins goes to infinity, each additional QAOA layer applied to the Sherrington-Kirkpatrick model is exactly reproduced by the time evolution of one spin interacting with an extra bosonic mode. This equivalence turns the original many-spin circuit into a compact spin-boson system whose dynamics can be simulated with matrix product states. The reduced model removes the exponential cost that previously blocked exact analysis beyond depth roughly 20. With the new representation the authors optimize parameters at depths up to 160 and obtain numerical evidence that QAOA reaches within a few percent of the optimal energy.

Core claim

In the thermodynamic limit the depth-p QAOA variational state for the Sherrington-Kirkpatrick Hamiltonian converges to the ground state of a spin-boson Hamiltonian in which one spin couples to p distinct bosonic oscillators. The mapping is obtained by showing that the action of each QAOA layer on the infinite-n SK model is exactly reproduced by the corresponding spin-boson evolution operator. Numerical simulation of the resulting bosonic system then supplies both the optimal QAOA parameters and the achieved energy for depths far beyond the reach of brute-force tensor-network contraction.

What carries the argument

The spin-boson mapping, which replaces the n-spin QAOA circuit with an effective single-spin-plus-p-modes system whose dynamics reproduce the infinite-n limit.

If this is right

  • The effective model can be simulated efficiently with matrix product states, removing the exponential-in-p barrier of exact QAOA evaluation.
  • QAOA is shown to achieve a (1-ε) approximation to the SK ground energy with depth scaling as O(n / ε^1.13) on average.
  • Parameter optimization becomes feasible at p=160, where the algorithm reaches an average error below 2.2 percent.
  • The same mapping applies to any QAOA instance whose cost Hamiltonian has a well-defined thermodynamic limit.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The mapping may extend to finite but large n with controlled corrections that could be computed perturbatively.
  • Similar reductions might apply to other mean-field spin-glass models or to QAOA on dense graphs beyond the SK case.
  • High-depth QAOA performance on real hardware could be benchmarked against the bosonic simulation to separate finite-size effects from circuit noise.

Load-bearing premise

The convergence proof requires that QAOA parameters remain bounded while the number of spins tends to infinity so the thermodynamic limit can be taken inside the circuit.

What would settle it

A direct comparison, for increasing but finite n, between the QAOA energy obtained from the bosonic simulation and the energy obtained from exact or high-fidelity simulation on the original n-spin system; any systematic deviation that grows with p would falsify the convergence claim.

Figures

Figures reproduced from arXiv: 2505.07929 by Abid Khan, Dylan Herman, Jeffrey Larson, Marco Pistoia, Minzhao Liu, Ruslan Shaydulin, Sami Boulebnane.

Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Normalized QAOA energy deviation [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. QAOA on finite-sized instances using parameters from the infinite-size limit. (a) Average approximation ratio ap [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Convergence of the approximate tensor network simulation methods. The top row (a-c) shows convergence for [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Cost to compute approximate QAOA energy [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Parameter values for [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Fitting the data points ( [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
read the original abstract

The Quantum Approximate Optimization Algorithm (QAOA) achieves monotonically improving performance with circuit depth $p$, yet the study of the high-depth regime has been obstructed by the exponential in $p$ cost of existing exact evaluation techniques. In this Letter, we prove that, in the infinite-size limit, the depth-$p$ QAOA state for the Sherrington-Kirkpatrick (SK) model converges to the state of a spin coupled to $p$ bosonic modes. We simulate the spin-boson system using matrix product states and provide numerical evidence that QAOA obtains a $(1-\epsilon)$ approximation to the optimal energy of the SK model with circuit depth $O(n/\epsilon^{1.13})$ in the average case. The modest computational cost of our approach allows us to optimize QAOA parameters and observe that QAOA achieves $\varepsilon\lesssim 2.2\%$ at $p=160$ in the infinite-size limit, extending far beyond $p\leq 20$ accessible to prior exact methods. Our mapping provides a many-body route to study and optimize high-depth QAOA in regimes previously inaccessible to exact evaluation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that, in the thermodynamic limit n→∞ with QAOA parameters held fixed, the depth-p QAOA state on the Sherrington-Kirkpatrick model converges to the ground state of a single spin coupled to p bosonic modes. It then uses matrix-product-state simulations of this effective spin-boson model to optimize QAOA angles at depths up to p=160 and reports numerical evidence that a circuit depth scaling as O(n/ε^{1.13}) suffices to reach a (1-ε) approximation to the optimal energy in the average case, achieving ε≲2.2% at p=160.

Significance. If the mapping and the reported scaling both hold, the work supplies a concrete many-body route to high-depth QAOA that bypasses the exponential cost of exact diagonalization and yields reproducible numerical predictions for approximation ratios at depths far beyond the p≤20 regime previously accessible. The parameter-free character of the infinite-n derivation and the use of standard, bond-dimension-controlled MPS methods are strengths that make the numerical claims falsifiable and extensible.

major comments (2)
  1. [Abstract and Sec. on numerical results] Abstract and the performance claim following the convergence theorem: the asserted scaling p=O(n/ε^{1.13}) for (1-ε) approximation requires a joint limit n→∞, p→∞ with p/n bounded away from zero. The convergence statement is derived for fixed p as n→∞; the manuscript does not quantify the rate of convergence in p or demonstrate that n-dependent corrections remain o(1) when p scales linearly with n. This leaves open whether the reported approximation ratios survive the joint limit.
  2. [MPS simulation section] MPS truncation error for the largest depths: the finite-bond-dimension results at p=160 are stated to be converged, yet the manuscript does not report a systematic extrapolation or error bound on the energy as a function of bond dimension for these largest p values. Because the central numerical claim rests on these energies, an explicit quantification of the truncation error is required.
minor comments (2)
  1. [Mapping derivation] Notation for the bosonic modes and the coupling constants should be introduced once in a dedicated paragraph rather than piecemeal across the derivation.
  2. [Figures] Figure captions for the energy-vs-p plots should explicitly state the bond dimension used and whether the plotted points are variational upper bounds or extrapolated values.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation of our work and for the constructive major comments. We address each point below and will incorporate revisions to clarify the scope of our claims and strengthen the numerical evidence.

read point-by-point responses

  1. Referee: Abstract and the performance claim: the asserted scaling p=O(n/ε^{1.13}) requires a joint limit n→∞, p→∞ with p/n bounded away from zero. The convergence statement is derived for fixed p as n→∞; the manuscript does not quantify the rate of convergence in p or demonstrate that n-dependent corrections remain o(1) when p scales linearly with n. This leaves open whether the reported approximation ratios survive the joint limit.

    Authors: We agree that the convergence theorem applies to fixed p in the thermodynamic limit, and all MPS results are obtained in that limit. The scaling p = O(n/ε^{1.13}) is inferred from a fit to the infinite-n approximation error versus p, under the working assumption that the thermodynamic-limit performance approximates the finite-n case for sufficiently large n. We do not claim a rigorous control of finite-n corrections in the joint limit. In the revision we will modify the abstract and the numerical-results section to state explicitly that the scaling is an extrapolation from the n→∞ data and is expected to hold approximately for large but finite n, without asserting a proof of the joint limit. revision: yes

  2. Referee: MPS truncation error for the largest depths: the finite-bond-dimension results at p=160 are stated to be converged, yet the manuscript does not report a systematic extrapolation or error bound on the energy as a function of bond dimension for these largest p values. An explicit quantification of the truncation error is required.

    Authors: We thank the referee for this observation. Although we monitored convergence by successively increasing bond dimension until the energy changed by less than 10^{-4}, we did not present a systematic extrapolation. In the revised manuscript we will add (in the main text or supplementary material) plots of variational energy versus bond dimension for p=160 together with a polynomial or exponential extrapolation to infinite bond dimension, thereby supplying explicit error estimates on the reported energies. revision: yes

Circularity Check

0 steps flagged

No circularity in the spin-boson mapping derivation

full rationale

The paper's core derivation is a proof that the depth-p QAOA state on the SK model converges to a single spin coupled to p bosonic modes in the n→∞ thermodynamic limit. This limit is taken directly from the structure of the all-to-all Hamiltonian and the product of QAOA unitaries with n-independent angles; it does not reduce to a fitted parameter, a self-definition, or a prior self-citation. The subsequent MPS simulations of the effective spin-boson model use standard tensor-network contraction with bond dimension as the sole convergence control, which is increased until numerical stability. The reported scaling p = O(n/ε^{1.13}) is presented explicitly as numerical evidence obtained by optimizing angles in the mapped model, not as a prediction forced by construction from the same inputs. No load-bearing self-citation, ansatz smuggling, or renaming of known results occurs in the central chain. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The mapping rests on taking the thermodynamic limit of the QAOA evolution operator and on the existence of a well-defined bosonic representation of the resulting infinite-spin interaction; no new particles or forces are postulated beyond the standard spin-boson model.

axioms (2)
  • domain assumption The Sherrington-Kirkpatrick couplings are drawn from a Gaussian distribution with zero mean and variance 1/n.
    Standard definition of the SK model used throughout the derivation of the effective Hamiltonian.
  • domain assumption QAOA parameters remain O(1) as n→∞ for fixed p.
    Required for the bosonic modes to stay finite in number and for the convergence statement to hold.

pith-pipeline@v0.9.0 · 5748 in / 1502 out tokens · 24824 ms · 2026-05-22T15:10:59.112735+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Constraint-Aware Quantum Optimization via Hamming Weight Operators

    quant-ph 2026-01 unverdicted novelty 8.0

    Hamming Weight Operators and an adaptive QAOA variant confine evolution to feasible states by construction, delivering faster convergence and roughly half the gate count versus penalty methods on finance and physics tasks.

  2. Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2

    math.PR 2026-05 unverdicted novelty 7.0

    A polynomial-time algorithm samples the SK model Gibbs measure with o(1) TVD error for β < 1/2 by combining potential Hessian ascent, stochastic localization, Jarzynski equality, and Glauber dynamics.

  3. Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2

    math.PR 2026-05 unverdicted novelty 7.0

    Polynomial-time algorithm samples the Sherrington-Kirkpatrick Gibbs measure at beta < 1/2 with o(1) TVD error by combining potential Hessian ascent, stochastic localization, covariance estimates, and Jarzynski equalit...

  4. Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut

    quant-ph 2026-02 unverdicted novelty 7.0

    QAOA on qudit-encoded integer graph problems outperforms the Frieze-Jerrum SDP for Max-k-Cut at p≤4 in regimes k=3 d≤10 and k=4 d≤40, while a new degree-of-saturation heuristic beats both on GSet but may be overtaken ...

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · cited by 3 Pith papers · 4 internal anchors

  1. [1]

    (386) The first equality follows from writing eΦ(∆) E as a spin-bosons stateproduced by a unitary quantum circuit acting on a qubit and bosonic modes; this is the substance of the spin-bosons construction detailed in appendix IV. As for the second limit, it follows from Φ(∆, D) E = Ψ(∆, D) E + O∥·∥2 D−1/2 (387) (lemma 8), Ψ(∆, D) E 2 = 1 (388) (as a state...

    work page

  2. [2]

    Furthermore, we highlight the folklore notion that the complexity of the AMP algorithm is at least Θ(1 /ϵ2). This is due to the AMP tracking a system of stochastic differential equations (SDEs) utilizing that Euler-Maruyama scheme, which in the worst case , has a convergence rate of O( √ δ) with the number of iterations. In the process of determining the ...

    work page

  3. [3]

    Hence E[|X(δ) ℓ − Xℓδ|2] ≤ (128 + 2C2

    exp 64β4 β8δ. Hence E[|X(δ) ℓ − Xℓδ|2] ≤ (128 + 2C2

    work page

  4. [4]

    Lemma 12 (Extracted From Proof of Proposition 5.3 [2])

    exp 64β4 β8δ. Lemma 12 (Extracted From Proof of Proposition 5.3 [2]) . Suppose that the true Mt satisfies E[M2 t ] = t, ∀t ∈ [0, q∗]. For the SK model | 1 Σ(δ) j − 1| = O β6eO(β4)√ δ Proof. From Equation (402) (Σ(δ) j )2 = E[(u(δj, X(δ) j ))2]. For |(u(t, z))2 − (u(t, y))2| ≤ | u(t, z) + u(t, y)||u(t, z) − u(t, y)| ≤ 8β2|z − y|, ∀t ∈ [0, 1], z, y ∈ R. 73 ...

    work page

  5. [5]

    Optimization of the Sherrington-Kirkpatrick Hamiltonian

    A. Montanari, Optimization of the Sherrington-Kirkpatrick Hamiltonian (2019), arXiv:1812.10897 [math.PR]. 77

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  6. [6]

    A. E. Alaoui, A. Montanari, and M. Sellke, Optimization of mean-field spin glasses (2020), arXiv:2001.00904 [math.PR]

    work page arXiv 2020

  7. [7]

    Basso, E

    J. Basso, E. Farhi, K. Marwaha, B. Villalonga, et al. , in 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 232 (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, Dagstuhl, Germany, 2022) pp. 7:1–7:21

    work page 2022

  8. [8]

    Zhou, gs, t is the autocorrelation function, Private correspondence (2022)

    L. Zhou, gs, t is the autocorrelation function, Private correspondence (2022)

    work page 2022

  9. [9]

    Fishman, S

    M. Fishman, S. R. White, and E. M. Stoudenmire, SciPost Phys. Codebases , 4 (2022)

    work page 2022

  10. [10]

    National energy research scientific computing

    work page

  11. [11]

    Argonne leadership computing facility

    work page

  12. [12]

    Villalonga, Performance of the QAOA on maxcut over large-girth regular graphs (2022)

    B. Villalonga, Performance of the QAOA on maxcut over large-girth regular graphs (2022)

    work page 2022

  13. [13]

    Verstraete and J

    F. Verstraete and J. I. Cirac, Physical Review B 73, 10.1103/physrevb.73.094423 (2006)

    work page doi:10.1103/physrevb.73.094423 2006

  14. [14]

    Larson, M

    J. Larson, M. Menickelly, J. P. O’Neal, and S. M. Wild, Interpolation-based composite derivative-free optimization (2025)

    work page 2025

  15. [15]

    Larson and M

    J. Larson and M. Menickelly, Mathematical Programming Computation 16, 1 (2024)

    work page 2024

  16. [16]

    S. M. Wild, in Advances and Trends in Optimization with Engineering Applications , edited by T. Terlaky, M. F. Anjos, and S. Ahmed (SIAM, 2017) pp. 529–540

    work page 2017

  17. [17]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Physical Review X 10, 10.1103/physrevx.10.021067 (2020)

    work page doi:10.1103/physrevx.10.021067 2020

  18. [18]

    A. Apte, S. H. Sureshbabu, R. Shaydulin, S. Boulebnane, Z. He, D. Herman, J. Sud, and M. Pistoia, arXiv:2504.01694 (2025)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  19. [19]

    T. Hao, Z. He, R. Shaydulin, J. Larson, et al. , End-to-end protocol for high-quality QAOA parameters with few shots (2024), arXiv:2408.00557 [quant-ph]

    work page arXiv 2024

  20. [20]

    Shaydulin, I

    R. Shaydulin, I. Safro, and J. Larson, in Proceedings of the IEEE High Performance Extreme Computing Conference (2019)

    work page 2019

  21. [21]

    Zhou, The QAOA at high girth for MaxCut and the Sherrington-Kirkpatrick model, Talk at the TQC 2022 conference (2022)

    L. Zhou, The QAOA at high girth for MaxCut and the Sherrington-Kirkpatrick model, Talk at the TQC 2022 conference (2022)

    work page 2022

  22. [22]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, Quantum 6, 759 (2022)

    work page 2022

  23. [23]

    A. E. Alaoui and A. Montanari, Algorithmic thresholds in mean field spin glasses (2020), arXiv:2009.11481 [cond-mat.stat- mech]

    work page arXiv 2020

  24. [24]

    Ivkov and T

    M. Ivkov and T. Schramm, Semidefinite programs simulate approximate message passing robustly (2023), arXiv:2311.09017 [cs.DS]

    work page arXiv 2023

  25. [25]

    Parisi formula for the ground state energy in the mixed p-spin model

    A. Auffinger and W.-K. Chen, Parisi formula for the ground state energy in the mixed p-spin model (2016), arXiv:1606.05335 [math.PR]

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  26. [26]

    O. Y. Feng, R. Venkataramanan, C. Rush, R. J. Samworth, et al. , Foundations and Trends in Machine Learning 15, 335 (2022)

    work page 2022

  27. [27]

    A. E. Alaoui, A. Montanari, and M. Sellke, Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree (2023), arXiv:2111.06813 [math.PR]

    work page arXiv 2023

  28. [28]

    H. E. Cheairi and D. Gamarnik, Algorithmic universality, low-degree polynomials, and max-cut in sparse random graphs (2024), arXiv:2412.18014 [cs.DS]

    work page arXiv 2024

  29. [29]

    A. E. Alaoui, A. Montanari, and M. Sellke, arXiv:2203.05093 (2024)

    work page arXiv 2024

  30. [30]

    Jekel, J

    D. Jekel, J. S. Sandhu, and J. Shi, in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (SIAM, 2025) pp. 5307–5387

    work page 2025

  31. [31]

    Nesterov et al

    Y. Nesterov et al. , Lectures on convex optimization , Vol. 137 (Springer, 2018)

    work page 2018

  32. [32]

    Talagrand, Annals of Mathematics , 221 (2006)

    M. Talagrand, Annals of Mathematics , 221 (2006)

    work page 2006

  33. [33]

    Panchenko, The Sherrington-Kirkpatrick Model (Springer Science & Business Media, 2013)

    D. Panchenko, The Sherrington-Kirkpatrick Model (Springer Science & Business Media, 2013)

    work page 2013

  34. [34]

    Auffinger and W.-K

    A. Auffinger and W.-K. Chen, Communications in Mathematical Physics 335, 1429–1444 (2014)

    work page 2014

  35. [35]

    W.-K. Chen, M. Handschy, and G. Lerman, Probability Theory and Related Fields 171, 53–95 (2017)

    work page 2017

  36. [36]

    Gamarnik, Proceedings of the National Academy of Sciences 118, e2108492118 (2021)

    D. Gamarnik, Proceedings of the National Academy of Sciences 118, e2108492118 (2021)

    work page 2021

  37. [37]

    On properties of Parisi measures

    A. Auffinger and W.-K. Chen, arXiv:1303.3573 (2013)

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  38. [38]

    Auffinger, W.-K

    A. Auffinger, W.-K. Chen, and Q. Zeng, The sk model is infinite step replica symmetry breaking at zero temperature (2021), arXiv:1703.06872 [math.PR]

    work page arXiv 2021

  39. [39]

    Jagannath and I

    A. Jagannath and I. Tobasco, Proceedings of the American Mathematical Society 144, 3135–3150 (2015)

    work page 2015