  The Quantum Approximate Optimization Algorithm (QAOA) finds approximate
solutions to combinatorial optimization problems. Its performance monotonically
improves with its depth $p$. We apply the QAOA to MaxCut on large-girth
$D$-regular graphs. We give an iterative formula to evaluate performance for
any $D$ at any depth $p$. Looking at random $D$-regular graphs, at optimal
parameters and as $D$ goes to infinity, we find that the $p=11$ QAOA beats all
classical algorithms (known to the authors) that are free of unproven
conjectures. While the iterative formula for these $D$-regular graphs is
derived by looking at a single tree subgraph, we prove that it also gives the
ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK)
model defined on the complete graph. We also generalize our formula to
Max-$q$-XORSAT on large-girth regular hypergraphs. Our iteration is a compact
procedure, but its computational complexity grows as $O(p^2 4^p)$. This
iteration is more efficient than the previous procedure for analyzing QAOA
performance on the SK model, and we are able to numerically go to $p=20$.
Encouraged by our findings, we make the optimistic conjecture that the QAOA, as
$p$ goes to infinity, will achieve the Parisi value. We analyze the performance
of the quantum algorithm, but one needs to run it on a quantum computer to
produce a string with the guaranteed performance.
