PaperlayerView exact revision on arXiv

Source-linked AI summary

Counterdiabaticity and the quantum approximate optimization algorithm

Jonathan Wurtz, Peter J. Love

arXiv:2106.15645v3quant-ph

TL;DR

At finite but large p, the paper asks how QAOA can retain adiabatic performance without the excessive p→∞ limit. It matches QAOA evolution to counterdiabatic schedules, finding polynomial convergence toward an approximation ratio of one and finite-p performance that can exceed finite-time adiabatic-only annealing.

  • Problem

    The p→∞ limit requires very large p, motivating the question of whether QAOA can reproduce or improve on finite-time adiabatic evolution at large but fixed p.

    Source: §1 · p. 2

  • Method

    An analytic procedure matches QAOA step generators to counterdiabatic time evolution, using BCH and Magnus expansions to construct CD-QAOA angles.

    Source: §1 · p. 3, §9 · p. 22

  • Results

    1-C(p) converges to zero at least as p^-μ, while finite-p QAOA can outperform finite-time adiabatic-only annealing.

    Source: §9 · pp. 22–23

  • Takeaways & Limitations

    Counterdiabaticity makes transferring smooth CD-QAOA angles between graphs a natural consequence of the matching procedure.

    Source: §7 · p. 20

    Explaining the subtleties of optimal Ising-chain protocols, including the scaling behavior, is beyond this work's scope.

    Source: §6 · p. 18

Abstract

from arXiv · show

The quantum approximate optimization algorithm (QAOA) is a near-term hybrid algorithm intended to solve combinatorial optimization problems, such as MaxCut. QAOA can be made to mimic an adiabatic schedule, and in the $p\to\infty$ limit the final state is an exact maximal eigenstate in accordance with the adiabatic theorem. In this work, the connection between QAOA and adiabaticity is made explicit by inspecting the regime of $p$ large but finite. By connecting QAOA to counterdiabatic (CD) evolution, we construct CD-QAOA angles which mimic a counterdiabatic schedule by matching Trotter "error" terms to approximate adiabatic gauge potentials which suppress diabatic excitations arising from finite ramp speed. In our construction, these "error" terms are helpful, not detrimental, to QAOA. Using this matching to link QAOA with quantum adiabatic algorithms (QAA), we show that the approximation ratio converges to one at least as $1-C(p)\sim 1/p^{\mu}$. We show that transfer of parameters between graphs, and interpolating angles for $p+1$ given $p$ are both natural byproducts of CD-QAOA matching. Optimization of CD-QAOA angles is equivalent to optimizing a continuous adiabatic schedule. Finally, we show that, using a property of variational adiabatic gauge potentials, QAOA is at least counterdiabatic, not just adiabatic, and has better performance than finite time adiabatic evolution. We demonstrate the method on three examples: a 2 level system, an Ising chain, and the MaxCut problem.

1 Introduction

QAOA approaches adiabatic optimization as p grows, but the infinite-depth limit is excessive for finite resources. This paper uses Trotter terms as counterdiabatic corrections to construct finite-depth angles and connect QAOA with continuous counterdiabatic schedules.

1 Introduction

  • At finite p, angles that are too small cause diabatic excitations, while angles that are too large accumulate Trotter error; matching these effects identifies an optimum.The lowest-order Trotter contribution is proportional to [HT, HS], and its strength depends on the angle magnitudes.Source: §1 · p. 2, Figure 1 · p. 3
  • Matching the second-order BCH term to a low-order adiabatic gauge potential makes the Trotter term a counterdiabatic correction that suppresses excitations.The signs of the second-order BCH term and the variational gauge-potential coefficient allow this matching.Source: §1 · pp. 2–3
  • The analytic procedure maps continuous counterdiabatic evolution to discrete QAOA angles by matching BCH and Magnus generators and variationally minimizing trace error.The procedure is numerically implementable without quantum simulation, using perturbative expansions of order ≲5.Source: §1 · p. 3
  • Kibble-Zurek scaling implies that smooth CD-QAOA approximation ratios approach one at least polynomially in p, though this convergence may be slower than optimal QAOA scaling.For the Ising chain, the cited scalings are 1 − C(p) ∼ p^-1/2 for finite-speed protocols and C(p) = 1 − 1/2p for optimal QAOA angles.Source: §1 · p. 4
  • Matching can run in reverse: optimizing smooth large-p QAOA angles is equivalent to optimizing continuous counterdiabatic protocols, and induced protocols can generate similar-shaped angles at another depth.When graphs have similar low-energy eigenspectra, the induced protocol and angles are expected to transfer with similar performance.Source: §1 · p. 4
  • At equal angle budget, QAOA can outperform finite-time adiabatic evolution because its effective evolution can suppress diabatic excitations or take nonadiabatic paths.The paper also reports that its method finds exact p = 1 angles for a two-level system and angles close to exact for the Ising chain.Source: §1 · pp. 4–5

