QAOA attains the SK optimum in the thermodynamic-first limit

The explanation

Take three spins, each pointing up (+1) or down (−1). Give each pair a random coupling: J₁₂ = 1.0, J₁₃ = −0.5 and J₂₃ = 0.8. The energy adds J times the two spins for each pair, divided by √3. A positive coupling likes the pair to agree; a negative one likes them to differ. Here all three wishes cannot hold at once. Checking all eight arrangements, the best is all spins up, with energy 1.3/√3 ≈ 0.751. That is about 0.250 per spin.

This is the Sherrington–Kirkpatrick model, a mean-field spin glass with independent Gaussian couplingsSource 1. A spin glass is a magnet with conflicting random interactions. For n spins, finding the best arrangement means searching 2ⁿ options. As n grows, the best energy per spin approaches a fixed constant P*. Parisi's theory describes P* through an order parameter, a function that records how pairs of good states overlapSource 2. Auffinger and Chen gave the ground-state version of Parisi's formula.

QAOA, the quantum approximate optimization algorithm, alternates two steps on qubitsSource 3. One step applies the energy function; the other mixes with a transverse field. A list of angles sets each step's strength. The depth p is the number of alternations. For each fixed instance, more depth eventually reaches its optimumSource 4. That does not give one finite depth that works as the number of spins growsSource 4. Basso and co-authors conjectured that QAOA's limiting energy approaches the Parisi optimum as depth growsSource 5.

The first paper claims that conjecture in its fixed-parameter thermodynamic formSource 6. Let the number of spins go to infinity first, then raise the depth. For every accuracy, some finite depth and fixed angles reach it in expected energy per spinSource 7. The angles do not depend on the system size or the couplingsSource 7. The paper gives no bound on the depth and no efficient way to choose the anglesSource 8.

The second paper supplies a key input. It proves the zero-temperature order parameter has full support on [0, 1)Source 9. This means its support has no gaps at any overlap scale below oneSource 9. Chen proved the same support conclusion separatelySource 10. The QAOA paper also gives a separate positive-temperature routeSource 11.

How sure is this? Lean, a computer proof checker, has formal proofs of the full-support theorem for any minimizer. It also proves value identities for the SK ground-state energy, given a Parisi minimizer. The Lean statement does not assert convergence of QAOA circuit energies. That main claim rests on the paper's long construction. No specialist review has been published.

What it doesn't show. This does not bound the depth needed, give an efficient way to choose angles, or say anything for a fixed finite number of spins.