PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, Mikhail D. Lukin

arXiv:1812.01041v2quant-phcond-mat.dis-nncond-mat.stat-mech

TL;DR

The paper addresses limited understanding of intermediate-depth QAOA and the difficulty of optimizing its variational parameters. It develops pattern-based heuristics, benchmarks MaxCut performance against quantum annealing, and analyzes near-term implementation resources. The results support polynomial-in-p initialization, non-adiabatic QAOA behavior on small-gap instances, and a proposed few-hundred-atom implementation, while larger-system scaling remains unresolved.

  • Problem

    Intermediate-depth QAOA performance and constructive outer-loop parameter optimization are insufficiently understood, limiting assessment of its near-term usefulness.

  • Method

    The paper searches optimal-parameter patterns, develops heuristic initialization strategies, benchmarks MaxCut QAOA against quantum annealing, and analyzes measurement and hardware resources.

  • Results

    The heuristics find quasi-optimal parameters with O(poly(p)) cost versus 2^O(p) random-initialization runs, while QAOA can learn a diabatic path on hard small-gap instances.

  • Takeaways & Limitations

    QAOA's observed parameter structure and non-adiabatic behavior support practical near-term studies, including a proposed two-dimensional implementation with a few hundred atoms.

  • Takeaways & Limitations

    Whether the observed (stretched)-exponential scaling persists at larger system sizes remains open because simulations reach only N = 22.

Abstract

from arXiv · show

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.

I. INTRODUCTION

QAOA is a hybrid quantum-classical algorithm for combinatorial optimization, but its intermediate-depth performance and parameter optimization remain insufficiently understood. This work studies MaxCut, introducing efficient optimization heuristics, comparing QAOA with quantum annealing, and assessing near-term implementation resources.

  • Algorithmic setting: QAOA alternates quantum state preparation and measurement with classical parameter optimization in a closed loop.A p-level circuit uses 2p variational parameters, whose values are optimized to maximize the measured objective.
  • Open problem: Intermediate-depth QAOA remains poorly understood despite monotonic improvement with depth and success in the p →∞ limit.Assessing depths between p = 1 and infinity is important for evaluating possible quantum advantage.
  • Contributions: The paper develops heuristic parameter-initialization strategies whose optimization cost scales polynomially in p, unlike random initialization requiring 2^O(p) runs.The strategies target quasi-optimal parameters for MaxCut and are based on patterns discovered in optimal QAOA parameters.
  • Contributions: QAOA outperforms adiabatic quantum annealing by multiple orders of magnitude in computation time on instances with very small spectral gaps.The comparison concerns difficult graphs where adiabatic annealing requires very long times because its runtime scales inversely with the square of the gap.
  • Experimental implementation: The resource analysis proposes implementing MaxCut instances with a few hundred vertices using a two-dimensional system of Rydberg-interacting atoms.The proposal is intended to test QAOA against the best classical algorithms for potential quantum advantages.

III. OPTIMIZING VARIATIONAL PARAMETERS

The authors search QAOA's parameter landscape extensively and find smooth, instance-clustered patterns in optimal parameters. These patterns motivate heuristic initialization strategies for efficient optimization.

  • Parameter search: Random-seeded BFGS searches over the parameter space are used to identify local optima across random u3R and w3R graph instances.The study considers graphs with 8 ≤N ≤22 and repeats gradient-based optimization from many seeds.
  • Observed patterns: Optimal γ_i parameters generally increase smoothly with i, while optimal β_i parameters decrease smoothly.The same qualitative pattern appears across multiple instances and depths.
  • Observed patterns: Optimal parameters for graphs from the same class occupy roughly the same value ranges as p varies.Analogous patterns are reported for weighted 3-regular and weighted complete graphs.
  • Interpretation: At fixed finite p, the concentration of relevant subgraph types is expected to make optimal-parameter distributions converge as N grows.The explanation relies on QAOA's objective being a sum of terms associated with subgraphs within distance p of each edge.

B. Heuristic optimization strategy for large p