2 Outline of the paper

The paper introduces adiabatic and counterdiabatic concepts, develops the matching method, and then applies it to a two-level system, an Ising chain, and regular MaxCut graphs.

2 Outline of the paper

  • Section 3 introduces adiabatic protocols, shortcuts to adiabaticity, and the variational adiabatic gauge potential used in matching.Section 4 presents the continuous-to-discrete matching method and its large-p perturbative justification.Source: §2 · p. 5
  • Sections 5–7 demonstrate the method on a two-level system, a one-dimensional Ising chain, and three-regular graphs for MaxCut.The two-level angles are exact up to perturbative error, while the MaxCut example also reverses the procedure to derive approximate counterdiabatic protocols.Source: §2 · p. 5
  • Sections 8–9 discuss the implications of CD-QAOA and future directions.Source: §2 · p. 5

3 Adiabatic protocols and shortcuts to adiabaticity

Adiabatic protocols slowly interpolate between simple and target Hamiltonians, while shortcuts to adiabaticity add controls or counterterms to suppress finite-speed excitations. Local variational adiabatic gauge potentials approximate the counterdiabatic term, with a lowest-order form connected to QAOA’s BCH expansion.

Adiabatic protocols and shortcuts to adiabaticity

  • Adiabatic evolution slowly changes a Hamiltonian to carry an initial eigenstate toward a target, while violating the gap-dependent speed condition produces diabatic excitations.The gap can become small near phase transitions, where such excitations are especially difficult to avoid.Source: §3 · pp. 5–6
  • Shortcuts to adiabaticity seek fast, high-quality preparation by choosing auxiliary fields or adding counterterms that suppress finite-speed diabatic excitations.Path-dependent protocols can select auxiliary-field paths, while counterdiabatic protocols add terms to the Hamiltonian.Source: §3 · p. 6
  • Variational adiabatic gauge potentials use local parameterized ansätze to approximate exact counterterms, which are typically highly nonlocal and exponentially large.For the identity projector, trace minimization can be computed analytically using trace identities rather than Hilbert-space calculations.Source: §3 · p. 6
  • The lowest-order variational gauge potential is proportional to the commutator of the simple and target Hamiltonians, matching the lowest-order BCH term used for a QAOA step.Its coefficient is nonpositive, and the norm depends on Hamiltonian powers up to the sixth, so the approximation captures local structure over a larger neighborhood.Source: §3 · p. 7
  • The expected benefit of a local gauge potential may fail in some cases: optimizing over all eigenstates could overcorrect ground-state evolution, a possibility left uncharacterized.The coefficient remains nonpositive for the ground state, so an infinitesimal coefficient is stated to improve performance.Source: §3 · p. 7

4 Counterdiabatic QAOA

The section maps between smooth discrete QAOA angles and continuous counterdiabatic evolution by matching their effective generators. The matching uses BCH terms to fix angles and annealing times, and it also allows smooth angles to be translated back into continuous schedules.

4 Counterdiabatic QAOA

  • Smooth CD-QAOA angles match each QAOA-step unitary to counterdiabatic evolution; matching the second-order BCH term to the approximate gauge-potential term fixes the angles.The second-order generator matching also sets the time step.Source: §4 · pp. 8–9

4.1 General Counterdiabatic QAOA

  • General matching minimizes the difference between BCH and Magnus generators, and variationally optimizing γq, βq, and τq fixes the angles and total evolution time for a given p.The construction can use higher expansion orders, though low orders are more tractable.Source: §4.1 · pp. 10–11

