  The $p$-stage Quantum Approximate Optimization Algorithm (QAOA$_p$) is a
promising approach for combinatorial optimization on noisy intermediate-scale
quantum (NISQ) devices, but its theoretical behavior is not well understood
beyond $p=1$. We analyze QAOA$_2$ for the maximum cut problem (MAX-CUT),
deriving a graph-size-independent expression for the expected cut fraction on
any $D$-regular graph of girth $> 5$ (i.e. without triangles, squares, or
pentagons).
  We show that for all degrees $D \ge 2$ and every $D$-regular graph $G$ of
girth $> 5$, QAOA$_2$ has a larger expected cut fraction than QAOA$_1$ on $G$.
However, we also show that there exists a $2$-local randomized classical
algorithm $A$ such that $A$ has a larger expected cut fraction than QAOA$_2$ on
all $G$. This supports our conjecture that for every constant $p$, there exists
a local classical MAX-CUT algorithm that performs as well as QAOA$_p$ on all
graphs.
