QAOA reaches the optimum, proved at last?
Two AI preprints claim QAOA attains the Sherrington–Kirkpatrick optimum, size first and depth second
Covers result 281 in OpenAI’s catalog: all 2 papers. See its connections to other results and the work it cites.
3:39. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
Picture a magnet in which every pair of spins is linked by a random coupling, some pulling them alike, some apart: the Sherrington–Kirkpatrick spin glass. As it grows, the best arrangement’s score per spin approaches a constant given by Parisi’s formula, about 0.763, called P*. The quantum approximate optimization algorithm, QAOA, alternates two kinds of pulses, p rounds of each, with tunable angles. For infinitely many spins its best score at depth 1 is 1/√(4e), about 0.303; published values reach 0.591 at depth 7 (our computer reproduces them) and about 0.748 at depth 160. In 2021 Basso, Farhi, Marwaha, Villalonga and Zhou conjectured that these values reach P* as the depth grows, with the number of spins going to infinity first.
Result 281 is two OpenAI preprints, 97 pages, dated September 25 and 27, 2026. The main paper claims that conjecture. For every accuracy, some finite depth and fixed angles, not depending on the size or the couplings, get that close on average as the size grows. A corollary: on random regular graphs of large degree, QAOA’s expected cut comes as close as desired to the best cut at leading order, 1/2 + P*/√degree.
What it doesn’t claim
Any bound on the depth, a recipe for the angles, guarantees at finite size, or a speedup. A classical algorithm by Montanari, unconditional since July 2026, already gets within any accuracy in time growing like the square of the size.
Where it stands
- Posted as preprints
- OpenAI, two papers, 97 pages, dated September 25 and 27, 2026
- Peer reviewed
- Not yet
- Formalized in Lean
- In part: classical inputs only, not the QAOA theorem (docs)
Last checked October 19, 2026. The preprints have not been revised. In Lean only classical inputs are formalized, in two parts of about 30,000 and 20,000 lines; our scan finds no unproved steps, but we did not rebuild them. The QAOA theorem itself is not formalized. OSVerify has not reviewed it, and we found no comment from specialists.
How the proof goes
- No gaps. Approximating Parisi’s solution with more and more steps gives upper bounds falling from 0.798 to 0.765, then 0.7636, toward P*. The companion paper proves that the full zero-temperature solution has no gaps, a result Hong-Bin Chen had posted in July, as the paper acknowledges. That is what lets message passing, the classical method of Montanari and colleagues, reach the optimum.
- Imitation. For a fixed circuit at infinite size, the spin glass scores the same as an infinitely bushy tree (an identity of Basso and colleagues), and the messages passed along the tree can be built from quantum pulses, first with temporary random seed fields, which echo constructions then remove. What remains is one fixed, finite sequence of pulses, possibly with very large angles.
The numbers in the video
- Ours: QAOA’s infinite-size values for depth 1 to 7, 0.3033 to 0.5915, matching the published tables.
- Published: 0.6773 at depth 17 (Basso and colleagues, 2021) and 0.7483 at depth 160 (Boulebnane and colleagues, September 30, 2026).
- Ours: step-function upper bounds on the Parisi value, 0.798, 0.765, 0.7636, 0.7633 and 0.7632, against P* ≈ 0.763166.
Read the source
- QAOA Attains the SK Ground-State Energy in the Thermodynamic-First Limit (PDF), 70 pages.
- Full Support of the Zero-Temperature Sherrington–Kirkpatrick Order Parameter (PDF), 27 pages.
- The Lean formalization notes.
- The collection’s catalog, where this is result 281.
The 2 papers in this result
OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.
Transcript
Read the full script
0:00The question
Picture a magnet in which every pair of spins is linked by a random coupling, some pulling them alike, some apart. This is the Sherrington–Kirkpatrick spin glass. As it grows, the best arrangement’s score per spin approaches a constant given by Parisi’s formula, about 0.763, called P*. The quantum approximate optimization algorithm, QAOA, alternates two kinds of pulses, p rounds of each, with tunable angles. For infinitely many spins, its best score at depth 1 is 1/√(4e), about 0.303. Our computer reproduces the published values up to depth 7, 0.591, and others have reached about 0.748 at depth 160. In 2021, Basso, Farhi, Marwaha, Villalonga and Zhou conjectured that these values reach P* as the depth grows. The order of limits matters: the number of spins goes to infinity first, so one fixed depth and one fixed set of angles, the same at every size, are judged as the size grows without bound.
1:08The claims
Result 281 is two OpenAI preprints, 97 pages, dated September 25 and 27, 2026. The main paper claims that conjecture: with the size going to infinity first and then the depth, QAOA’s best expected score per spin approaches P*. For every accuracy, some finite depth and fixed angles, not depending on the size or the couplings, get that close on average as the size grows. A corollary: on random regular graphs of large degree, QAOA’s expected cut comes as close as desired to the best cut at leading order, 1/2 + P*/√degree. Not claimed: any bound on the depth, a recipe for the angles, guarantees at finite size, or a speedup. A classical algorithm by Montanari, unconditional since July, already gets within any accuracy in time growing like the square of the size.
2:03How the proof goes
The key input concerns Parisi’s solution. Approximating it with more and more steps, our computer finds the upper bound falling from 0.798 to 0.765, then 0.7636, toward P*. The companion paper proves that the full solution has no gaps, a result Hong-Bin Chen had posted in July, as the paper acknowledges. That is what lets message passing, the classical method of Montanari and colleagues, reach the optimum. The main proof then makes QAOA imitate that classical algorithm. For a fixed circuit at infinite size, the spin glass scores the same as an infinitely bushy tree, and the messages passed along it can be built from quantum pulses, first with temporary random seed fields, which echo constructions then remove. What remains is one fixed, finite sequence of pulses, possibly with very large angles.
3:01Where it stands
The preprints are unrefereed and unchanged since release. In Lean, only classical inputs are formalized, in two parts of about 30,000 and 20,000 lines; our scan finds no unproved steps, but we did not rebuild them. The QAOA theorem itself is not formalized. OSVerify has not reviewed it, and we found no comment from specialists. If it holds, for any accuracy, a quantum circuit of fixed depth comes that close to the spin glass optimum on average as systems grow, though how deep it must be, nobody knows.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.