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

By Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, Mikhail D. Lukin. Physical Review X, 2018

1,062 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/1dae572c4606b5d8ea9e1f88c9c16d287851d7a5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size (2019, methodology): “instance average predicted average at n=26 Figure 1: (a) Our upper bounds on V p= min ;V p( ;) as a function of p. These are based on optimizing V p( ;) = lim n!1E J[hC=ni], using heuristics from [10]. The values of V p and the parameters are given in Table1. (b) The expectation value of C=nfor 60 r”
Quantum simulation and computing with Rydberg-interacting qubits (2020, background): “Zhou et al. 267 analyze the performance of QAOA on a closely related weighted MaxCut problems, where the goal is to ﬁnd two subsets of vertices that maximize the total weight of the edges connecting the two subsets (an example of a ﬁve vertex graph is shown in Fig 16c).”
Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe (2022, background): “, quantum algorithms whose gates depend on continuous parameters that then are optimized by an external classical algorithm in order to extremalize the variational cost function [399, 538, 633, 654].”
General parameter-shift rules for quantum gradients (2021, background): “Since then, it has been investigated analytically [60, 61, 62], numerically [63, 64], and on quantum computers [65, 66].”
Parameterized quantum circuits as machine learning models (2019, background): “[111] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin, “Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices,” arXiv preprint”
Variational quantum algorithms (2020, methodology): “Larger p requires improvements in the parametrization and optimization [175].”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, background): “In modern quantum computing research, the design and implementation of quantum approximate optimization algorithms (QAOAs) are of great interest [177], [178].”
Practical quantum advantage in quantum simulation (2022, methodology): “…simulating these models by using the large-scale entangling operations implied by many-body dynamics as a variational circuit that can form the basis for methods such as variational quantum eigensolver 105 , quantum approximate optimization 106 and quantum machine learning 53,69,71–73, 107 , 108 on”