Abstract
The Quantum Approximate Optimization Algorithm (QAOA) uses a quantum computer to implement a variational method with layers of alternating unitary operators, optimized by a classical computer to minimize a cost function. While rigorous performance guarantees exist for the QAOA at small depths , the behavior at large depths remains less clear, though simulations suggest exponentially fast convergence for certain problems. In this work, we gain insights into the deep QAOA using an analytic expansion of the cost function around transition states. Transition states are constructed recursively: from a local minima of the QAOA with layers we obtain transition states of the QAOA with layers, which are stationary points characterized by a unique direction of negative curvature. We construct an analytic estimate of the negative curvature and the corresponding direction in parameter space at each transition state. Expansion of the QAOA cost function along the negative d