QAOA reaches the spin-glass optimum—when system size goes first

← All digests

Family 281 · Mathematical physics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-25

1. The question

The Quantum Approximate Optimization Algorithm, or QAOA, alternates two simple types of quantum evolution. One encodes an objective function; the other mixes possible answers. Increasing the number of alternating layers enlarges the family of states it can prepare.

For a fixed finite instance, sufficiently many layers can approach the optimum. A harder question asks whether, for each desired accuracy, one finite depth can work for arbitrarily large random instances. The depth must be chosen before sending the system size to infinity.

Family 281 reports this property for the Gaussian zero-field Sherrington–Kirkpatrick spin glass. Its companion studies the full support of the zero-temperature Parisi order parameter, supplying one route to the classical near-optimal calculation that the QAOA construction compiles. The family concerns asymptotic attainability; it does not provide an efficient angle-selection algorithm or a quantitative depth bound.

2. Background and essential definitions

A random optimization landscape

For $n$ signs $\sigma_i\in\{-1,1\}$, define

$$h_{n,J}(\sigma)=\frac1{\sqrt n}\sum_{i<j}J_{ij}\sigma_i\sigma_j,$$

where the $J_{ij}$ are independent standard real Gaussian variables. Some pairs prefer equal signs and others opposite signs, creating frustration. The normalization makes the optimal energy of order $n$.

The positive optimum per spin is

$$P_* =\lim_{n\to\infty}\frac1n\mathbb E\max_\sigma h_{n,J}(\sigma).$$

The manuscript maximizes this sign convention; equivalently it studies the ground energy of its negative. The expectation averages over the random couplings.

For quantum spins, replace $\sigma_i$ by the Pauli matrix $Z_i$, giving the cost operator $C_{n,J}$, and use the mixer $B_n=\sum_iX_i$. The initial state $|+\rangle^{\otimes n}$ is the uniform superposition of all sign configurations. A depth-$p$ QAOA state is

$$|\psi\rangle=e^{-i\beta_pB_n}e^{-i\gamma_pC_{n,J}}\cdots e^{-i\beta_1B_n}e^{-i\gamma_1C_{n,J}}|+\rangle^{\otimes n}.$$

Measuring in the computational basis samples a classical configuration. Its expected objective equals $\langle\psi,C_{n,J}\psi\rangle$.

Overlaps and the Parisi description

The overlap of two configurations is $R_{12}=n^{-1}\sum_i\sigma_i^1\sigma_i^2$. It measures their similarity. The Parisi variational description uses an order parameter organizing overlap scales.

At zero temperature in covariance convention $\xi(t)=t^2/2$, the admissible order parameter is a nonnegative, nondecreasing, right-continuous function $\gamma:[0,1)\to[0,\infty)$ with finite integral. This $\gamma$ is a function, distinct from the QAOA angle vector of the same conventional name.

Its Stieltjes measure satisfies $\mu_\gamma([0,t])=\gamma(t)$, including a possible atom $\gamma(0)$ at zero. It need not be a probability measure or have finite total mass. Full relative support means every nonempty open overlap interval below one carries positive measure.

The corresponding value function solves

$$\partial_t\Phi=-\frac12\bigl(\partial_{xx}\Phi+\gamma(t)(\partial_x\Phi)^2\bigr), \qquad \Phi(1,x)=|x|,$$

and the Parisi functional is $\mathcal P(\gamma)=\Phi(0,0)-\tfrac12\int_0^1t\gamma(t)\,dt$. Its minimum equals $P_*$.

3. Development history and previous partial results

Sherrington and Kirkpatrick introduced the model, and Parisi proposed its hierarchical order parameter. Guerra established the interpolation bound and Talagrand the positive-temperature formula. Auffinger and Chen developed the zero-temperature formula and its attainment. Determining the minimizer’s support is a separate problem from proving the formula.

Auffinger, Chen and Zeng showed infinitely many zero-temperature support points. That does not exclude an interior interval containing none. More recently, Lopatto established full interval support in the low-temperature zero-field phase, and Hong-Bin Chen established zero-temperature full support and smooth absolute continuity. M2 explicitly credits this earlier full-support conclusion. Its contribution is a different coercive-identity argument, strict positivity of the density away from zero, and scalar consequences used in optimization.

Farhi, Goldstone and Gutmann introduced QAOA. Later fixed-depth analysis of its SK performance established limiting formulas and concentration at fixed parameters. Basso, Farhi, Marwaha, Villalonga and Zhou related the limit to large-degree trees and conjectured eventual attainment of the Parisi value. Spin–boson calculations and semiclassical studies supplied further numerical and heuristic evidence.

Classical optimization supplies another key predecessor. Montanari’s Parisi-diffusion approach and the broader work of El Alaoui, Montanari and Sellke give near-optimal algorithms under support hypotheses. M1 compiles a finite classical calculation into standard QAOA controls. Its primary route uses M2; an independent positive-temperature route uses Lopatto’s support theorem and existing finite-iteration analysis.

4. What the new manuscripts claim

Eventual QAOA optimality

For fixed deterministic angles, define

$$v_p(\boldsymbol\gamma,\boldsymbol\beta) =\lim_{n\to\infty}\frac1n\mathbb E\langle\psi,C_{n,J}\psi\rangle, \qquad Q_p=\sup_{\boldsymbol\gamma,\boldsymbol\beta}v_p.$$

M1 claims $\lim_{p\to\infty}Q_p=P_*$. Precisely, for every $\varepsilon>0$, there exist a finite $p$ and deterministic real angles, independent of both $n$ and $J$, with limiting expected energy at least $P_*-\varepsilon$.

