  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-\epsilon)$ 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.
