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

Abstract

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 the QAOA’s performance beyond its lowest-depth variant. An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization. We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations. Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimalp-level QAOA parameters inO[poly(p)]time, whereas the standard strategy of random initialization requires2O(p)optimization runs to achieve similar performance. We then benchmark the 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 the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps. Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA. When quantum fluctuations in measurements are accounted for, we illustrate that optimization is 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.

Alternate abstract:

Plain Language Summary

Quantum computers hold the promise to solve computational problems that are beyond the reach of the most powerful classical computers. Recently, hybrid quantum-classical algorithms such as the quantum approximate optimization algorithm (QAOA) have been proposed as promising applications for the near-term quantum computers. Nevertheless, not much is currently understood about their performance or mechanism beyond the simplest cases, as one critical hurdle is to find the optimal adjustable parameters for the algorithms. Here, we provide the first in-depth study of the performance of the QAOA by developing an efficient parameter-optimization procedure. We show that the QAOA can exploit novel mechanisms to speed up computation and provide tools that will guide the implementation of similar algorithms on near-term quantum computers.

Using the observed pattern in typical problems, our parameter-optimization procedure heuristically selects good initial parameters that can be further optimized. This strategy works remarkably well on all problems tested, efficiently finding high-quality parameters that would be intractable for conventional schemes. With these parameters in hand, we then discover that the QAOA can use operations beyond a conventional quantum paradigm to speed up the computation time by many orders of magnitude. Additionally, we propose a feasible implementation for a near-term experiment with hundreds of atoms that will allow the QAOA to challenge the best classical computers.

This work will greatly stimulate and guide the implementation of the QAOA and similar algorithms on near-term quantum-computing devices. Our theoretical insights will likely induce further understanding of these algorithms and increase confidence in their potential to exhibit quantum computational advantages.