Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Quantum Approximate Optimization Algorithm and the
  Sherrington-Kirkpatrick Model at Infinite Size   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 be tailored to 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.

10
The categories of this paper are: q-bio
14
The categories of this paper are: math-ph
16
The categories of this paper are: stat
28
The categories of this paper are: alg-geom
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
24
The categories of this paper are: dg-ga
31
The categories of this paper are: ao-sci
22
The categories of this paper are: chao-dyn
7
The categories of this paper are: hep-th
21
The categories of this paper are: adap-org
23
The categories of this paper are: solv-int
29
The categories of this paper are: funct-an
12
The categories of this paper are: nucl-th
6
The categories of this paper are: astro-ph
30
The categories of this paper are: q-alg