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

QAOA’s performance beyond its lowest-depth variant was not well understood, limiting the evidence available to assess it at intermediate depths. The paper develops parameter-initialization heuristics and benchmarks QAOA on MaxCut, reporting average approximation-ratio improvement with increasing depth on random graphs.

  • Problem

    Beyond p = 1, QAOA’s performance was poorly understood, although investigating intermediate depths was considered important for assessing potential quantum advantage.

    Source: §II · p. 3

  • Method

    The authors use patterns in optimal parameters to devise initialization heuristics for QAOA optimization and benchmark performance against quantum annealing on MaxCut.

    Source: §I · p. 2, §VII · p. 12

  • Results

    On random MaxCut graphs, the approximation ratio improved exponentially for unweighted and stretched-exponentially for weighted graphs on average, through p ≤ 50.

    Source: §VII · p. 12

  • Takeaways & Limitations

    The authors conclude that their results suggest promising strategies for QAOA’s practical realization on near-term quantum devices.

    Source: §VII · p. 12

    Whether the observed (stretched) exponential improvement with p persists beyond N = 22 remains open.

    Source: §VII · p. 12

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 · II. QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM

The paper studies QAOA for MaxCut, addressing the challenge of optimizing its variational parameters beyond shallow depth and outlining its performance and near-term implementation. QAOA alternates problem and mixing operations, with measurements and classical optimization used to select its parameters.

I. INTRODUCTION

  • On difficult instances with very small spectral gaps, QAOA outperforms adiabatic quantum annealing by multiple orders of magnitude in computation time.The paper attributes this to QAOA learning via optimization to use diabatic mechanisms to overcome challenges faced by adiabatic annealing.Source: §I · p. 2
  • Observed patterns in optimal parameters support heuristic initialization with polynomial-in-p optimization, versus 2^O(p) runs for random initialization.The strategies are described as quasi-optimal because they usually produce known global optima; a new parametrization may also reduce search-space dimension.Source: §I · pp. 1–2
  • For numerically accessible problem sizes, QAOA can often find the solution in measurement outputs before optimal parameters are found, while optimization is expected to matter more at a few hundred vertices.The proposed near-term implementation uses a 2D system of a few hundred Rydberg-interacting neutral atoms; vertex renumbering can reduce the required interaction range.Source: §I · p. 2

II. QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM

  • A p-level QAOA circuit uses 2p variational parameters, and a classical optimizer searches them to maximize the objective's averaged measurement output.The processor starts in |+⟩⊗N, alternates the problem and mixing Hamiltonians, and estimates the objective through repeated computational-basis measurements.Source: §I · p. 1, §II · p. 3
  • The study focuses on MaxCut, seeking to maximize the weight of edges whose endpoint spins are anti-aligned, on unweighted and randomly weighted d-regular graphs.It benchmarks instances up to N ≤ 22 vertices and p ≤ 50.Source: §I · p. 2, §II · p. 3
  • QAOA has a provable p = 1 approximation guarantee in certain cases, and its performance can only improve with depth, approaching r = 1 as p → ∞.For u3R graphs, the cited p = 1 guarantee is r* ≥ 0.6924; the paper notes that the locality-based bound becomes intractable as p grows.Source: §II · p. 3
  • QAOA performance beyond p = 1 remains poorly understood, and efficient parameter optimization at intermediate depths is an outstanding problem.Shallow depth may limit performance on bounded-degree graphs because the algorithm cannot see the whole graph; examining a parameter grid can require N^O(p) possibilities.Source: §I · p. 1, §II · p. 3

III. OPTIMIZING VARIATIONAL PARAMETERS · A. Patterns in optimal parameters

Optimal QAOA parameters show smooth, depth-ordered patterns across random graph instances, which motivate heuristic initialization strategies intended to find quasi-optimal parameters in O(poly(p)) time. Symmetries reduce parameter degeneracies, and the observed patterns are explained in part by the small set of relevant subgraphs at low depth.

III. OPTIMIZING VARIATIONAL PARAMETERS

  • The parameter patterns motivate heuristic strategies intended to find quasi-optimal p-level QAOA parameters in O(poly(p)) time, rather than relying on random initialization.The discussion focuses mainly on random u3R and w3R instances and reports similar results for u4R, w4R, and randomly weighted complete graphs.Source: §III · p. 4

