Analysis of the Quantum Approximate Optimization Algorithm with Constant Evolution Time

We introduce a systematic analytic framework to study the Quantum Approximate Optimization Algorithm (QAOA) on random quadratic problems in the constant time regime. While this regime covers optimized QAOA at constant depth, our framework allows to take the depth to infinity as long as the total evolution time is kept constant. Besides, where previous analytic results required taking the infinite size limit, our methods also give access to finite size corrections. Our results are applicable to QAOA used as an approximate optimizer (approximately optimizing a local cost function) or as an exact solver (producing an optimal solution with high probability). We derive several lessons from a numerical implementation of these analytic methods. First, we explore the infinite depth, constant time limit of QAOA corresponding to constant time annealing. We observe QAOA already converges to this regime for a small, yet problem-size-independent Trotterization step, suggesting the QAOA state might be best understood as living in a problem-size-independent subspace. We further compute the first finite-size correction to the energy at optimal angles for common constraint satisfaction problems, leading to fundamental and practical insights on the relation between finite size and infinite size angles. Finally, we revisit the mean-field formalism of QAOA introduced by [Hogg, 2000], showing that in certain cases, particularly at optimal angles, the homogeneity assumption underlying this approach fails to hold.