The chosen word may contain inverse gates, zero angles and very large angles. It uses only the standard cost and transverse-field mixer in its final form. The theorem gives no quantitative finite-size rate, required-depth bound or efficient angle-selection procedure. It is stated in expected energy.

Full zero-temperature support

M2 claims that every admissible minimizer satisfies

$$\operatorname{supp}\mu_\gamma=[0,1).$$

It obtains smoothness on $[0,1)$, $\gamma(0)=0$ and $\gamma'(t)>0$ for $0<t<1$. Thus the measure has a smooth density strictly positive away from zero. These statements concern the relative interval below one, not a claim of finite total mass or smooth extension through the endpoint one.

For the controlled diffusion $dX_t=\gamma(t)\Phi_x(t,X_t)\,dt+dB_t$, with $X_0=0$ and standard Brownian motion $B_t$, M2 also obtains consistency identities $\mathbb E\Phi_x(t,X_t)^2=t$ and $\mathbb E\Phi_{xx}(t,X_t)^2=1$.

Applying the existing El Alaoui–Montanari–Sellke theorem, M2 derives a randomized classical algorithm using at most $C(\varepsilon)n^2$ real-arithmetic operations and returning energy within $\varepsilon n$ of the optimum with probability tending to one. Probability includes disorder and algorithmic randomness. This operation model should not be silently replaced by a bit-complexity claim.

A MaxCut consequence

M1 transfers the QAOA construction to large-degree regular graphs. For every $\eta>0$, it chooses a finite depth and normalized angles independent of degree and graph. For sufficiently large $D$, every simple unweighted $(D+1)$-regular graph of girth greater than $2p+1$ has expected cut fraction at least

$$\frac12+\frac{P_*-\eta}{\sqrt D},$$

using ordinary MaxCut cost angles scaled as $2\boldsymbol\gamma/\sqrt D$. Girth is the length of the shortest cycle. A random-regular-graph corollary makes the difference from the optimal cut negligible at the $1/\sqrt D$ scale, taking graph size to infinity first at fixed degree and then degree to infinity. The probability there is over the graph; the cut fraction already averages quantum measurement.

5. Why the advance matters

Importance: 4/5, provisional. The family claims a central asymptotic attainability result for QAOA on a canonical spin glass, together with a structural analysis of the order parameter feeding the construction.

The limit order makes the result stronger than fixed-instance convergence as depth grows. One finite circuit word is chosen for an accuracy target and then used throughout the thermodynamic limit. At the same time, absent depth and angle-selection bounds prevent this from being an efficient practical optimization guarantee.

The classical near-optimal calculation also makes clear that this is not a demonstrated quantum speedup over classical algorithms. Its significance is that standard QAOA controls can asymptotically realize the required performance. The rating measures that claim if correct, while crediting the earlier support and optimization results.

6. The main idea

Exclude gaps in overlap support

M2 studies $q(t)=\mathbb E\Phi_x(t,X_t)^2$. Variational optimality supplies contact conditions at support points. On a hypothetical interval where the order parameter is a positive constant, an integrated rational identity gives strict convexity of $q'$.

The endpoint contact conditions force $q'$ to have average one across the interval, while strict convexity and endpoint bounds force it below one inside. This contradiction excludes an interior gap. Initial and terminal gaps require separate arguments. Once consistency holds at every time, derivative-moment identities yield smoothness and the stated positive density.

Compile a classical near-optimal formula

M1 first represents a bounded near-optimal calculation as a finite function of Gaussian variables on a rooted-tree Hilbert space. Normalized sums of child calculations supply new Gaussian coordinates. Smooth approximations and exclusions of selected vertex types prevent compiled operations from feeding back into their own controls.

Temporary longitudinal seed fields make the desired functions implementable through cost and mixer commutators. Small reserved sets of helper spins realize neighbor sums. The construction controls their contribution to energy rather than treating them as free extra resources.

Remove temporary controls before taking the limit

A further echo construction removes the longitudinal seed controls from the already selected finite circuit. Selective rotations and a large displacement produce the required effective field, while a separate energy calculation preserves the target value.

Only after all approximations and control removal does the argument choose one finite ordinary cost–mixer word and invoke the fixed-word tree-to-SK identity. This order prevents an auxiliary control or a system-size-dependent circuit from remaining hidden in the final QAOA claim.

7. Scope, limitations, and open questions

Both manuscripts concern the pure Gaussian zero-field SK model with the stated normalization. Nonzero external fields and general mixed-spin covariances are not included automatically.

M1 supplies existential depth and angles for limiting expected energy. It gives no explicit accuracy-depth law, efficient search procedure, finite-size guarantee or joint limit in which depth grows with $n$. Large angles may also carry implementation costs not measured by the layer count.

M2’s support result is not the first full-support statement; its distinct argument and scalar consequences should be assessed in that historical context. Quantitative QAOA bounds and extensions to other disordered optimization models remain separate questions beyond this family.

8. Sources and further reading

The Basso and collaborators paper states the QAOA conjecture and tree relation. Chen’s paper gives the earlier zero-temperature full-support result, and El Alaoui–Montanari–Sellke provide the optimization theorem. M1 and M2 below specify the new constructions and their dependencies, reported as stated.

Source manuscripts

• M1. OpenAI, QAOA attains the SK ground-state energy in the thermodynamic-first limit (September 25, 2026).
• M2. OpenAI, Full support of the zero-temperature Sherrington-Kirkpatrick order parameter (September 27, 2026).

Sources consulted on 25 October 2026 at repository revision 1581d4c. Download the manuscript citations.