A. Patterns in optimal parameters

  • Time-reversal symmetry and an additional MaxCut Z2 symmetry create parameter degeneracies that can be removed before searching for optimal parameters.For udR graphs, further redundancy permits restricting γ_i to [−π/2, π/2); β_i can be restricted to [−π/4, π/4) generally.Source: A. Patterns in optimal parameters · p. 4
  • Extensive seeded BFGS searches on random u3R and w3R graphs with 8 ≤ N ≤ 22 found global optima that were non-degenerate after symmetry reductions.For each instance and level, local optimization was repeated from many seeds to identify the global optimum.Source: A. Patterns in optimal parameters · p. 4
  • Across 100 random u3R and w3R graphs with various vertex counts, optimal γ*_i generally increases smoothly and β*_i decreases smoothly with i; similar patterns occur for weighted complete graphs.Similar patterns persist to p ≲ 15 if the number of random seeds is increased accordingly.Source: A. Patterns in optimal parameters · p. 4
  • Optimal parameters have a small spread across instances; at fixed finite p, the relevant-subgraph argument implies their distribution should converge to fixed values as N → ∞.The objective depends on subgraphs within distance p of each edge; as N grows, each relevant subgraph type is expected to appear with a fixed fraction.Source: A. Patterns in optimal parameters · p. 4
  • Even at small depth, the optimal-parameter pattern resembles adiabatic annealing, with HC gradually turned on and HB gradually turned off.The paper notes that QAOA's mechanism goes beyond the adiabatic principle, as discussed later.Source: A. Patterns in optimal parameters · p. 4

B. Heuristic optimization strategy for large p … B. Performance of QAOA on typical instances

The paper develops heuristics that seed QAOA optimization from patterns in parameters at lower levels, then compares their performance with random initialization and studies QAOA error scaling on typical graphs. Average error decreases exponentially with p on unweighted graphs and by a stretched exponential on weighted graphs, with small-gap instances qualifying these trends.

B. Heuristic optimization strategy for large p

  • The INTERP heuristic initializes level p + 1 by linearly interpolating the optimized parameter curve at level p.The heuristics generate starting points for standard classical optimizers; they are not guaranteed to find the global optimum.Source: B. Heuristic optimization strategy for… · p. 5
  • FOURIER reuses optimized low-frequency amplitudes in a discrete sine/cosine parameterization, and can keep the parameter count fixed as circuit depth increases.When q ≥ p, the parameterization can describe all level-p QAOA protocols; smooth optimal parameters motivate using fixed q.Source: B. Heuristic optimization strategy for… · p. 5
  • For MaxCut, the authors favor FOURIER for its slight performance edge, while noting INTERP is simpler and may work better on other problems.Source: B. Heuristic optimization strategy for… · p. 5

A. Comparison between our heuristics and randomly initialized (RI) optimizations

  • For 16-vertex w4R graphs, FOURIER matches the best of 1000 random-initialized runs at low p and outperforms it when p ≥5; matching its performance requires exponentially many random runs.Across 40 instances of 16-vertex u3R and w3R graphs, the median random-run count needed to match FOURIER scales exponentially with p (Fig. 3).Source: Figure 3 · p. 5, A. Comparison between our heuristics… · p. 6

B. Performance of QAOA on typical instances

  • The simulations cover random u3R and w3R graphs with 8 ≤ N ≤22 and QAOA levels p ≤20, but finite-size results do not establish how error scaling changes at larger sizes.The decay constant p0 depends on N, and whether the scaling persists for larger graphs remains unknown.Source: B. Performance of QAOA on typical… · pp. 6–7
  • On the studied u3R instances, QAOA reaches fractional error below approximately 10^-2, consistent with adiabatic preparation when minimum gaps are at least about 0.2.The authors interpret QAOA as Trotterized quantum annealing with smoothly changing parameters; the exponential-error trend breaks down for hard instances with small gaps.Source: B. Performance of QAOA on typical… · pp. 6–7
  • On typical graphs, u3R fractional error decays exponentially with p, while w3R averages follow stretched-exponential decay; hard weighted instances can plateau at intermediate p.The weighted-graph scaling describes the average, while individual instances vary; Fig. 4 presents the fitted trends.Source: B. Performance of QAOA on typical… · pp. 6–7, Figure 4 · p. 6

V. ADIABATIC MECHANISM, QUANTUM ANNEALING, AND QAOA · A. Comparing QAOA with quantum annealing · T >0 TTSQA(T). (11)

