  The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth
quantum circuit to produce a parameter dependent state. For a given
combinatorial optimization problem instance, the quantum expectation of the
associated cost function is the parameter dependent objective function of the
QAOA. We demonstrate that if the parameters are fixed and the instance comes
from a reasonable distribution then the objective function value is
concentrated in the sense that typical instances have (nearly) the same value
of the objective function. This applies not just for optimal parameters as the
whole landscape is instance independent. We can prove this is true for low
depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our
results generalize beyond this example. We support the arguments with numerical
examples that show remarkable concentration. For higher depth circuits the
numerics also show concentration and we argue for this using the Law of Large
Numbers. We also observe by simulation that if we find parameters which result
in good performance at say 10 bits these same parameters result in good
performance at say 24 bits. These findings suggest ways to run the QAOA that
reduce or eliminate the use of the outer loop optimization and may allow us to
find good solutions with fewer calls to the quantum computer.