The paper turns smooth optimal-parameter patterns into interpolation and Fourier-based initialization methods, then evaluates QAOA performance at larger depths. FOURIER enables efficient optimization and reveals exponential or stretched-exponential average error decay, while larger-size scaling remains unresolved.

  • Heuristic strategies: INTERP initializes level p+1 by linearly interpolating optimized parameter curves from level p.It starts at p = 1 and repeatedly optimizes before generating the next-level initial point.
  • Heuristic strategies: FOURIER replaces 2p parameters with 2q frequency amplitudes and reuses optimized amplitudes when increasing the QAOA level.Low-frequency components are motivated by the smoothness of optimal parameters; q ≥p retains full expressivity.
  • Benchmarking: FOURIER matches the best of 1000 random-initialization runs at low p, while average random initialization performs substantially worse.The comparison uses a 16-vertex weighted 4-regular graph and attributes the gap to a highly non-convex parameter landscape.
  • Performance: For unweighted 3-regular graphs, the average fractional error follows 1−r ∝e^−p/p0, whereas weighted graphs follow 1−r ∝e^−√p/p0.Weighted instances show stretched-exponential average behavior, with individual hard instances sometimes exhibiting intermediate plateaus.
  • Scaling caveat: Finite-size simulations cannot determine whether the observed exponential or stretched-exponential scaling persists at larger system sizes.The reported simulations reach N = 22, leaving larger-size behavior unresolved.

V. ADIABATIC MECHANISM, QUANTUM ANNEALING, AND QAOA

The paper compares QAOA with quantum annealing using time-to-solution, focusing on instances where small spectral gaps make adiabatic evolution inefficient. QAOA remains effective on these hard instances, with optimized performance largely independent of the gap and substantially faster than adiabatic quantum annealing.

  • Quantum annealing and time-to-solution: Adiabatic quantum annealing requires runtime scaling as O(1/∆min^2), making instances with extremely small minimum gaps inefficient.Such instances are designated hard instances for adiabatic QA.
  • Quantum annealing and time-to-solution: TTS measures the runtime needed to find the ground state at least once with a target probability, balancing success probability against annealing time.The paper uses a 99% target probability and neglects state-preparation and measurement overheads.
  • Comparison metric: QAOA and QA are compared using optimized time-to-solution metrics, with QAOA parameters interpreted as evolution times under the cost and mixing Hamiltonians.The resulting QAOA metric excludes the overhead of finding optimal variational parameters and is not the actual experimental runtime.
  • Empirical comparison: For graphs with reasonably large gaps, QAOA’s optimal time-to-solution follows the Landau-Zener prediction proportional to 1/∆min^2.This indicates that quasi-adiabatic QAOA parameterizations are effective when the minimum gap is not too small.
  • Empirical comparison: For small-gap graphs, QAOA finds solutions faster than adiabatic QA, while its optimized time-to-solution appears independent of the gap and beats adiabatic QA by many orders of magnitude.Some instances have ∆min as small as 10^-8, implying an adiabatic runtime T ≳ 10^16.
  • Mechanism: The strong correlation between optimized QAOA and QA time-to-solution suggests that QAOA uses an effective annealing schedule, whether slow adiabatic or fast diabatic evolution is preferable.The authors suggest optimized schedules beyond a linear ramp might allow QA to match QAOA.

B. Beyond the adiabatic mechanism: a case study

On a hard MaxCut instance with a very small spectral gap, QAOA can exploit optimized diabatic transitions rather than follow an adiabatic path. Interpreting optimized parameters as an annealing path reveals how excited-state population is transferred to the ground state.

  • Hard instance: Δmin < 10^-3 makes the adiabatic condition require T ≳ 10^6 for the representative 14-vertex instance.The instance exhibits a small minimum spectral gap along the quantum annealing path.
  • QAOA performance: QAOA reaches the diabatic-bump ground-state population at small p and substantially enhances it after p ≳ 24.The FOURIER heuristic is used to optimize QAOA on the hard instance.
  • Annealing-path interpretation: QAOA parameters can be converted into a smooth annealing path by interpreting their sum as the total annealing time and linearly interpolating intermediate times.The conversion is applied to p = 40 optimal parameters to track instantaneous eigenstate populations.
  • Diabatic mechanism: The constructed annealing path accumulates population in the first excited state before the minimum-gap anticrossing, then swaps populations through a diabatic transition.The final population differs slightly from QAOA because of Trotterization and interpolation, while the underlying mechanism remains the same.
  • General interpretation: QAOA can learn a suitable annealing path that may be adiabatic or non-adiabatic, depending on the problem instance.The effective dynamics may involve many excited states in more complex cases, although the heuristic strategies can still find suitable paths.