On random MaxCut graphs with very small quantum-annealing gaps, optimized QAOA achieves solution-finding times that are nearly gap-independent and beat the adiabatic prediction by many orders of magnitude. The comparison uses time-to-solution metrics, with QAOA’s metric excluding the overhead of finding optimal parameters.

V. ADIABATIC MECHANISM, QUANTUM ANNEALING, AND QAOA

  • QAOA can find MaxCut configurations with high probability as p increases, and the section compares its efficiency with quantum annealing to examine how it overcomes adiabatic limitations.The stated motivation is to assess solution-finding efficiency and explain a mechanism that is not necessarily limited by QA’s minimum gap.Source: §V · p. 7

A. Comparing QAOA with quantum annealing

  • Adiabatic QA relies on remaining in the instantaneous ground state, with success typically requiring T = O(1/∆min^2), making very-small-gap instances hard for adiabatic QA.The final Hamiltonian encodes the MaxCut solution in HC.Source: A. Comparing QAOA with quantum annealing · p. 7

T >0 TTSQA(T). (11)

  • Time-to-solution balances success probability against run time by allowing repeated shorter anneals or a single longer anneal.The QA metric targets a 99% probability of finding the ground state at least once and neglects state-preparation and measurement overheads.Source: A. Comparing QAOA with quantum annealing · p. 7, T >0 TTSQA(T). (11) · p. 7
  • QAOA’s benchmark TTS uses the ground-state population after the optimal p-level protocol and does not include the overhead of finding optimal parameters.Its variational parameters γi and βi are interpreted as evolution times under HC and HB, whose sum defines the total annealing time Tp.Source: T >0 TTSQA(T). (11) · p. 7
  • For gaps as small as 10^-8, adiabatic QA requires T ≳ 10^16, while QAOA’s optimal TTS appears gap-independent and beats the adiabatic TTS by many orders of magnitude.The figure compares optimal QAOA TTS with the minimum QA spectral gap across random w3R graphs; most graphs with gaps ≳ 10^-2 instead follow the Landau–Zener 1/∆min^2 prediction.Source: Figure 5 · p. 8, T >0 TTSQA(T). (11) · p. 8
  • For small-gap graphs, QA’s optimal annealing time is often non-adiabatic, and its optimal TTS is strongly correlated with QAOA’s.The findings suggest QAOA uses the better annealing schedule, whether slow and adiabatic or fast and diabatic; the authors suggest optimized schedules beyond the linear ramp could match QAOA.Source: T >0 TTSQA(T). (11) · p. 8

B. Beyond the adiabatic mechanism: a case study

The case study shows that QAOA can exploit diabatic transitions to overcome the small-gap limitations of adiabatic quantum annealing. Mapping optimized QAOA parameters to an annealing path reveals how population transfer at an anticrossing can produce a large final ground-state population.

B. Beyond the adiabatic mechanism: a case study

  • For N = 14 with ∆min < 10^-3, adiabatic QA requires T ≳1/∆min^2 ≈10^6, while a non-adiabatic ground-state-population bump occurs at T ≈40.The Landau-Zener formula fits the simulated ground-state population.Source: B. Beyond the adiabatic mechanism: a… · p. 8
  • At p ≳24, QAOA substantially enhances ground-state population beyond the diabatic-bump level, after matching that population at small p on an N = 14 instance.The QAOA populations were obtained using the FOURIER heuristic strategy.Source: B. Beyond the adiabatic mechanism: a… · p. 8, Figure 6 · p. 9
  • The p = 40 QAOA parameters define a smooth annealing path whose population moves from the ground state to the first excited state before the anticrossing, then swaps back at the crossing.The constructed path’s final population differs slightly from QAOA because of Trotterization and interpolation, but the underlying diabatic mechanism is the same; other tested path prescriptions show similar qualitative features.Source: B. Beyond the adiabatic mechanism: a… · p. 9
  • For this instance, QAOA dynamics are mostly explained by an effective two-level system, but more complex spectra may involve many excited states; heuristic optimization can still find suitable paths.QAOA’s path may be adiabatic or diabatic depending on the instance.Source: B. Beyond the adiabatic mechanism: a… · p. 10

VI. CONSIDERATIONS FOR EXPERIMENTAL IMPLEMENTATION … 1. Reducing interaction range

