QAOA and the SK optimum: Parisi support and the order of limits

Source and verification

This article explains family 281 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Spin-glass energy and quantum optimization

Family 281 contains two linked manuscripts. The first argues that the quantum approximate optimization algorithm, QAOA, approaches the Sherrington–Kirkpatrick optimum when system size tends to infinity before circuit depth. The companion proves full support of a zero-temperature Parisi order parameter and supplies the scalar diffusion identities used in the quantum construction. (OpenAI, 2026) (OpenAI, 2026a)

The prerequisites are Gaussian probability, stochastic calculus, variational principles, and quantum circuits. The analytic companion uses a nonlinear heat equation; the quantum argument also uses a Hilbert-space limit of computations on large-degree trees. We introduce these objects before describing their roles.

For independent standard Gaussian couplings $J_{ij}$ and spins ${\sigma }_i\in \{-1,1\}$, set

$$h_{n,J}(\sigma )=\frac{1}{\sqrt{n}}\sum _{i<j}{J}_{ij}{\sigma }_i{\sigma }_j.$$

The positive ground-state value is $P_{\ast }={\lim }_{n\to \infty }{n}^{-1}\mathbb{E}{\max }_{\sigma }{h}_{n,J}(\sigma )$. Thus we maximize the displayed Hamiltonian; changing its sign gives the usual minimum-energy convention.

Replace each spin by its Pauli $Z$ matrix to form the cost operator $C_{n,J}$, and let $B_n={\sum }_i{X}_i$ be the transverse-field mixer. A depth-$p$ QAOA state starts from $|+{⟩}^{\otimes n}$ and alternates cost gates $e^{-i{\gamma }_j{C}_{n,J}}$ and mixer gates $e^{-i{\beta }_j{B}_n}$. The vectors of angles are deterministic.

For fixed depth and angles, define

$$\begin{array}{c}{v}_p(\mathbf{\gamma },\mathbf{\beta })=\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}⟨C_{n,J}{⟩}_{\mathrm{QAOA}},\\ Q_p=\underset{\mathbf{\gamma },\mathbf{\beta }}{\sup }{v}_p.\end{array}$$

Manuscript's thermodynamic-first conclusion

For the pure Gaussian zero-field SK model, ${\lim }_{p\to \infty }{Q}_p=P_{\ast }$. Equivalently, for each $\epsilon >0$, some finite depth and deterministic angles, independent of system size and disorder, have limiting expected energy at least $P_{\ast }-\epsilon$. (OpenAI, 2026b)

Measurement bounds $Q_p\le P_{\ast }$, and adding a zero-angle layer gives $Q_{p+1}\ge Q_p$. The work lies in constructing a single finite word at each accuracy. The theorem supplies no quantitative depth bound, finite-size error estimate, or efficient procedure for finding its angles. Allowing depth to grow for each fixed finite instance would be a different quantifier order.

🏷️ The Parisi variational problem

An admissible order parameter is a nonnegative, nondecreasing, right-continuous function $\gamma :[0,1)\to [0,\infty )$ with ${\int }_0^1\gamma <\infty$. This scalar function is distinct from the QAOA cost-angle vector. Its locally finite Stieltjes measure is defined by ${\mu }_{\gamma }([0,t])=\gamma (t)$, including an atom $\gamma (0)$ at zero. It need not have total mass one, or even finite total mass.

The value function solves the backward Parisi equation

$$\begin{array}{c}{\Phi }_t=-\frac{1}{2}\left({\Phi }_{xx}+\gamma (t){\Phi }_x^2\right),\\ \Phi (1,x)=|x|,\\ \mathcal{P}(\gamma )={\Phi }_{\gamma }(0,0)-\frac{1}{2}{\int }_0^{1}t\gamma (t)dt.\end{array}$$

For integrable coefficients, the solution is defined through stochastic control and approximation. Operationally, one chooses an adapted drift control $a_s\in [-1,1]$, maximizes the expected terminal absolute position, and pays $\frac{1}{2}\int \gamma (s)a_s^{2}ds$. The optimal drift is $\gamma {\Phi }_x$.

The established Parisi formula and minimizer existence theorem, imported by the manuscripts, identify $P_{\ast }={\min }_{\gamma }\mathcal{P}(\gamma )$. The covariance convention is $\xi (t)=t^2/2$. The unordered-pair Hamiltonian has covariance $n{R}_{12}^2/2-1/2$, where $R_{12}=n^{-1}{\sum }_i{\sigma }_i^1{\sigma }_i^2$. Adding one configuration-independent centered Gaussian of variance $1/2$ corrects that constant without changing the expected maximum.