VI. CONSIDERATIONS FOR EXPERIMENTAL IMPLEMENTATION

Experimental QAOA implementation must balance measurement cost, optimization quality, coherence time, and graph connectivity. Simulations and hardware considerations indicate useful strategies for scaling MaxCut experiments toward hundreds of vertices, while current numerical evidence remains limited to small instances.

  • A. Finite measurement samples: Finite projective-measurement samples create a trade-off between measurement cost and optimization quality.Good optima require higher objective-function precision, which requires more measurements; objective variance also affects measurement demands.
  • A. Finite measurement samples: Random initialization fails to find the MaxCut solution until 10^3–10^4 measurements, whereas FOURIER-based initialization is compared favorably on the representative instance.The simulation starts from p = 1 or p = 5 and increases QAOA depth using FOURIER heuristics.
  • A. Finite measurement samples: QAOA at p = 5 is more advantageous than QA at T = 100 when coherence time is limited.QA at T = 100 appears to perform as well as QAOA on the representative instance, but QAOA is preferred under limited coherence.
  • A. Finite measurement samples: The simulations are limited to small-size instances, where generic QAOA and QA retain small but significant ground-state populations.For larger systems, the authors expect generic ground-state probabilities to become exponentially small while optimization measurements grow polynomially with problem size.
  • 1. Reducing interaction range: Rydberg-blockade controlled gates can implement the QAOA interaction term by tuning coupling strength, detuning, and gate time.The protocol targets stroboscopic implementation for general graphs.
  • 1. Reducing interaction range: Cuthill-McKee renumbering reduces bandwidth to around B ≈ 100 for N = 400 random 3-regular graphs.In 2D, the corresponding interaction diameter is expected to be within reach for near-term quantum devices.

2. Example Implementation with Rydberg Atoms

The proposed neutral-atom implementation uses Rydberg interactions to realize QAOA gates, with parallel collective operations reducing circuit depth. Conservative estimates indicate QAOA at p ≃25 for 400-vertex 3-regular graphs is feasible.

  • Hardware mapping: Neutral atoms encode qubits in hyperfine ground states, while Rydberg excitation induces the interactions needed for QAOA.The implementation uses global driving beams for single-qubit terms and Rydberg-blockade gates for interacting pairs.
  • Parallel operations: Collective Rydberg gates can reduce two-qubit operation steps from the number of edges to the number of vertices.For dense graphs with approximately N^2 edges, this provides a factor-N reduction.
  • Experimental scale: 400-vertex 3-regular graphs require an estimated 10 µm interaction radius in a 2D array, realizable with high Rydberg levels.The estimate assumes an interaction range of five atoms and 2 µm minimum separation.
  • Resource estimates: With Ω∼2π × 10-100 MHz and τ ∼200 µs, the estimated two-qubit gate error is roughly 10^-3-10^-4.These conservative assumptions support QAOA at level p ≃Ωτ/N ∼25 for 400-vertex 3-regular graphs.
  • Outlook: The paper proposes benchmarking few-hundred-atom QAOA against classical and semiclassical solvers on near-term devices.The outlook also connects the methodology to Maximum Independent Set using neutral-atom encodings.

Appendix A: Optimal parameter pattern for weighed graphs

Optimal parameters for weighted graph families exhibit smooth, class-dependent patterns that motivate iterative heuristic initialization. These patterns support INTERP and FOURIER strategies for scaling optimization to higher QAOA levels.

  • Observed patterns: For weighted 3-regular and weighted complete graphs, optimal γ_i parameters tend to decrease smoothly with i.Parameters from graph instances in the same class also cluster within similar ranges.
  • Weighted 3-regular graphs: Weighted 3-regular graphs show a wider spread and larger γ* values than unweighted 3-regular graphs.Random edge weights effectively increase the number of subgraph types and alter the effective mean-field strength.
  • Weighted complete graphs: Weighted complete graphs have narrower and smaller parameter spreads than both unweighted and weighted 3-regular graphs.The common edge environment narrows the distribution, while random weights retain a nonzero spread.
  • Heuristic motivation: Both INTERP and FOURIER exploit smooth deformation of optimal parameters as QAOA depth increases.FOURIER was selected for the main results because random perturbations gave it a slight performance advantage.
  • INTERP strategy: INTERP generates level-p+1 initial points by linearly interpolating optimized level-p parameters.The procedure repeatedly optimizes from p = 1, increases p, and reuses the preceding local optimum.

