Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm designed to tackle combinatorial optimization problems. Despite its promise for near-term quantum applications, not much is currently understood about its performance beyond its lowest-depth variant. An essential but missing ingredient for understanding and deploying QAOA is a constructive approach for the outer-loop classical optimization. We give an in-depth study of QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit non-adiabatic operations. 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 to use non-adiabatic mechanisms to circumvent challenges associated with vanishing spectral gaps. Finally, we provide a realistic resource analysis on the experimental implementation of QAOA. When we account for quantum projection noise, optimization will be important only for system sizes beyond numerical simulations, but accessible on near-term devices. We also propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms.