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

Edward Farhi; Jeffrey Goldstone; Sam Gutmann; Leo Zhou

doi:10.22331/q-2022-07-07-759

paper

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

arXiv:1910.08187 · doi:10.22331/q-2022-07-07-759

Abstract

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 $2 p$ QAOA parameters, in the infinite size limit that can be evaluated on a computer with $O (1 6^{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.

32 pages, 2 figures, 2 tables. Improved presentation for journal version. Results and technical content unchanged since v2

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

Abstract

References in corpus (5)

Cited by in corpus (105)