4.2 Reverse Counterdiabatic QAOA

  • In reverse matching, fixed smooth angles determine optimized step intervals and generally nonlinear counterdiabatic schedules, making angle optimization analogous to schedule optimization.The lowest-order piecewise construction matches a first-order Magnus expansion to a second-order BCH expansion; intermediate-p schedules require subtracting the counterdiabatic contribution when recovering s(t).Source: §4.2 · p. 11

4.3 Conclusion: Counterdiabatic QAOA

  • For large finite p, matching the counterdiabatic Hamiltonian to effective QAOA evolution fixes angles and an analogous annealing time, with the matching enabled by the shared sign of the AGP and second-order BCH terms.In reverse, smooth angles can be used to optimize the protocol fields and total time.Source: §4.3 · pp. 11–12

5 Example 1: 2-level system

For the two-level system, the first-order commutator is the exact adiabatic gauge potential, so counterdiabatic evolution can produce an exact final eigenstate at any speed. Perturbative matching also yields CD-QAOA angles close to exact angles, including at small depth.

5 Example 1: 2-level system

  • The first-order commutator is the exact adiabatic gauge potential for the two-level system, making counterdiabatic evolution exact at any speed.The two-site Ising model with the specified initial state reduces by symmetry to a two-level system.Source: §5 · p. 13
  • p = 1 QAOA is exact: π/4 rotations about the Z and X generators prepare the final eigenstate.The state is first rotated in the XY plane and then in the YZ plane.Source: §5 · p. 13
  • Higher-order BCH and Magnus matching brings γ and β close to π/4, showing that perturbative CD-QAOA matching can find near-exact angles even at small p.For the reported p = 1 linear-schedule calculation, T = 0.9974 and γ = β = 0.2506π.Source: §5 · pp. 13–14
  • For p > 1, repeated X- and Z-axis rotations can track the exact eigenstate, with non-unique protocols corresponding to different choices of adiabatic schedule.The reported generator matching uses fourth-order BCH and third-order Magnus expansions and requires no quantum simulation.Source: §5 · p. 14, Figure 4 · p. 14

6 Example 2: Ising chain

In the transverse Ising chain, finite-depth CD-QAOA approaches its analogous continuous counterdiabatic protocol in the perturbative regime, while finite-speed CD protocols have slower approximation-ratio scaling than the conjectured optimal QAOA bound. The approximate gauge potential is not exact through the chain, so protocol choice affects diabatic excitations.

6 Example 2: Ising chain

  • The chain has a critical point at λ = 1/2, s = 0, and its first-order approximate gauge potential is exact only at the beginning and end of annealing.Different schedules therefore produce final states with different amounts of diabatic excitation, motivating optimization over smooth protocols.Source: §6 · p. 15
  • At large p and small s, CD-QAOA closely follows its analogous continuous counterdiabatic protocol; larger s makes higher-order BCH errors accumulate and the protocols diverge.For p = 1 and s = 0, the induced angles give C1 = 0.7368, close to the optimal value C1 = 0.7500.Source: §6 · p. 16, Figure 5 · p. 17
  • The approximation-ratio prefactor depends on protocol details, including average s and the speed of crossing the phase transition.For an optimal power-law passage through the critical point, the scaling instead includes a logarithmic correction.Source: §6 · p. 16
  • For s ≠ 0, CD protocols approach unit approximation ratio as 1/√p, slower than the conjectured maximum (2p + 1)/(2p + 2), which approaches unity as 1/2p.The paper concludes that optimal Ising-chain protocols are non-adiabatic; smooth protocols instead scale as p^-1/2 or log(p)/p.Source: §6 · p. 16, Figure 5 · p. 17
  • For s = 0, the matched annealing time scales as √p, while for s < 0 it is linear in p; for s > 0, some total times cannot be matched at any p.For s ≠ 0, the time scales as p, with the prefactor depending on the average auxiliary-field strength.Source: §6 · p. 16, Figure 5 · p. 17
  • Smooth adiabatic-like initial angles may provide a warm start, but finding globally optimal fixed-p angles can be difficult because optimal protocols may be non-smooth.The paper notes that non-smooth protocols can be hard to locate in the high-dimensional angle space.Source: §6 · pp. 16, 18