Write $u={\Phi }_x$, $a={\Phi }_{xx}$, and consider the diffusion

$$\begin{array}{c}d{X}_t=\gamma (t)u(t,X_t)dt+d{B}_t,\\ X_0=0.\end{array}$$

Here $B_t$ is Brownian motion, not the quantum mixer. On every time interval ending before one, the spatial derivatives are controlled; $|u|\le 1$ and the drift has an integrable deterministic bound.

The companion’s main statement is that every admissible minimizer has full relative support $\mathrm{supp}{\mu }_{\gamma }=[0,1)$. In particular, $\gamma (b)>\gamma (a)$ whenever $0\le a<b<1$. It also gives the self-consistency identities $\mathbb{E}u(t,X_t{)}^2=t$ and $\mathbb{E}a(t,X_t{)}^2=1$. Pure SK covariance and zero external field are essential hypotheses. (OpenAI, 2026a)

🏷️ Contact conditions and the exclusion of gaps

Let $q(t)=\mathbb{E}u(t,X_t{)}^2$. The gradient along the diffusion is a martingale, and Itô’s formula gives $q^{\prime }(t)=\mathbb{E}a(t,X_t{)}^2$.

At a minimizer, the first variation in an admissible integrable direction $\eta$ is

$$D\mathcal{P}(\gamma )[\eta ]=\frac{1}{2}{\int }_0^1\eta (t)(q(t)-t)dt.$$

Adding a Stieltjes atom at $s$ corresponds to $\eta =1_{[s,1)}$. Removing a fraction of the measure on any compact set is also an admissible direction. These two variations show that

$$G(s)={\int }_s^1(q(t)-t)dt$$

is nonnegative everywhere and vanishes on the relative support. Removal must allow arbitrary measure, not just atoms, because no initial discreteness assumption is available. At an interior support point, $G^{\prime }=0$ and $G^{\prime \prime }\ge 0$, hence $q(s)=s$ and $q^{\prime }(s)\le 1$.

Suppose $(a,b)$ were a support gap with both endpoints in the support. The coefficient $\gamma$ would be constant there. The companion proves that when its constant value is positive, $q^{\prime }$ is strictly convex on the gap. It therefore lies strictly below its endpoint chord, which is at most one. Integration yields $q(b)-q(a)<b-a$, contradicting contact at both endpoints.

Zero-coefficient gaps require a separate heat-equation argument: $q^{\prime }$ is strictly increasing, so its value stays below the right endpoint bound. This also rules out an initial gap using $q(0)=0$. A terminal plateau is excluded by a boundary layer near the cusp $|x|$: it gives $1-q(t)\ge c\sqrt{1-t}$ near one, forcing $G<0$. Infinite support alone would not establish these exclusions.

🏷️ The integrated curvature certificate

Strict convexity is the analytic core. On a positive constant interval $\gamma =c$, put $r=c{\Phi }_x$, $v=r_x$, $w=r_{xx}$, and $z=r_{xxx}$. Differentiating along the diffusion gives

$$\begin{array}{c}{q}^{\prime \prime \prime }(t)=c^{-2}\\ \times \mathbb{E}[z^2-12v{w}^2+6v^4](t,X_t).\end{array}$$

The negative term prevents a pointwise positivity argument based only on convexity of $\Phi$. The manuscript instead adds a derivative whose integral is zero.

For a smooth finite-step approximation, write the diffusion density as $f=e^{c\Phi }g$ and let $s=-{\partial }_x\log g$ be the score of the forward heat factor. Backward shape inequalities for $r$ and forward comparisons for $s$ produce nonnegative quantities built from $r,s$ and their derivatives. For example, $R=r^2$, $K=rs$, $b=-w/r$, and $j=r(s/r{)}_x$ are used, with quotients extended through zero.

For a polynomial $F$ in these variables, the identity

$$\begin{array}{c}f\left[r{\partial }_{x}F+(v+R-K)F\right]\\ ={\partial }_x(rfF)\end{array}$$

has zero integral when the proved tail estimates remove its boundary terms. The companion chooses a rational polynomial $F$ so that subtracting this derivative from $z^2-12v{w}^2+6v^4$ leaves weighted squares and a remainder with 22 positive coefficients. In particular,

$$\begin{array}{c}\mathbb{E}[z^2-12v{w}^2+6v^4]\\ \ge \frac{1}{1000}\mathbb{E}{v}^4>0.\end{array}$$

We expanded the finite polynomial identity using exact rational arithmetic: all 22 listed coefficients agree, and the coefficient of $v^4$ is $1661507/1521000000>1/1000$. This check verifies the algebraic certificate only. It does not verify the shape inequalities, integration by parts, or approximation theorem needed to apply it.

