MAXCUT QAOA 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 leq 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 leq 2p+1. Under this conjecture, the approximation ratio is at least 0.7924 for all 3 regular graphs and p=3. In addition, using a simple indistinguishability 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.