7 Example 3: regular MaxCut graphs

For regular MaxCut graphs, smooth optimized CD-QAOA angles can be mapped to a continuous counterdiabatic schedule and then used to derive angles at other depths. This connects angle optimization to smooth schedule optimization and gives a route to parameter transfer between graphs.

7 Example 3: regular MaxCut graphs

  • The method maps smooth optimized CD-QAOA angles to a continuous protocol and then induces angles for a different p from that same protocol.The pipeline optimizes angles for a graph, infers λ(t) and s(t), and maps the inferred schedule back to QAOA angles.Source: §7 · p. 19, Figure 6 · p. 20
  • Optimizing smooth CD-QAOA angles is equivalent to searching for an optimal smooth continuous protocol (λ, s) under the chosen ansatz.Without a smoothness constraint, optimal protocols are bang-bang.Source: §7 · p. 19
  • The inferred schedule can be biased toward larger average s because fixed p leaves total time dependent on average s, unlike a continuous protocol with fixed T.The authors note that larger total times have fewer excitations under the adiabatic theorem.Source: §7 · p. 19
  • The paper reports p = 12 angles for a 14-vertex 3-regular graph with C12 = 0.99004 and equivalent time T ≈ 9.3.The adiabatic-inspired initial angles were optimized for the specific graph and yielded a smooth angle set.Source: §7 · p. 19
  • Using the variational minimization procedure of Eq. (27), this protocol derives p = 24 angles with approximation ratio C24 = 0.99994 and equivalent adiabatic time T ≈ 15.4.Source: §7 · p. 20
  • Transfer between graphs is expected to work when their low-energy eigenspectra are shared, since their optimal continuous protocols should then be similar.The paper presents direct transfer of smooth angles as a natural consequence of counterdiabaticity.Source: §7 · p. 20

8 QAOA is better than continuous-time adiabatic protocols

With a fixed angle budget T, the paper compares QAOA with finite-time adiabatic and counterdiabatic protocols. Matching the signs of the variational gauge-potential and BCH coefficients lets finite-p QAOA reproduce a counterdiabatic contribution and outperform adiabatic-only evolution.

8 QAOA is better than continuous-time adiabatic protocols

  • For a fixed angle budget T, globally optimal QAOA angles have an approximation ratio at least as high as fixed-budget CD-QAOA angles with variable p.The optimal CD-QAOA protocol can optimize the effective schedule λ(t) and choose p(T); the matching sign implies finite optimal p(T).Source: §8 · p. 21
  • At fixed T, increasing p weakens the effective counterdiabatic term, while sufficiently large p suppresses higher-order BCH errors.The resulting effective Hamiltonian can then approximate the target counterdiabatic Hamiltonian.Source: §8 · p. 21
  • At fixed total time T, optimal QAOA has a better approximation ratio than finite-time adiabatic-only evolution because it can at least reproduce counterdiabatic evolution.The effective counterdiabatic term may be less than optimal, but its sign gives the comparison.Source: §8 · pp. 21–22
  • The second-order BCH term and lowest-order variational gauge-potential coefficient are both negative, enabling finite-p counterdiabatic matching.If the coefficient were positive, the matching procedure would instead favor p approaching infinity to reduce the commutator contribution.Source: §8 · pp. 21–22
  • Smooth CD-QAOA angles can perform well at finite p, but the paper does not establish that smooth angles are always optimal.An optimal protocol may be non-smooth and need not keep intermediate states near an instantaneous ground state.Source: §8 · p. 22

9 Conclusion

The conclusion links QAOA and quantum adiabatic algorithms through the second-order BCH term, which matches a low-order adiabatic gauge potential. The resulting CD-QAOA construction is tractable classically, yields a polynomial convergence bound for smooth angles, and explains parameter-transfer and interpolation behaviors while leaving several questions open.