The limiting argument passes this integrated inequality using spatial derivatives through order four. It does not require convergence of the auxiliary score ratios. This yields strict convexity on every positive constant interval and completes the gap argument.

The companion also derives smoothness and $\gamma (0)=0$ from moment identities. Differentiating $\mathbb{E}{a}^2=1$ gives

$$\gamma (t)=\frac{\mathbb{E}{\Phi }_{xxx}(t,X_t{)}^2}{2\mathbb{E}{\Phi }_{xx}(t,X_t{)}^3}.$$

The denominator is positive. Simultaneous differentiation of polynomial moments bootstraps regularity; a fixed-time approximation by short constant intervals yields ${\gamma }^{\prime }(t)>0$ for $0<t<1$. The selected formal scope states full support and consistency, rather than all these further regularity conclusions.

🏷️ From the diffusion to a finite Gaussian calculation

Full support turns the gradient martingale into a direct representation of the optimum. Its terminal limit $U_1$ has $U_1^2=1$ almost surely, because $|u|\le 1$ and $\mathbb{E}u(t,X_t{)}^2=t\to 1$. The value identities are

$$P_{\ast }=\mathbb{E}[U_1{B}_1]={\int }_0^1\mathbb{E}a(t,X_t)dt.$$

The integral after a stopping time $T<1$ contributes at most $1-T$, by Cauchy–Schwarz and $\mathbb{E}{a}^2=1$.

Fix $T$ and discretize with $\Delta =T/N$, $t_j=j\Delta$, and independent standard Gaussians $Z_1,\dots ,Z_{N+1}$. Euler steps give

$$\begin{array}{rl}{Y}_j=& Y_{j-1}+\sqrt{\Delta }{Z}_j\\ & +\Delta \gamma (t_{j-1})u(t_{j-1},Y_{j-1}),\\ & Y_0=0.\end{array}$$

Normalize the martingale directions as $g_j=c_{j}a(t_{j-1},Y_{j-1})Z_j$, where $c_j=(\mathbb{E}a(t_{j-1},Y_{j-1}{)}^2{)}^{-1/2}$. They are orthonormal in $L^2$, and $c_j\to 1$ uniformly as the mesh is refined at fixed $T$.

Use the last Gaussian to round the terminal gradient to a spin:

$$\begin{array}{c}{F}_N=\mathrm{sgn}(u(T,Y_N)+U),\\ U=2F_{\mathrm{G}}(Z_{N+1})-1,\end{array}$$

where $F_{\mathrm{G}}$ is the standard Gaussian distribution function. The variable $F_{\mathrm{G}}(Z_{N+1})$ is uniform on $(0,1)$, so $U$ is uniform on $(-1,1)$ and the conditional mean of $F_N$ given the first $N$ Gaussians is exactly $u(T,Y_N)$.

Set $A_j=\mathbb{E}[F_N{g}_j]$, $B_i=\mathbb{E}[F_N{Z}_i]$, and $A_0=0$. The companion proves

$$\begin{array}{c}\underset{N\to \infty }{\lim }\sum _{j=0}^N{A}_j{B}_{j+1}\\ ={\int }_0^T\mathbb{E}a(t,X_t)dt.\end{array}$$

The shifted index matters. The coefficient vectors approach $\sqrt{\Delta }/c_j$ and $\sqrt{\Delta }\mathbb{E}a(t_{i-1},Y_{i-1})$, respectively, in ${\ell }^2$. Their shifted product is a Riemann sum; Cauchy–Schwarz controls accumulated errors, and the extra rounding-coordinate term tends to zero. The order is mesh refinement at fixed $T$, then $T\uparrow 1$.

🏷️ Rooted energy and quantum synthesis

The QAOA manuscript realizes the finite Gaussian calculation on a limiting rooted tree. Symmetric Fock space records how many child states differ from the initial state; these “particles” count excitations in a representation, not physical spins. A centered child vector $f$ defines a Gaussian coordinate at its parent with covariance $⟨f,g⟩$ against the coordinate from $g$.

Starting with a local Gaussian seed $g_0$, recursively lift $g_j$ to the next Gaussian $Z_{j+1}$. Conditional mean zero and the normalization of the $g_j$ make them orthonormal, so their Gaussian lifts are exactly independent. This is an orthogonality argument within the rooted construction; arbitrary calculations sharing descendants are not assumed independent.

