Source-linked AI summary
The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Leo Zhou
TL;DR
The paper asks how QAOA performs on typical instances of the all-to-all Sherrington-Kirkpatrick model, where its computational power is not fully understood. It develops an infinite-size energy formula and evaluates it through p = 12. At p = 11, QAOA surpasses standard semidefinite programming, while measured energies concentrate at the calculated value.
Problem
QAOA’s performance on typical instances of the Sherrington-Kirkpatrick model is not fully explored, despite the model’s role as an all-to-all combinatorial optimization problem.
Method
The paper develops a technique and explicit formula for the typical-instance QAOA energy at fixed p in the infinite-size limit.
Results
At p = 11, QAOA surpasses standard semidefinite programming, with V̄11 ≤−0.6393 < −2/π, and finite-size simulations show agreement up to O(1/√n) effects.
Takeaways & Limitations
For fixed p, QAOA measurements on almost every SK instance concentrate at the calculated energy, enabling parameters to be determined in advance for typical instances.
Takeaways & Limitations
The p = 1 analysis uses symmetry of the coupling distribution, and the behavior of QAOA at large p relative to the Parisi value remains uncertain.
Abstract
from arXiv · showhide
The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers $p$. While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of $n$ spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within $(1-ε)$ times the ground state energy. We hope to match its performance with the QAOA. Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the $2p$ QAOA parameters, in the infinite size limit that can be evaluated on a computer with $O(16^p)$ complexity. We evaluate the formula up to $p=12$, and find that the QAOA at $p=11$ outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as $n\to\infty$, measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.
1 Introduction
QAOA is a shallow, parameterized quantum algorithm for approximate combinatorial optimization whose typical-instance behavior can be analyzed through parameter-dependent cost landscapes. The paper applies this perspective to the SK model and develops an infinite-size evaluation method.
- QAOA uses a shallow quantum circuit with p layers and 2p parameters for approximate combinatorial optimization.
- For large systems, the expected cost depends on QAOA parameters but not on the particular typical instance, up to finite-size effects.Thus, optimal parameters are shared across typical instances from the same distribution.
- The paper introduces a technique to evaluate typical-instance QAOA energy for arbitrary fixed p as the problem size tends to infinity.It applies the technique to the Sherrington-Kirkpatrick model and shows concentration of measured energies at the calculated value.
- The paper summarizes its results through a formula for typical-instance QAOA energy and evaluations up to p = 12.
2 The Quantum Approximate Optimization Algorithm (QAOA)
QAOA prepares a parameterized quantum state by alternating cost-dependent and mixing unitaries. Measuring this state yields candidate bit strings, while the paper focuses on determining optimal parameters in advance for typical SK instances.
- QAOA encodes a classical cost function C(z) as a diagonal computational-basis operator and seeks strings near its absolute minimum.
- The circuit alternates p layers of cost and mixing unitaries, using parameter vectors γ and β with p components each.
- The QAOA objective function is evaluated for a given cost function C and its parameterized quantum state.
- Measuring the QAOA state produces a bit string whose cost is near the objective value or better.For typical SK instances, the paper seeks optimal parameters in advance rather than optimizing them separately for every instance.
3 The Sherrington-Kirkpatrick (SK) model
The SK model is a complete-graph spin system with random all-to-all couplings, and its ground-state energy is known asymptotically. Existing approaches include simulated annealing, semidefinite relaxations, and a conjecture-dependent classical algorithm.
- The SK model describes n spins with all-to-all couplings and can be formulated as a combinatorial search problem on a complete graph.
- Couplings Jjk are independently drawn from a mean-zero, variance-one symmetric distribution, including ±1 or standard normal examples.The asymptotic classical and quantum results are stated to be independent of the chosen coupling distribution under these assumptions.
- The Parisi formula characterizes the limiting typical-instance energy, although evaluating it is extremely challenging.
- At T = 1, typical instances have energy density C/n = −0.5.
- Simulated annealing reaches C/n = −0.754 on a 10000-bit instance after 10 million steps but is not believed to reach the lowest energy.
- Spectral relaxation and standard semidefinite programming with sign rounding yield C/n = −2/π + o(1) ≈ −0.6366.
- Assuming full replica symmetry breaking, Montanari’s algorithm finds typical-instance strings below (1 −ϵ) times the lowest energy in time c(ϵ)n2.
4 Summary of Results
The paper develops an infinite-size formula for typical-instance QAOA energy on the SK model, proves concentration over instances and measurements, and evaluates performance through p=12. The computed results surpass standard semidefinite programming at p=11, while higher-p values beyond p=8 are not fully optimized.
- Formula and concentration: The main result is an explicit formula for the typical-instance QAOA energy Vp(γ, β) in the infinite-size limit.The formula applies at fixed p and arbitrary QAOA parameters.
- Formula and concentration: The QAOA energy concentrates at Vp(γ, β) over both typical SK instances and computational-basis measurements as n→∞.The concentration result holds for any fixed p and any parameters (γ, β).
- Formula and concentration: The formula can be evaluated using O(16^p) time and O(4^p) memory.The computation stores a vector of dimension |D| = (4^p − 2^p)/2 and evaluates the required sums.
- Numerical evaluation: The calculation was optimized through p=8 and evaluated through p=12, with p=9–12 using extrapolated, unoptimized parameters.The p=9–12 values therefore provide upper bounds on the optimized values.
- Numerical evaluation: At p=11, the QAOA reaches V̄11 ≤ −0.6393, surpassing the standard semidefinite-programming value −2/π ≈ −0.6366.The infinite-size predictions also agree well with simulations of 30 random 26-spin instances.
- Numerical evaluation: For p=8, the optimal parameters repeatedly emerged as the best local minimum across 10^4 random starting points.The observed parameter pattern was used to generate guesses for p=9–12.
5 The QAOA applied to the SK model at p = 1
The paper evaluates the QAOA at p = 1 by changing to a configuration basis and computing first and second moments of the SK energy. In the infinite-size limit, the two moments coincide in the relevant sense, yielding concentration, while finite-size fluctuations scale as O(1/√n).
- Configuration-basis calculation: At p = 1, the analysis changes from string sums to a configuration basis indexed by the four possible paired-bit configurations.The configuration counts are summarized using multinomial coefficients.
- Moment calculation: The p = 1 calculation evaluates the expected first and second moments of the normalized cost by differentiating with respect to an auxiliary parameter.The first and second moments are then simplified using the configuration counts and QAOA transition amplitudes.
- Infinite-size limit: The infinite-size p = 1 formula is the same for Gaussian and uniformly signed couplings, despite their finite-size expressions differing slightly.This agreement holds when the couplings are drawn from the standard normal distribution or uniformly from {+1, −1}.
- Concentration: The infinite-size second moment equals the square of the first moment, implying concentration over both instances and measurements.The paper explicitly connects this equality to concentration in the QAOA output energy.
- Finite-size effects: O(1/n) variance and O(1/√n) standard deviation characterize the combined finite-size fluctuations over instances and measurements.At p = 1, finite-size optimization changes γ by O(1/n), while β remains unchanged from its infinite-size value.
- Generic QAOA states: Generic parameter choices can produce exponentially small expected cost, concentrating useful behavior near a parameter region with γ of order 1/√n.The paper relates this observation to barren-plateau concerns for variational quantum algorithms.
6 General p
The paper proves an arbitrary-p procedure for evaluating the first and second moments of the QAOA energy for typical SK instances as n→∞. The resulting expression uses an iterative classical computation over configurations and establishes the corresponding energy formula.
- O(16^p) complexity evaluates the first and second moments of C/n for arbitrary p and any 2p QAOA parameters in the n→∞ limit.The procedure corresponds to the formula given in Section 4.
- A sequence of bit-wise string transformations makes each f factor depend on one transformed string and absorbs z_m into other variables.After transformation, the coupling variables J_jk appear together with z_m, enabling the subsequent averaging step.
- The calculation reorganizes sums over 2p-layer strings into a configuration basis A = {+1, −1}^2p and configuration counts n_a.Each configuration records the indexed bits across the strings, allowing the sums to be expressed through multiplicities.
- The theorem gives the expected QAOA energy for a typical SK instance in the infinite-size limit through computable functions W_u(γ, β).The resulting expression is identified as the expected energy, and the paper states that the proof establishes its main theorem.
7 Discussion
For growing-degree graphs such as the complete graph underlying the SK model, fixed-depth locality arguments differ from bounded-degree cases. The paper evaluates this prospect and finds improved performance with increasing p, while leaving the large-p asymptotics unresolved.
- At p = 1, each SK clause sees all qubits, and at p = 2 it sees all qubits and all edges.The SK interaction graph is complete, so bounded-degree locality arguments do not apply.
- O(16^p) complexity permits optimization up to p = 8 and evaluation up to p = 12, while a later O(p2 4^p) result reaches p = 20.The paper reports its own evaluation range and notes the improved complexity from Ref. [17].
- At p = 4, the QAOA energy crosses −0.5n, and at p = 11 it surpasses spectral relaxation and standard semidefinite programming, which yield −2n/π.The paper states that the large-p limit may approach the Parisi value or something less optimal.