Analyzing high-depth QAOA for MaxCut on d-regular graphs using infinite graph tensor networks

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm for approximately solving combinatorial optimization problems. We rigorously analyze its performance for the MaxCut problem on large d-regular graphs, extending previous work to significantly greater circuit depths. This analysis is enabled by modeling the problem on an infinite d-regular tree and using an infinite graph tensor network to compute local expectation values of the QAOA wavefunction. We find that at optimal QAOA parameters, the bond dimension required for a given accuracy in our analysis grows slower than in a generic quantum evolution. This observation provides insight into the dynamics of the QAOA.