A root-shift isometry $\mathsf{L}$ moves a centered vector to one child excitation and leaves the new root initially unchanged. The limiting edge energy is the bounded quadratic form $\mathcal{E}(f)=\mathrm{Re}⟨f,\mathsf{L}f⟩$. Its continuity estimate is

$$\begin{array}{c}|\mathcal{E}(f)-\mathcal{E}(g)|\\ \le (\Vert f\Vert +\Vert g\Vert )\Vert f-g\Vert .\end{array}$$

Extracting the one-particle component gives $\mathcal{E}(F_N)={\sum }_j{A}_j{B}_{j+1}$. Thus the scalar coefficient identity supplies a near-optimal rooted target with its energy, not merely its distribution.

Smooth bounded approximations replace the sign and unbounded transmitted functions. A finite type partition then excludes the receiver’s type, all path-ancestor types, and a small set of helper types from each aggregation. These exclusions prevent a compiled operation from changing its own parameters. The output can be written as $\sin (2\theta )$ for a bounded odd angle calculation.

The synthesis theorem implements that calculation with cost and mixer gates plus a temporary Gaussian longitudinal control $\exp (-it{\sum }_i{s}_i{Z}_i)$. Helper spins implement neighbor aggregation through commutators along receiver–sender–helper–sender walks. Subdividing sender types preserves walks returning to the same sender while suppressing different-sender contributions. The theorem controls repeated use inside a fixed surrounding circuit, including changes to lower formulas.

If helpers have total probability $p_H$, the energy error is at most $2\eta +2\sqrt{p_H}$ for synthesis tolerance $\eta$. Helpers are chosen rare but with fixed positive probabilities before compilation.

The extra seed field must then be removed. The manuscript constructs a small-amplitude component with a large coherent displacement. Selective rotations act on it while cancelling their leading action on the main component; a long cost echo turns that small change into a finite longitudinal field. The same effective Gaussian seed must be reusable throughout the word. A separate root-shift calculation controls energy, since reproducing a Gaussian law alone would be insufficient.

These operator and echo estimates are substantial inputs from the QAOA manuscript. The selected review covers their statements, roles, and final assembly; it does not independently verify the full synthesis and seed-removal proofs.

🏷️ Fixing the word before taking limits

The final construction chooses the scalar stopping time and mesh, bounded approximation, type exclusions, helper operations, seed compilation, and echo parameters in that order. Each inner approximation is finite after its outer tolerance has been chosen. Negative and large angles are allowed; consecutive identical gate types can be merged, with zero-angle gates inserted to obtain standard QAOA form.

Only after this process produces one ordinary finite cost–mixer word does the imported tree-to-SK identity apply. For that fixed word, its SK value equals the limit of $\sqrt{D}/2$ times the distinguished-edge correlation on the $(D+1)$-regular tree with cost $D^{-1/2}{\sum }_{\{i,j\}}{Z}_i{Z}_j$.

An error allocation of $\epsilon /4$ for the classical target, synthesis plus helper errors below $\epsilon /2$, and seed-removal error below $\epsilon /4$ gives value above $P_{\ast }-\epsilon$. There is no exchange of the depth, degree, size, and approximation limits.

As a consequence, a fixed normalized word achieves expected MaxCut fraction at least $1/2+(P_{\ast }-\eta )/\sqrt{D}$ on $(D+1)$-regular graphs of girth greater than $2p+1$, for sufficiently large $D$. Its usual MaxCut cost angles are $2\mathbf{\gamma }/\sqrt{D}$. The separate comparison with the optimum concerns random regular graphs, first sending size to infinity at fixed degree, then degree to infinity. It does not assert optimality on every high-girth graph or at fixed degree.

🏷️ Source and formalization boundaries

The companion’s full-support proof, contact conditions, rational certificate, curvature transfer, moment identities, and finite Gaussian coefficients were read along with selected analytic prerequisites. The QAOA paper was reviewed through its definitions, scalar realization, synthesis interfaces, seed-removal interface and conclusion, final assembly, and MaxCut consequence. The full operator estimates, shape-propagation proofs, positive-temperature alternative, and external theorems were not independently verified.

The selected formalization gives Parisi value identities and Gaussian approximations conditional on an admissible minimizer and its diffusion; it does not assert convergence of QAOA circuit energies. Its second statement gives full relative support and selected consistency identities for an admissible minimizer, without separately asserting existence. These boundaries are narrower than the manuscripts’ combined conclusions.

Ashkin–Teller criticality offers a contrasting statistical-mechanics setting in which the interaction structure and limiting observable differ from the mean-field SK energy. Exact quantum factoring highlights a different circuit guarantee: an explicit polynomial worst-case bound, which the QAOA optimality theorem here does not provide.