9 Conclusion

  • The second-order BCH term that determines QAOA’s effective generator matches a low-order adiabatic gauge potential that suppresses diabatic excitations.The sign match implies that for large T a large but finite p(T) can be optimal, and QAOA can include excitation-reducing terms or take nonadiabatic paths.Source: §9 · p. 22
  • The analytic CD-QAOA angle construction is tractable at any system size using classical trace minimization, without quantum simulation.The derivation is perturbatively exact at large p and performs well for small-to-intermediate p ≲10, suggesting direct use or variational warm starts.Source: §9 · p. 22
  • The proposed insights may extend beyond MaxCut to off-diagonal Hamiltonians, but that application is outside this paper’s scope.The authors identify variational quantum eigensolver applications to quantum chemistry as one possible setting.Source: §9 · p. 22
  • The approximation ratio converges to one at least as 1−C(p) ∼ p^-μ for smooth CD-QAOA angles, with μ=1/2 for the transverse Ising model.The exponent is derived from model critical exponents; the reported Ising exponent is slower than the conjectured optimal μ=1, and optimal angles may converge faster.Source: §9 · p. 23
  • Optimized QAOA may require an auxiliary term s(t) to match its effective Hamiltonian, and the paper leaves this issue for further study.The protocol is described as fast and counterdiabatic near its edges, but slow and adiabatic-only near its middle except for a large s term.Source: §9 · p. 23
  • Optimal QAOA angles can be degenerate, so a smooth counterdiabatic set may appear non-smooth after symmetry transformations.The paper leaves open how to distinguish transformed counterdiabatic angles from non-smooth angles that cannot be made smooth in this way.Source: §9 · p. 23
  • Smooth CD-QAOA angles explain observed transfer between similar MaxCut graphs and interpolation from level p−1 to p.The construction also adds a counterdiabatic term to adjust for different annealing times at different p.Source: §9 · p. 23
  • The paper establishes that QAOA can beat finite-time quantum annealing but gives no bound on the improvement.An explicit performance separation under analogous quantum resources remains an open direction.Source: §9 · p. 23

A Appendix: BCH and Magnus Expansion terms

The appendix records BCH and Magnus expansion terms used in the paper’s effective-evolution analysis. It notes the structure of higher-order contributions, including nested commutators from the counterdiabatic term.

A Appendix: BCH and Magnus Expansion terms

  • The BCH expansion is written as a sum of terms Z1, Z2, Z3, Z4, and higher orders.The appendix also mentions constructively finding higher-order terms.Source: A Appendix: BCH and Magnus Expansion… · p. 24
  • The Magnus expansion is written as a sum of terms Ω1, Ω2, Ω3, and higher orders for a smooth protocol expanded around t0.The listed protocol expansion includes λ(t−t0) ≈ λ0 + λ̇t + λ̈t²/2.Source: A Appendix: BCH and Magnus Expansion… · p. 24
  • For smooth α(λ) and schedule λ(t), the text relates α to λ̇τα and defines α as the interval-average coefficient.The second-order term is shown with a commutator [HT, HS] plus higher-order contributions.Source: A Appendix: BCH and Magnus Expansion… · p. 24
  • Higher-order Magnus contributions from the counterdiabatic term include doubly nested commutators, with third-order terms such as [HT, [HT, HS]].The text gives prefactors including λ̇τ^4, λ̈τ^5, and λ̇²τ^5.Source: A Appendix: BCH and Magnus Expansion… · p. 24

B Derivation of Eq. 32

The appendix derives Eq. 32 from the adiabatic gauge-potential and two-site Ising Hamiltonian terms. It evaluates traces in the +1 sector of Z2 symmetry and obtains the expression by dividing numerator by denominator.

B Derivation of Eq. 32

  • The derivation of Eq. 32 uses the adiabatic gauge-potential term defined in Eq. 8 and the two-site Ising Hamiltonian terms defined in Eq. 31.Source: B Derivation of Eq. 32 · pp. 24–25
  • The operators select the +1 sector of Z2 symmetry, where the traces over the subspace and operators equal 4 for both numerator and denominator.Source: B Derivation of Eq. 32 · p. 25
  • Eq. 32 is obtained by dividing the numerator by the denominator, with care required for factors of −1, 2, and i.Source: B Derivation of Eq. 32 · p. 25
Loading 2106.15645v3…