The section examines practical constraints on QAOA experiments, including finite measurement precision and the interaction range needed to encode large graphs. It presents QAOA as applicable across experimental platforms and combinatorial problems, using MaxCut as its example [45] [46].

A. Finite measurement samples

  • Finite projection noise creates a trade-off between measurement cost and optimization quality, while higher objective-value variance requires more measurements but may aid near-optimal MaxCut sampling [47].The simulations evaluate the objective by repeated projective measurements until its error falls below a threshold.Source: A. Finite measurement samples · p. 10
  • ∼10–10^2 measurements suffice for QAOA to find the 14-vertex MaxCut solution; starting at p = 5 beats p = 1 and random p = 1 needs 10^3–10^4 measurements.QA with T = 100 performs comparably on this instance, but p = 5 QAOA is more advantageous when coherence time is limited.Source: Figure 7 · p. 10, A. Finite measurement samples · p. 10
  • For larger instances, generic QAOA/QA ground-state probability is expected to be exponentially small, while optimization measurements grow only polynomially with problem size.The small-instance simulations are complicated by non-negligible ground-state population; the authors expect parameter patterns and heuristics to be useful at larger sizes.Source: A. Finite measurement samples · p. 10

VI. CONSIDERATIONS FOR EXPERIMENTAL IMPLEMENTATION

  • QAOA’s hybrid, short- and intermediate-depth circuits suit near-term devices with limited coherence, and the framework applies across experimental platforms, with MaxCut as an example [45] [46].The authors report that QAOA is not generally limited by small spectral gaps.Source: §VI · p. 10, B. Implementation for large problem… · p. 11

B. Implementation for large problem sizes

  • Problems with a few hundred vertices are an interesting quantum-benchmark regime: BiqMac solves MaxCut exactly up to N ≲100 but takes over an hour on larger instances, while breakout local search often finds solutions at a few hundred vertices.The paper also identifies comparison with the Goemans-Williamson approximation guarantee r* ≈ 0.878 as a question for this regime.Source: B. Implementation for large problem… · p. 11

1. Reducing interaction range

  • Cuthill-McKee renumbering reduces bandwidth to around B ≈100 for 400-vertex random 3-regular graphs, mitigating the interaction-range demands of graph embedding.Minimum graph bandwidth is NP-hard; the paper expects a 2D interaction diameter of about 100 for N = 400 3-regular graphs.Source: §1 · p. 11
  • Alternative implementations can encode long-range interactions as local fields at the cost of extra qubits and gauge constraints, or target unit disk graphs that fit 2D geometries and retain NP-hard MaxCut.The bandwidth problem can also be generalized to higher dimensions.Source: §1 · p. 11

2. Example Implementation with Rydberg Atoms · VII. CONCLUSION AND OUTLOOK

The paper reports QAOA benchmark results and outlines a feasible neutral-atom implementation for MaxCut. It also identifies open questions about scaling and the extension of its methods to other optimization problems.

2. Example Implementation with Rydberg Atoms

  • In the neutral-atom implementation, hyperfine ground states encode qubits, a global driving beam implements qubit rotations, and Rydberg-blockade gates stroboscopically realize interaction terms.The |1⟩ state is excited to a Rydberg level to induce interactions; the implementation draws on recently demonstrated high-fidelity entanglement.Source: §2 · p. 12
  • Rydberg-blockade collective gates can run in parallel, reducing two-qubit operation steps from the number of edges to the number of vertices N—an N-fold reduction for dense graphs with ∼N^2 edges.The authors note that interaction falloff may limit the distance between qubits, but vertex renumbering or focusing on unit disk graphs can support interesting MaxCut sizes.Source: §2 · p. 12
  • A 2D neutral-atom array could implement level-p ≃ Ωτ/N ∼25 QAOA for 400-vertex 3-regular graphs, with an estimated two-qubit gate error of roughly 10^-3–10^-4.The estimate assumes an interaction range of 5 atoms in 2D, corresponding to a 10 µm radius at 2 µm minimum separation, and coupling strength Ω∼2π × 10–100 MHz with coherence time τ∼200 µs.Source: §2 · p. 12

