QAOA attains the SK optimum in the thermodynamic-first limit

2 papersLean

Proves that QAOA approaches the ground-state energy of the Gaussian zero-field Sherrington–Kirkpatrick model when system size tends to infinity before circuit depth. For every accuracy, finite depth and deterministic angles independent of size and disorder achieve the required limiting expected energy per spin. This also yields leading-order optimal expected MaxCut values on large-degree random regular graphs, with size tending to infinity before degree.

Watch

▶Introduction: the problem and why it mattersin preparation

▶The presented solutionin preparation

Papers 2

QAOA attains the SK ground-state energy in the thermodynamic-first limit

OpenAI · September 25, 2026

We prove that the Quantum Approximate Optimization Algorithm (QAOA) approaches the ground-state energy per spin of the Gaussian zero-field Sherrington–Kirkpatrick model when system size tends to infinity first and circuit depth then increases. For every accuracy, some finite depth and deterministic angles, independent of system size and disorder, achieve that accuracy in the limiting expected energy per spin using the standard cost Hamiltonian and transverse-field mixer. This proves the eventual Parisi-optimality conjecture of Basso, Farhi, Marwaha, Villalonga, and Zhou in its fixed-parameter thermodynamic formulation. We give no quantitative bound on the required depth or efficient angle-selection procedure.

Read PDF Download Source

Cite

@misc{OAI:QAOA-attains-the-SK-ground-state-energy-in-the-thermodynamic-first-limit-September-25-2026,
  author = {{OpenAI}},
  title = {{QAOA attains the SK ground-state energy in the thermodynamic-first limit}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/QAOA-attains-the-SK-ground-state-energy-in-the-thermodynamic-first-limit-September-25-2026/QAOA-attains-the-SK-ground-state-energy-in-the-thermodynamic-first-limit-September-25-2026.pdf}{OAI:QAOA-attains-the-SK-ground-state-energy-in-the-thermodynamic-first-limit-September-25-2026}},
  year = {2026}
}

Full support of the zero-temperature Sherrington-Kirkpatrick order parameter

OpenAI · September 27, 2026

We prove that every admissible integrable minimizer of the zero-temperature Parisi functional for the pure, zero-field Sherrington–Kirkpatrick model has full relative Stieltjes support on \([0,1)\). Thus its support has no gaps at any overlap scale below one. We use the covariance normalization \(\xi(t)=t^2/2\).

Read PDF Download Source

Cite

@misc{OAI:Full-support-of-the-zero-temperature-Sherrington-Kirkpatrick-order-parameter-September-27-2026,
  author = {{OpenAI}},
  title = {{Full support of the zero-temperature Sherrington--Kirkpatrick order parameter}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Full-support-of-the-zero-temperature-Sherrington-Kirkpatrick-order-parameter-September-27-2026/main.pdf}{OAI:Full-support-of-the-zero-temperature-Sherrington-Kirkpatrick-order-parameter-September-27-2026}},
  year = {2026}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

The linked formalization supplies variational identities for the Gaussian zero-field Sherrington–Kirkpatrick ground-state energy used in the paper's QAOA argument. Conditional on an admissible Parisi minimizer and its associated diffusion, it proves convergence of the finite-system ground-state energy, identifies its limit with the Parisi value, and gives equivalent terminal-martingale and integrated-curvature formulas.

It also proves convergence of finite Gaussian coefficient sums to the curvature integral, which approaches the ground-state value as the terminal time tends to one. The selected statement covers these value and approximation results; it does not itself assert convergence of QAOA circuit energies.

The formalization proves that every admissible integrable minimizer of the zero-temperature Parisi functional for the pure zero-field Sherrington–Kirkpatrick model has full relative Stieltjes support on \([0,1)\). Equivalently, the order parameter increases strictly between every two overlap values below one, so its support has no gap. The covariance normalization is \(\xi(t)=t^2/2\).

The statement also constructs the associated diffusion and proves its selected self-consistency moment identities. It is conditional on the order parameter being a minimizer and does not separately assert existence of a minimizer.

Comparator links

Result	Comparator statement
Parisi ground-state value identities and finite Gaussian approximation	SKValue.lean
Full support of zero-temperature SK minimizers	SKFullSupport.lean

Scope note on GitHub →