The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size

By Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Leo Zhou. Quantum, 2019

309 citations recorded by the source corpus.

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(16p) 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→∞, 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/1a3538deece965f8ba487eba7119fdf009910152

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Quantum approximate optimization of non-planar graph problems on a planar superconducting processor (2020, background): “While the prospects for achieving quantum advantage with QAOA remain unclear, QAOA prescribes a simple paradigm for optimization which makes it amenable to both analytical results and implementation on current processors [13– 21].”
Challenges and opportunities in quantum optimization (2023, unknown): “52,53).”
Barren plateaus in variational quantum computing (2024, unknown): “With the previous being said, there have been promising research direction to train a quantum alternating operator ansatz in regimes where the BP proofs do not hold (for exaxmple, training classically on small problems and transferring parameters) 134–139 .”