MaxCut quantum approximate optimization algorithm performance guarantees for p > 1

We obtain worst-case performance guarantees for p = 2 and 3 QAOA for MaxCut on uniform 3-regular graphs. Previous work by Farhi et al. obtained a lower bound on the approximation ratio of 0.692 for p = 1. We find a lower bound of 0.7559 for p = 2, where worst-case graphs are those with no cycles <= 5. This bound holds for any 3-regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all p, where worst-case graphs have with no cycles <= 2p + 1. Under this conjecture, the approximation ratio is at least 0.7924 for all 3-regular graphs and p = 3. In addition, using an indistinguishable argument we find an upper bound on the worst-case approximation ratio for all p, which indicates classes of graphs for which there can be no quantum advantage for at least p < 6.

Automated summary

This research provides worst-case performance guarantees for p = 2 and 3 QAOA on uniform 3-regular graphs for the MaxCut problem. Lower bounds for approximation ratios are determined, and a conjecture for a hierarchy of worst-case graphs based on cycle constraints is proposed. An upper bound on worst-case approximation ratios is also identified, suggesting limitations for quantum advantage in certain graph classes.