  The quantum approximate optimization algorithm (QAOA) is a method of
approximately solving combinatorial optimization problems. While QAOA is
developed to solve a broad class of combinatorial optimization problems, it is
not clear which classes of problems are best suited for it. One factor in
demonstrating quantum advantage is the relationship between a problem instance
and the circuit depth required to implement the QAOA method. As errors in NISQ
devices increases exponentially with circuit depth, identifying lower bounds on
circuit depth can provide insights into when quantum advantage could be
feasible. Here, we identify how the structure of problem instances can be used
to identify lower bounds for circuit depth for each iteration of QAOA and
examine the relationship between problem structure and the circuit depth for a
variety of combinatorial optimization problems including MaxCut and MaxIndSet.
Specifically, we show how to derive a graph, $G$, that describes a general
combinatorial optimization problem and show that the depth of circuit is at
least the chromatic index of $G$. By looking at the scaling of circuit depth,
we argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and
Boolean satisifiability problems are suitable for QAOA approaches while
Knapsack and Traveling Sales Person problems are not.
