  The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid
quantum-classical variational algorithm designed to tackle combinatorial
optimization problems. Despite its promise for near-term quantum applications,
not much is currently understood about QAOA's performance beyond its
lowest-depth variant. An essential but missing ingredient for understanding and
deploying QAOA is a constructive approach to carry out the outer-loop classical
optimization. We provide an in-depth study of the performance of QAOA on MaxCut
problems by developing an efficient parameter-optimization procedure and
revealing its ability to exploit non-adiabatic operations. Building on observed
patterns in optimal parameters, we propose heuristic strategies for
initializing optimizations to find quasi-optimal $p$-level QAOA parameters in
$O(\text{poly}(p))$ time, whereas the standard strategy of random
initialization requires $2^{O(p)}$ optimization runs to achieve similar
performance. We then benchmark QAOA and compare it with quantum annealing,
especially on difficult instances where adiabatic quantum annealing fails due
to small spectral gaps. The comparison reveals that QAOA can learn via
optimization to utilize non-adiabatic mechanisms to circumvent the challenges
associated with vanishing spectral gaps. Finally, we provide a realistic
resource analysis on the experimental implementation of QAOA. When quantum
fluctuations in measurements are accounted for, we illustrate that optimization
will be important only for problem sizes beyond numerical simulations, but
accessible on near-term devices. We propose a feasible implementation of large
MaxCut problems with a few hundred vertices in a system of 2D neutral atoms,
reaching the regime to challenge the best classical algorithms.
