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

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 quasioptimal $p$-level QAOA parameters in $O[\mathrm{poly}(p)]$ time, whereas the standard strategy of random initialization requires $2^{O(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.

Popular 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.

Figure 1

(a) Schematic of a $p$-level quantum approximation optimization algorithm [2]. A quantum circuit takes input $|+{⟩}^{\otimes n}$ and alternately applies $e^{-i{\gamma }_i{H}_C}$ and $X_{{\beta }_i}=e^{-i{\beta }_i{\sigma }^x}$, and the final state is measured to obtain the expectation value with respect to the objective function $H_C$. This result is fed to a (classical) optimizer to find the best parameters $(\overrightarrow{\mathit{\gamma }},\overrightarrow{\mathit{\beta }})$ that maximizes $⟨H_C⟩$. (b) An example of a MaxCut problem on a five-vertex graph, where one seeks an assignment of spin variables on the vertices such that the sum of edge weights between antialigned spins is maximized (black edges).

Figure 2

(a) Optimal QAOA parameters $({\overrightarrow{\mathit{\gamma }}}^{*},{\overrightarrow{\mathit{\beta }}}^{*})$ for an example instance of MaxCut on a 16-vertex unweighted 3-regular (u3R) graph at level $p=7$. (b) The parameter pattern visualized by plotting the optimal parameters of 40 instances of 16-vertex u3R graphs, for $3\le p\le 5$. Each dashed line connects parameters for one particular graph instance. For each instance and each $p$, we use the classical BFGS optimization routine [35] from ${10}^4$ random initial points, and keep the best parameters.

Figure 3

(a) Comparison between our FOURIER heuristic and the RI approach for optimizing the QAOA, on an example instance of a 16-vertex w4R graph. The figure of merit $1-r$, where $r$ is the approximation ratio, is plotted as a function of QAOA level $p$ on a log-linear scale. The RI points are obtained by optimizing from 1000 randomly generated initial parameters, averaged over ten such realizations. (b) The median number of randomly initialized optimization runs needed to obtain an approximation ratio as good as our FOURIER heuristic, for 40 instances of 16-vertex u3R and w3R graphs. A log-linear scale is used, and exponential curves are fitted to the results. Error bars are 5th and 95th percentiles.

Figure 4

Average performance of the QAOA as measured by the fractional error $1-r$, plotted on a log-linear scale. The results are obtained by applying our heuristic optimization strategies FOURIER to up to 100 random instances of (a) u3R graphs and (b) w3R graphs. Differently colored lines correspond to fitted lines to the average for different system size $N$, where the model function is $1-r\propto e^{-p/p_0}$ for unweighted graphs and $1-r\propto e^{-\sqrt{p/p_0}}$ for weighted graphs. The insets show the dependence of the fit parameters $p_0$ on the system size $N$.

Figure 5

(a) ${\mathrm{TTS}}_{\mathrm{QAOA}}^{\mathrm{opt}}$ versus the minimum spectral gap in QA, ${\mathrm{\Delta }}_{\min }$, for many random w3R graph instances. 1000 random instances are generated for each graph vertex size $N$. The maximum cutoff $p$ is taken to be $p_{\max }=50$, 50, 40, 35, 30 for $N=10$, 12, 14, 16, 18, respectively. The dashed line corresponds to the prediction of $\mathrm{T}\mathrm{T}\mathrm{S}\propto 1/{\mathrm{\Delta }}_{\text{min}}^2$ in the adiabatic regime using the Landau-Zener formula [39]. (b) ${\mathrm{TTS}}_{\mathrm{QAOA}}^{\mathrm{opt}}$ versus ${\mathrm{TTS}}_{\mathrm{QA}}^{\mathrm{opt}}$ for each random graph instance. The dashed line indicates when the two are equal. The (Pearson’s) correlation coefficient between the two is $\rho [\ln ({\mathrm{TTS}}_{\mathrm{QAOA}}^{\mathrm{opt}}),\ln ({\mathrm{TTS}}_{\mathrm{QA}}^{\mathrm{opt}})]\approx 0.91$.

Figure 6

(a) A schematic of how the QAOA and the interpolated annealing path can overcome the small minimum gap limitations via diabatic transitions (purple line). A naive adiabatic quantum annealing path leads to excited states passing through the anticrossing point (green line). (b) An instance of a weighted 3-regular graph that has a small minimum spectral gap along the quantum annealing path given by Eq. (9). The optimal MaxCut configuration is shown with two vertex colors, and the black (red) lines are the cut (uncut) edges. (c) Population in low-energy states after the quantum annealing protocol with different total times $T$. The black solid line follows the Landau-Zener formula for the ground state population, $p_{\mathrm{GS}}=1-\exp (-cT{\mathrm{\Delta }}_{\min }^2)$, where $c$ is a fitting parameter. (d) Population in low-energy states using the QAOA at different levels $p$. The FOURIER heuristic strategy is used in the optimization. (e) Interpreting QAOA parameters (at $p=40$) as a smooth quantum annealing path, via linear interpolation according to Eq. (14). The annealing time parameter $s=t/T_p$, where $T_p={\sum }_{i=1}^p(|{\gamma }_i^{*}|+|{\beta }_i^{*}|)$. The red dotted line labels the location of anticrossing where the gap is at its minimum, at which point $f(s)\approx 0.92$. The inset shows the original QAOA optimal parameters ${\gamma }_i^{*}$ and ${\beta }_i^{*}$ for $p=40$. (f) Instantaneous eigenstate population under the annealing path given in (e). Note that the instantaneous ground state and first excited state swap at the anticrossing point.

Figure 7

Full Monte Carlo simulation of the QAOA accounting for measurement projection noise, on the example 14-vertex instance studied in Fig. 6. For various optimization strategies, we keep track of approximation ratio $r_i=|{\mathrm{Cut}}_i|/|\text{MaxCut}|$ from the $i$th measurement and plot minimum fractional error $1-r_i$ found after $M$ measurements, averaged over many Monte Carlo realizations. The blue solid and red dashed lines correspond to QAOA optimized with the FOURIER strategy starting with an educated guess of $(\overrightarrow{\mathit{\gamma }},\overrightarrow{\mathit{\beta }})$ at $p=1$ and $p=5$, respectively. The orange dash-dotted line corresponds to the QAOA optimized starting with random guesses at $p=1$. The three labeled dotted lines are results from QA with total time $T=10$, ${10}^2$, ${10}^3$.

Figure 8

(a) Vertex renumbering to reduce the graph bandwidth. Top: An example of vertex renumbering for a five-vertex graph. Bottom: Distribution of graph bandwidths for 1000 random 3-regular graphs with $N=400$ each. The blue (orange) bars are the bandwidth before (after) vertex renumbering. The inset shows the sparsity pattern of the adjacency matrix before and after vertex renumbering for one particular graph. (b) A protocol to use a Rydberg-blockade controlled gate to implement the interaction term $\exp (-i\gamma {\sigma }_i^z{\sigma }_j^z)$. By choosing a proper gate time for the second step $(t=2\pi /\sqrt{{\mathrm{\Omega }}^2+{\mathrm{\Delta }}^2})$, one does not populate the Rydberg level $|r⟩$. With tunable coupling strength $\mathrm{\Omega }$ and detuning $\mathrm{\Delta }$, one can control the interaction time $\gamma$.

Figure 9

Optimal QAOA parameters $({\overrightarrow{\mathit{\gamma }}}^{*},{\overrightarrow{\mathit{\beta }}}^{*})$ for 40 instances of 16-vertex (a) w3R graphs and (b) weighted complete graphs, for $3\le p\le 5$. Each dashed line connects parameters for one particular graph instance. For each instance and each $p$, the BFGS routine is used to optimize from ${10}^4$ random initial points, and the best parameters are kept as $({\overrightarrow{\mathit{\gamma }}}^{*},{\overrightarrow{\mathit{\beta }}}^{*})$.

Figure 10

Schematics of the two variants of the FOURIER[$q$, $R$] heuristic strategy for optimizing the QAOA, when $R=0$ and $R>0$. Optimized parameters (green) at level $p-1$ are used to generate good initial points (blue) for optimizing at level $p$; the same process is repeated to optimize for level $p+1$. When generating initial points, black dashed arrows indicate appending a higher-frequency component [Eq. (b3)], and pink dashed arrows correspond to adding random perturbations [Eq. (b4)]. In the $R>0$ variant, two local optima (green) are kept in parallel at each level $p$ for generating good initial points: $({\overrightarrow{\mathit{u}}}_{(p)}^L,{\overrightarrow{\mathit{v}}}_{(p)}^L)$ is the same optimum obtained from the FOURIER[$q,0$] strategy, and $({\overrightarrow{\mathit{u}}}_{(p)}^B,{\overrightarrow{\mathit{v}}}_{(p)}^B)$ is the best of $R+2$ local optima, $R$ of which are obtained from perturbed initial points. We find that keeping the $({\overrightarrow{\mathit{u}}}_{(p)}^L,{\overrightarrow{\mathit{v}}}_{(p)}^L)$ optimum improves the stability of the heuristic, as random perturbations can sometimes lead to erratic and nonsmooth optimized parameters.

Figure 11

The fractional error achieved by optimizing using our various heuristics on an example instance of a 14-vertex w3R graph. This instance is the same shown in Fig. 6.

Figure 12

(a) Energy spectrum of low excited states (measured from the ground state energy $E_{\mathrm{GS}}$) along the annealing path for the graph instance given in Fig. 6. Only states that can couple to the ground state are shown, i.e., states that are invariant under the parity operator $\mathcal{P}={\prod }_{i=1}^N{\sigma }_i^x$. The inset shows the energy gap from the ground state in the logarithmic scale. (b) Time to solution for the linear-ramp quantum annealing protocol, ${\mathrm{TTS}}_{\mathrm{QA}}$, for the same graph instance. The TTS in the long time limit follows a line predicted by the Landau-Zener formula, which is independent of the annealing time $T$. (c) The TTS for the QAOA at each iteration depth $p$.

Figure 13

(a) Instantaneous eigenstate populations along the linear-ramp quantum annealing path given by Eq. (9) for the example graph in Fig. 6. The annealing time is chosen to be $T=T^{*}=40$, which corresponds to the time where the diabatic bump occurs in Fig. 6. (b) Coupling between the instantaneous ground states and the first few excited states. The plotted quantities measure the degree of adiabaticity [as explained in Eq. (d5)].

Figure 14

Comparison of three different optimization routines applied to ten instances of 14-vertex w3R graphs. The initial point of optimization is generated with either our heuristics (FOURIER or INTERP) or random initialization (RI). We plot the fractional error $1-r$, averaged over instances, for each optimization routine and each initialization strategy at each $p$. The error bars are sample standard deviations from the ten instances. For our heuristic strategy, the optimization starts with a single initial point generated using our FOURIER[$\infty ,0$] or INTERP heuristics as described in Appendix pp2. For the RI strategy, we generate 50 random initial points uniformly in the parameter space and optimize from each initial point; both the best and the average of 50 RI runs are plotted.

Figure 15

(a) Pattern in the optimal QAOA parameters at level $p=3$ for 20 random instances of the MIS problem. Each dashed line connects parameters for one particular graph instance. (b) The energy difference relative to the ground state in the quantum annealing protocol of Eq. (h6) for an example 32-vertex MIS instance. The annealing protocol progresses as the parameter $\xi$ increases from 0 to 1. The minimum spectral gap between the ground state (GS) and the first excited state (1E) is ${\mathrm{\Delta }}_{\min }=0.0012$ at $\xi =0.6666$. (c) Comparing performance of quantum annealing and the QAOA on the example instance, in terms of the ground state population at the end of the quantum evolution. The equivalent evolution time for the QAOA is calculated via $T_{\mathrm{QAOA}}={\sum }_{i=1}^{p-1}|{\gamma }_i|+{\sum }_{i=1}^p|{\beta }_i|$. (d) The effective annealing schedule converted from optimized 25-level QAOA parameters for the example MIS instance. (e) The population of the system in the instantaneous eigenstates, during the effective annealing schedule that approximates the dynamics under the 25-level QAOA. Here, we observe that the algorithm attempts to transport the system to the fifth excited state, keeping it there before it undergoes a series of anticrossings toward the ground state.