VII. CONCLUSION AND OUTLOOK

  • Up to p ≤50, QAOA’s approximation ratio improved exponentially for random unweighted graphs and stretched-exponentially for random weighted graphs, on average.The benchmarks used the proposed heuristic optimization strategies.Source: §VII · p. 12
  • Heuristic initialization based on optimal-parameter patterns finds quasi-optimal p-level parameters in O(poly(p)) time, versus 2^O(p) random-initialization runs for similar performance.The authors note that more sophisticated methods could improve the heuristics’ performance and robustness.Source: §VII · p. 12
  • On hard instances with extremely small spectral gaps, QAOA learned a diabatic path with significantly higher MaxCut success probabilities than adiabatic quantum annealing.A metric combining success probability and runtime suggests QAOA may not be limited by small spectral gaps; this behavior was observed in all examined hard instances, but its scaling to larger problems remains unknown.Source: §VII · p. 12
  • Scaling beyond N = 22 and the extrapolation of QAOA’s advantage on small-gap instances remain open, while machine-learning methods and experiments could test robustness and genuine quantum speedup.The authors describe experimental implementation on near-term devices as a litmus test for speedup on practical problems.Source: §VII · p. 12
  • For Maximum Independent Set, separate work [45] shows a natural encoding in the ground state of Rydberg-interacting neutral atoms, and the MaxCut methodology transfers with similar parameter patterns and non-adiabatic mechanisms.The paper identifies MIS as an NP-hard problem with real-world applications.Source: §VII · p. 12

Appendix A: Optimal parameter pattern for weighed graphs · Appendix B: Details of heuristic optimization strategies · 1. Interpolation-based strategy

Weighted-graph QAOA parameters retain smooth, class-specific patterns, while the appendix details heuristic initializations, including INTERP’s stepwise linear interpolation as the QAOA level increases.

Appendix A: Optimal parameter pattern for weighed graphs

  • For weighted 3-regular graphs, optimal γ_i values tend to increase smoothly and β_i values to decrease smoothly with i, and same-class instances cluster in similar ranges.The pattern is shown across 40 instances and resembles that for unweighted 3-regular graphs.Source: Appendix A · p. 16, Figure 9 · p. 16
  • Weighted 3-regular graphs have a wider spread and larger γ values than unweighted 3-regular graphs, attributed to more subgraph types and stronger effective mean-field strength.Source: Appendix A · p. 16
  • Weighted complete graphs have narrower, smaller γ spreads than 3-regular graphs; the spread comes from random edge weights and is expected to vanish as N increases.The smaller γ values are attributed to each qubit interacting with all N −1 other qubits; every edge sees one subgraph type.Source: Appendix A · p. 16

Appendix B: Details of heuristic optimization strategies

  • INTERP and FOURIER both work well on the examined instances, but FOURIER was used for main-text results because it had a slight edge with random perturbations.Source: Appendix B · p. 16

1. Interpolation-based strategy

  • INTERP uses linear interpolation to initialize level p + 1 from the level-p optimum, based on the close resemblance between successive optimal-parameter shapes.Source: §1 · p. 16
  • INTERP starts at p = 1, optimizes to a local optimum, interpolates the γ and β vectors to seed the next level, and repeats until reaching the target level.Source: §1 · pp. 16–17

2. Details of FOURIER[q, R] strategy

FOURIER[q, R] optimizes QAOA by representing its parameters in frequency space and carrying optimized parameters from depth p forward to depth p + 1. Its variants limit the frequency components and use random perturbations to improve the chance of escaping local optima.

2. Details of FOURIER[q, R] strategy

  • FOURIER reuses a depth-p optimum in the (u,v) representation to initialize depth p + 1, adding a higher-frequency component with zero amplitude in the basic variant.The R > 0 variant also optimizes from perturbed initial points.Source: §2 · p. 17, Figure 10 · p. 17
  • q sets the maximum frequency: q = p uses the full p-level QAOA parameterization, while fixed q truncates components and bounds the number of parameters as depth grows.The paper uses FOURIER[∞, 10] for its main-text results unless otherwise stated.Source: §2 · pp. 17–18
  • R controls random perturbations: the improved strategy optimizes from R + 1 additional starts, perturbing the best depth-p optimum to seek better local optima.The perturbation strength α is set to 0.6 for the paper's results.Source: §2 · pp. 17–18
  • Keeping the basic strategy's local optimum alongside the best perturbed optimum improves stability because perturbations can produce erratic, non-smooth parameters.The figure depicts these optima being carried forward to generate initial points at the next depth.Source: §2 · p. 17, Figure 10 · p. 17
  • The authors perturb FOURIER rather than INTERP because correlated changes in (γ,β) through (u,v)-space may help escape local optima, whereas perturbing INTERP works less well.They attribute this difference to the smoothness of the optimal parameters.Source: §2 · p. 18

