Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm

We consider the maximum cut and maximum independent set problems on random regular graphs in the infinite-size limit, and calculate the energy densities achieved by QAOA for high degrees up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mn>100</mml:mn> </mml:math> . Such an analysis is possible because the reverse causal cones of the operators in the Hamiltonian are with high probability associated with tree subgraphs, for which efficient classical contraction schemes can be developed. We combine the QAOA analysis with state-of-the-art upper bounds on optimality for both problems. This yields novel and better bounds on the approximation ratios achieved by QAOA for large problem sizes. We show that the approximation ratios achieved by QAOA improve as the graph degree increases for the maximum cut problem. However, QAOA exhibits the opposite behavior for the maximum independent set problem, i.e. the achieved approximation ratios decrease when the degree of the problem is increased. This phenomenon is explainable by the overlap gap property for large <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>d</mml:mi> </mml:math> , which restricts local algorithms (like QAOA) from reaching near-optimal solutions with high probability. In addition, we use the QAOA parameters determined on the tree subgraphs for small graph instances, and in that way outperform classical algorithms like Goemans-Williamson for the maximum cut problem and minimal greedy for the maximum independent set problem. In this way we circumvent the parameter optimization problem and are able to compute the expected approximation ratios.