  We consider the maximum cut and maximum independent set problems on random
regular graphs, and calculate the energy densities achieved by QAOA for high
regularities up to $d=100$. Such an analysis is possible because the reverse
causal cones of the operators in the Hamiltonian are 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 regularity increases for the
maximum cut problem. However, QAOA exhibits the opposite behavior for the
maximum independent set problem, i.e. the approximation ratios decrease with
increasing regularity. This phenomenon is explainable by the overlap gap
property for large $d$, 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
derive bounds on the expected approximation ratios.
