  Despite much recent work, the true promise and limitations of the Quantum
Alternating Operator Ansatz (QAOA) are unclear. A critical question regarding
QAOA is to what extent its performance scales with the input size of the
problem instance, in particular the necessary growth in the number of QAOA
rounds to reach a high approximation ratio. We present numerical evidence for
an exponential speed-up of QAOA over Grover-style unstructured search in
finding approximate solutions to constrained optimization problems. Our result
provides a strong hint that QAOA is able to exploit the structure of an
optimization problem and thus overcome the lower bound for unstructured search.
  To this end, we conduct a comprehensive numerical study on several
Hamming-weight constrained optimization problems for which we include
combinations of all standardly studied mixer and phase separator Hamiltonians
(Ring mixer, Clique mixer, Objective Value phase separator) as well as quantum
minimum-finding inspired Hamiltonians (Grover mixer, Threshold-based phase
separator). We identify Clique-Objective-QAOA with an exponential speed-up over
Grover-Threshold-QAOA and tie the latter's scaling to that of unstructured
search, with all other QAOA combinations coming in at a distant third. Our
result suggests that maximizing QAOA performance requires a judicious choice of
mixer and phase separator, and should trigger further research into other QAOA
variations.
