Abstract
The Quantum Approximate Optimization Algorithm (QAOA) achieves monotonically improving performance with circuit depth p, yet the study of the high-depth regime has been obstructed by the exponential in p cost of existing exact evaluation techniques. In this Letter, we prove that, in the infinite-size limit, the depth-p QAOA state for the Sherrington-Kirkpatrick (SK) model converges to the state of a spin coupled to p bosonic modes. We simulate the spin-boson system using matrix product states and provide numerical evidence that QAOA obtains a (1-ε) approximation to the optimal energy of the SK model with circuit depth O(n/ε^1.13) in the average case. The modest computational cost of our approach allows us to optimize QAOA parameters and observe that QAOA achieves ε 2.2% at p=160 in the infinite-size limit, extending far beyond p≤ 20 accessible to prior exact methods. Our mapping provides a many-body route to study and optimize high-depth QAOA in regimes previously inaccessible to exact evaluation.