🏷️ Key steps and proof outlines

The helper commutator distinguishes a return from a new sender

The synthesis theorem depends on a specific cancellation. Let $I,J,K$ denote disjoint receiver, sender, and helper masks, and partition $J$ into pieces $J_l$ of probabilities $p_l$. Fix the lower formula $f_j$ before refining the partition; its dependencies avoid all three masks. Write $A_{ij}=D^{-1/2}{1}_{i\sim j}$. The elementary commutators construct

$$\begin{array}{rl}{H}_l& =\sum _{i,j,k}{A}_{ij}{A}_{jk}{P}_i{X}_j{Z}_k,\\ G_l& =\sum _{j,k}{A}_{jk}{X}_j{f}_j{Y}_k,\end{array}$$

where $i\in I,j\in J_l,k\in K$, and $P$ is the required receiver Pauli axis. Commuting once more at the helper gives paths $i-j-k-j^{\prime }$, with $j,j^{\prime }\in J_l$.

For a return $j^{\prime }=j$, $X_j^2=I$, the pinned helper satisfies $X_k=1$, and averaging its adjacent helper population supplies the factor $p_K$. Dividing by $p_K$ leaves the desired coupling of the receiver to the sender formula. Paths with distinct $j,j^{\prime }$ are the error. Refinement suppresses them because both senders must fall in the same small part: the squared column estimate contains ${\sum }_l{p}_l^2$, which tends to zero.

A helper-root cut requires an additional subtraction. If $d_l,e_l$ are its incoming child vectors and $q(d)$ denotes the corresponding Gaussian field, the correction is

$$Q_K=\frac{1}{p_K}\sum _l(q(d_l)q(e_l)-⟨d_l,e_l⟩).$$

The inner product is the same-neighbor covariance. Treating the two fields as independent would lose precisely the desired return contribution. Orthogonality between partition pieces controls this centered quadratic field. The source also checks cuts inside the lower formula, so this contraction can be called repeatedly inside a surrounding circuit. These operator estimates, rather than the path picture alone, justify recursive synthesis. (OpenAI, 2026b, p.c ontraction through unused spins)

The terminal cusp rules out a plateau by a quantitative boundary layer

Interior curvature does not by itself exclude a final interval on which the order parameter is constant. Suppose $\gamma =c\ge 0$ on $(a,1)$. For $c>0$, set

$$h(t,y)=\mathbb{E}{e}^{c|y+\sqrt{1-t}Z|}.$$

The drift $c{\Phi }_x=h_x/h$ is a change of measure of Brownian motion, with transition density

$$k_{s,t}(x,y)=p_{t-s}(y-x)\frac{h(t,y)}{h(s,x)}.$$

For $c=0$, use $h=1$. Choose a fixed $s>a$ and a bounded interval carrying positive mass under $X_s$. The Gaussian factor then gives a uniform positive lower bound for the density of $X_t$ near $y=0$, for all $t$ sufficiently close to one.

Put $ϵ=1-t$. When $|y|\le \sqrt{ϵ}$, the two events $y+\sqrt{ϵ}Z>0$ and $<0$ both have a fixed positive probability, also after normalization by the bounded exponential tilt. Since $u(t,y)$ is the tilted mean of this sign, $1-u(t,y{)}^2\ge \kappa >0$ throughout that interval. Its width is $2\sqrt{ϵ}$, so

$$1-q(t)=\mathbb{E}[1-u(t,X_t{)}^2]\ge C\sqrt{1-t}.$$

Consequently $q(t)-t\le (1-t)-C\sqrt{1-t}<0$ near the endpoint, contradicting nonnegativity of the contact potential $G$.

The proof combines a spatial density lower bound and a conditional sign-variance lower bound. Neither alone controls the expectation. This explains why the nonsmooth terminal condition contributes a square-root boundary layer and why a terminal plateau needs its own argument. (OpenAI, 2026a)

🏷️ Manuscripts and verification scope

• QAOA attains the SK ground-state energy in the thermodynamic-first limit — pinned manuscript and companion source.
• Full support of the zero-temperature Sherrington–Kirkpatrick order parameter — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The selected Parisi value and finite Gaussian approximation statements are conditional on an admissible minimizer and its associated diffusion; they do not assert convergence of QAOA circuit energies. The full-support statement covers any admissible integrable minimizer in the pure zero-field model with covariance t²/2 and selected diffusion consistency identities, without separately asserting existence of a minimizer. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Full support of the zero-temperature Sherrington–Kirkpatrick order parameter.

🐻  OpenAI 2026b. QAOA attains the SK ground-state energy in the thermodynamic-first limit.