2. Details of FOURIER[q, R] strategy

FOURIER[q, R] represents QAOA parameters in a frequency-based coordinate system and recursively reuses lower-depth optima. Its frequency truncation and perturbation controls balance compactness with escape from local optima.

  • Parameterization: FOURIER[q, R] uses amplitude parameters (u,v) in R^2q, with q controlling the maximum retained frequency and R controlling random perturbations.The paper’s main results use FOURIER[∞, 10], where q = p and R = 10.
  • Recursive initialization: The strategy starts at p = 1 and reuses each optimized level-p point to generate an initial point for level p + 1.This recursive construction is repeated until the target QAOA depth is reached.
  • Basic variant: FOURIER[∞, 0] adds a zero-amplitude higher-frequency component before optimizing the next QAOA level.The resulting point is refined with a local optimization routine such as BFGS.
  • Perturbed variant: FOURIER[∞, R > 0] adds R perturbed starts because the basic strategy can become trapped in suboptimal local optima.The best among the unperturbed and perturbed local optima is retained.
  • Stability: Keeping the best unperturbed optimum improves stability because perturbations can produce erratic, nonsmooth optimal parameters.The perturbation strength is set to α = 0.6 for the paper’s results.
  • Fixed-frequency variants: Fixed-q variants truncate u and v to their first q frequency components, stopping the addition of higher frequencies once q is reached.This bounds the number of parameters even as QAOA depth increases.

3. Comparison between heuristics

The heuristic comparison shows that perturbation-assisted FOURIER can outperform smoother initialization at higher depth, while QAOA’s time-to-solution must be weighed against optimization overhead and circuit errors.

  • Heuristic comparison: FOURIER[∞, 10] outperforms INTERP and FOURIER[∞, 0] beginning at approximately p ≳20 on the example instance.FOURIER[5,10] uses only 2q = 10 parameters yet closely matches low-p performance and beats the R = 0 heuristic at large p.
  • Parameter dimension: The fixed-q result suggests that optimal QAOA parameters may lie on a small-dimensional manifold.This parameterization could simplify optimization for intermediate-depth QAOA.
  • Quantum annealing: For the difficult graph instance, non-adiabatic quantum annealing with T ≈20 achieves orders-of-magnitude shorter TTS than adiabatic evolution.The energy spectrum includes only states that can couple to the parity-invariant ground state.
  • Practical depth: QAOA’s optimized time-to-solution occurs at p = 49, but p = 4 or p = 5 may be preferable in practice.The practical recommendation reflects optimization overhead and error accumulation at deeper circuit depths.
  • Interpretation: QAOA time-to-solution can show discontinuities because heuristic optimization may miss global optima and energy optimization need not track ground-state population smoothly.The reported jumps therefore reflect both optimization and objective-function effects.

Appendix D: Effective few-level understanding of the diabatic bump

The appendix explains the diabatic bump using instantaneous eigenstate dynamics, showing that a carefully chosen non-adiabatic runtime enables useful population transfer while limiting excessive leakage.

  • Few-level dynamics: The dynamics are expressed in the instantaneous-eigenstate basis, where off-diagonal derivative couplings connect the ground state to excited states.The instantaneous gaps are defined relative to the ground state, and the evolution begins entirely in that state.
  • Adiabatic versus diabatic evolution: The standard adiabatic condition requires a runtime scaling as T = O(1/∆min^2), but very small gaps make this limit impractical.The appendix instead considers runtimes that intentionally break adiabaticity while involving only a few excited states.
  • Mechanism of the diabatic bump: At T = T* = 40, population leaks into the first excited state before the anticrossing, which later becomes the ground state.The same dynamics are reproduced by restricting the simulation to the first few instantaneous basis states.
  • Mechanism of the diabatic bump: The diabatic bump occurs when runtime balances population transfer out of the ground state against suppression of excessive leakage.This balance explains why the bump appears only within a particular runtime range.

