The QAOA for MaxCut on dense graphs

Which quantum algorithms are definitively better than classical algorithms? One candidate is the Quantum Approximate Optimization Algorithm (QAOA), but its performance is not well-understood except in sparse instances, where quantum interference is limited. Here we make a first step at studying the lowest-depth QAOA for MaxCut on dense graphs. We find an analytic expression for the optimal cut fraction on large D-regular graphs in terms of the number of triangles per edge. When the graph is nearly a clique, the QAOA is close to optimal. We discuss our parameterization and compare with local classical algorithms.