3. Comparison between heuristics · Appendix C: Time-to-solution (TTS) for example graph instance

On the example graph, non-adiabatic quantum annealing achieves orders-of-magnitude shorter time-to-solution than adiabatic evolution, while QAOA heuristics show differing performance and depth tradeoffs. The appendix explains QAOA time-to-solution behavior and the parity restriction used in the annealing spectrum.

3. Comparison between heuristics

  • FOURIER[∞, 10] outperforms INTERP and FOURIER[∞, 0] from about p = 20, while INTERP and FOURIER[∞, 0] perform essentially identically.The comparison is for the 14-vertex w3R example graph.Source: §3 · p. 18, Figure 11 · p. 18
  • With only 2q = 10 parameters, FOURIER[5,10] closely matches other heuristics at low p and beats R = 0 at large p, suggesting a small-dimensional manifold of optimal parameters.The (u,v) parameterization may simplify intermediate-p optimization.Source: §3 · p. 18, Figure 11 · p. 18

Appendix C: Time-to-solution (TTS) for example graph instance

  • The annealing spectrum shows only parity-invariant eigenstates because the annealing Hamiltonian commutes with parity and the initial state is parity-invariant.The spectrum is for the graph instance used in the TTS comparison.Source: Appendix C · p. 18, Figure 12 · p. 19
  • On the example graph, non-adiabatic quantum annealing at T ≈ 20 yields orders-of-magnitude shorter time-to-solution than adiabatic evolution, whose long-time TTS is independent of T.The long-time behavior follows the Landau-Zener formula.Source: Appendix C · p. 18, Figure 12 · p. 19
  • QAOA’s optimal TTS occurs at p = 49, but p = 4 or 5 may be preferable in practice because deeper circuits add optimization overhead and error accumulation.The TTS curve uses the FOURIER[∞, 10] heuristic and is computed through pmax = 50.Source: Appendix C · p. 18, Figure 12 · p. 19
  • Discontinuous jumps in QAOA ground-state population can arise from heuristic trapping and escape, or because QAOA optimizes energy rather than ground-state population.Random perturbations may help escape a local optimum; jumps can occur even when the global optimum is found at every depth.Source: Appendix C · p. 18, Figure 12 · p. 19

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

The diabatic bump can be understood through dynamics involving only a few instantaneous eigenstates. At T = T* = 40, population leakage before an anticrossing enables transfer to the state that becomes the ground state, while excessive leakage is suppressed.

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

  • In the instantaneous-eigenstate basis, the evolution couples states through energy gaps and time-dependent eigenstate derivatives, starting from the ground state.The ground-state energy is set to zero, with initial coefficients a0 = 1 and ai = 0 for i ≠ 0.Source: Appendix D · p. 19
  • At T = T* = 40, population leaks from the ground state to the first excited state before the anticrossing, which becomes the ground state afterward.This run time balances allowing leakage out of the ground state against suppressing excessive leakage, explaining why the bump occurs over a particular time-scale range.Source: Figure 13 · p. 19, Appendix D · p. 20
  • When small minimum gaps make the adiabatic time T = O(1/∆2_min) impractical, an appropriate nonadiabatic run time can restrict dynamics to a few excited states.In this regime, the evolution can be understood by truncating the instantaneous-eigenstate dynamics to the first few basis states.Source: Appendix D · pp. 19–20

Appendix E: Comparing different classical optimization routines · Appendix F: Details of Simulation with Measurement Projection Noise

Heuristic initialization outperformed repeated random starts across classical optimizers, while measurement-noise simulations specified how finite-shot objective estimates and optimization settings were handled.

Appendix E: Comparing different classical optimization routines

  • The optimizer comparison used 10 weighted 3-regular graphs with 14 vertices and a budget of 20p objective evaluations per run, including BFGS gradient-estimation costs.Runs incremented p from 1 and used heuristic or random initial points.Source: Appendix E · p. 20
  • One heuristic-initialized run generally outperformed the best of 50 random-initialized runs, regardless of the classical optimizer.The comparison used FOURIER and INTERP heuristic strategies versus random initialization.Source: Appendix E · pp. 20–21
  • For larger p, Bayesian Optimization typically underperformed Nelder-Mead and BFGS, whose observed performance was comparable but not conclusively different.The authors attribute the slight difference between Nelder-Mead and BFGS to potentially suboptimal tolerances and step sizes under the limited evaluation budget.Source: Appendix E · p. 21