Appendix E: Comparing different classical optimization routines

The appendix evaluates three classical optimization routines under a fixed evaluation budget and finds that heuristic initialization is substantially more effective than random initialization across routines.

  • Experimental setup: The experiment compares Bayesian Optimization, Nelder-Mead, and BFGS on 10 weighted 3-regular graph instances, terminating each run after 20p objective evaluations.The comparison uses 14-vertex graphs and examines the effect of initialization strategy.
  • Initialization quality: The average local optimum from 50 random-initialization runs is much worse than the best result, revealing a difficult QAOA parameter landscape.The authors interpret this pattern as evidence of low-quality, non-degenerate local optima.
  • Initialization quality: One heuristic-initialized optimization run is generally better than the best of 50 randomly initialized runs, regardless of the classical routine used.This supports integrating the heuristic strategies with multiple optimization algorithms.
  • Routine dependence: Bayesian Optimization typically performs worse than Nelder-Mead or BFGS at larger p.The observed behavior is consistent with Bayesian Optimization being better suited to lower-dimensional parameter spaces.
  • Noisy objective evaluation: Measurement projection noise is modeled by estimating the objective from finite samples of computational-basis measurement outcomes.The estimate converges to the exact expectation value as the number of measurements approaches infinity.
  • Noisy objective evaluation: The simulations target precision ξ by sampling until the cumulative standard error falls below ξ, while enforcing M ≥ 10 measurements per evaluation.The expected sample requirement scales roughly as M ≈ Var(Fp)/ξ^2.

Appendix G: Techniques to speed up numerical simulation

The appendix describes simulation and implementation techniques for QAOA, quantum annealing, and Maximum Independent Set, including symmetry reduction and efficient operator application.

  • Symmetry reduction: Parity symmetry reduces the simulated Hilbert space from 2^N to 2^(N−1) because the initial state and dynamics remain in the positive-parity sector.The parity operator commutes with both problem and mixer Hamiltonians.
  • Quantum-annealing simulation: Quantum-annealing dynamics are simulated by sequentially applying small time steps without explicitly forming the full evolution operator.The implementation uses scaling and squaring with a truncated Taylor-series approximation.
  • QAOA simulation: For QAOA, diagonal problem evolution and sequential mixer operations are implemented as vector operations, avoiding explicit sparse-matrix formation.Analytical gradients further reduce gradient-computation cost from O(p^2) to O(p).
  • Maximum Independent Set: For MIS, QAOA is formulated over independent-set states and optimized by measuring the system to estimate the objective before classically updating parameters.A large interaction penalty constrains the dynamics to states satisfying n_i n_j = 0 on every graph edge.
  • MIS parameter structure: At p = 3, optimal MIS parameters cluster into two visually distinct groups, with one group resembling a quantum-annealing protocol.The pattern was found through exhaustive searches with randomly initialized optimization.
  • MIS mechanism: The effective p = 25 schedule transports population to the fifth excited state, holds it there, and then uses a sequence of anticrossings to return to the ground state.This behavior combines adiabatic and non-adiabatic operations while navigating a complicated level-crossing structure.
  • MIS performance: For an MIS instance with minimum spectral gap ∆min = 0.0012, QAOA reaches larger ground-state population in much shorter time than the adiabatic scale 1/∆min^2 ≈ 10^6.The effective annealing path is obtained by converting optimized p = 25 QAOA parameters into a smooth schedule.

P (t)/f QAOA

The QAOA-like schedule navigates a complicated level-crossing structure through both diabatic and adiabatic operations, using intermediate excited-state population before returning to the ground state.

  • Effective QAOA dynamics: The system diabatically couples to excited states, lingers to maximize fifth-excited-state population, and then exploits anticrossings to return to the ground state.The mechanism is presented as a learned combination of adiabatic and non-adiabatic operations.
Loading 1812.01041v2…