  The quantum approximate optimization algorithm (QAOA) has rapidly become a
cornerstone of contemporary quantum algorithm development. Despite a growing
range of applications, only a few results have been developed towards
understanding the algorithms ultimate limitations. Here we report that QAOA
exhibits a strong dependence on a problem instances constraint to variable
ratio$-$this problem density places a limiting restriction on the algorithms
capacity to minimize a corresponding objective function (and hence solve
optimization problem instances). Such $reachability~deficits$ persist even in
the absence of barren plateaus [McClean et al., 2018] and are outside of the
recently reported level-1 QAOA limitations [Hastings 2019]. These findings are
among the first to determine strong limitations on variational quantum
approximate optimization.