Appendix F: Details of Simulation with Measurement Projection Noise

  • Measurement-noise simulations estimated the objective by averaging M measurement outcomes and sampling until the standard error fell below precision target ξ, with M ≥ 10.The expected sample count was approximately Var(Fp)/ξ^2.Source: Appendix F · p. 21
  • The simulations stopped when the objective change was at most ϵ or the parameter-step norm was at most δ; BFGS used δ for finite-difference gradient estimates.BFGS was implemented as MATLAB R2017b fminunc.Source: Appendix F · p. 21
  • For the Fig. 7 representative instance, simulations used ϵ = 0.1, ξ = 0.05, and δ = 0.01, starting at p = 1 or p = 5 and increasing levels with FOURIER[∞, 0].Initial points were random at p = 1 or educated guesses based on optimal parameters from small instances at p = 1 and p = 5.Source: Appendix F · p. 21
  • Each simulated run tracked the largest cut found after each measurement, and 500 runs with different pseudorandom seeds were averaged.The averaged histories were used for the simulated experiments.Source: Appendix F · p. 21

Appendix G: Techniques to speed up numerical simulation · Appendix H: QAOA for Maximum Independent Set

Appendix G describes simulation and optimization techniques that reduce computational costs, while Appendix H applies QAOA to Maximum Independent Set and examines its performance and mechanism on a difficult instance.

Appendix G: Techniques to speed up numerical simulation

  • Parity symmetry confines QAOA and quantum annealing dynamics to the positive sector, reducing the simulated Hilbert space from 2^N to 2^(N−1).The initial state has positive parity, and the parity operator commutes with both the cost and mixer Hamiltonians.Source: Appendix G · pp. 21–22
  • Quantum annealing simulation advances in small time steps using state evolution without forming the full evolution operator; the authors used scaling and squaring with a truncated Taylor approximation.They report this ran slightly faster than the Krylov subspace method for small time steps.Source: Appendix G · p. 22
  • For QAOA, diagonal cost evolution and sequential mixer vector operations avoid explicitly forming the mixer matrix, improving simulation speed and saving memory.The authors work in the standard σz basis.Source: Appendix G · p. 22
  • Analytic gradients using GRAPE-like techniques reduce gradient-computation cost from O(p^2) to O(p) for p-level QAOA.For the FOURIER strategy, gradients with respect to its new parameters are related to the original-parameter gradients through the parameter transformation matrices.Source: Appendix G · p. 22

Appendix H: QAOA for Maximum Independent Set

  • MIS QAOA prepares a variational state, estimates its objective by repeated computational-basis measurements, and uses classical search to maximize that estimate.The MIS objective is defined over independent sets, and the appendix describes implementation through appropriate waveforms in the constrained neutral-atom regime.Source: Appendix H · p. 22
  • For 20 random MIS instances, optimal p = 3 parameters clustered in two groups, with one group's smooth curve resembling a quantum-annealing protocol.For the example instance, the effective schedule from optimized 25-level QAOA transports population to the fifth excited state before a series of anticrossings toward the ground state.Source: Appendix H · p. 22, Figure 15 · p. 23
  • For an MIS instance with Δmin = 0.0012, QAOA achieved a much larger ground-state population in much shorter time than the adiabatic timescale of about 10^6.The comparison uses the adiabatic timescale 1/Δmin^2; the instance is difficult for adiabatic quantum annealing because of its small spectral gap.Source: Figure 15 · p. 23, Appendix H · p. 23

P (t)/f QAOA

QAOA navigates a complicated level-crossing structure through both adiabatic and non-adiabatic operations, and these mechanisms can extend beyond MaxCut to difficult MIS instances.

P (t)/f QAOA

  • QAOA navigates a complicated level-crossing structure through a combination of adiabatic and non-adiabatic operations.The population analysis shows that the algorithm learns this behavior during evolution.Source: P (t)/f QAOA · p. 23
  • The system diabatically couples to excited states, lingers to maximize population in the fifth excited state, then uses anticrossings to return to the ground state.Source: P (t)/f QAOA · p. 23
  • The non-adiabatic mechanisms observed in QAOA for MaxCut can play a significant role in difficult MIS instances.Source: P (t)/f QAOA · p. 23

Related papers

Loading 1812.01041v2…