Adiabatic Quantum Computing

Tameem Albash; Daniel A. Lidar

Source-linked AI summary

Adiabatic Quantum Computing

Tameem Albash, Daniel A. Lidar

arXiv:1611.04471v2Nov 14, 2016quant-ph

TL;DR

The review asks how adiabatic quantum computing works, when it yields quantum speedups, and how it relates to universal quantum computation and complexity theory. It synthesizes adiabatic theorems, explicit algorithms, universality results, and stoquastic obstructions, concluding that AQC has broad theoretical scope but speedups and runtime depend critically on difficult gap analyses and setting-specific limitations.

Problem
The field needs a theoretical account of AQC's principles, algorithmic accomplishments and limitations, and place within computational complexity theory.
Method
The review synthesizes adiabatic-theorem variants, explicit speedup algorithms, universality proofs, Hamiltonian complexity theory, and stoquastic AQC in the closed-system setting.
Results
AQC is universal with non-stoquastic Hamiltonians, while stoquastic AQC has mixed results ranging from classical-equivalent slowdowns to possible scaling advantages and unresolved speedups.
Takeaways & Limitations
Assessing AQC performance requires analyzing minimum spectral gaps and distinguishing proven speedups from weaker comparisons with available or corresponding classical algorithms.
Takeaways & Limitations
The review is restricted to closed-system AQC and excludes open-system experiments, error correction, and several related fields.

Abstract

from arXiv · show

Adiabatic quantum computing (AQC) started as an approach to solving optimization problems, and has evolved into an important universal alternative to the standard circuit model of quantum computing, with deep connections to both classical and quantum complexity theory and condensed matter physics. In this review we give an account of most of the major theoretical developments in the field, while focusing on the closed-system setting. The review is organized around a series of topics that are essential to an understanding of the underlying principles of AQC, its algorithmic accomplishments and limitations, and its scope in the more general setting of computational complexity theory. We present several variants of the adiabatic theorem, the cornerstone of AQC, and we give examples of explicit AQC algorithms that exhibit a quantum speedup. We give an overview of several proofs of the universality of AQC and related Hamiltonian quantum complexity theory. We finally devote considerable space to Stoquastic AQC, the setting of most AQC work to date, where we discuss obstructions to success and their possible resolutions.

I. INTRODUCTION

AQC provides a distinct framework for quantum computation, with universal power in the non-stoquastic setting but difficult-to-establish speedups because performance depends on spectral gaps and theorem assumptions.

Universality: Non-stoquastic AQC is as powerful as the circuit model, with mutual simulation possible using at most polynomial resource overhead.
Definition and scope: AQC uses time-dependent Hamiltonian evolution to connect an easily prepared initial ground state with a computational final ground state.The standard interpolation is H(s)=(1−s)H0+sH1, with the output required to be close to the ground state of H1.
Adiabatic theorem and cost: AQC runtime is governed by the minimum spectral gap: general sufficient bounds scale as 1/∆3, improving to O(1/∆2) up to polylogarithmic factors under stronger smoothness assumptions.The gap is difficult to bound for complicated many-body Hamiltonians, linking AQC performance to condensed-matter phase transitions.
Algorithms and speedups: Explicit speedups include adiabatic Grover search and several circuit-model algorithms, but many proposed algorithms show no speedup or have an unresolved speedup status.The review emphasizes that gap analysis is often highly non-trivial beyond polynomial-time equivalence.
Scope: The review focuses on closed-system AQC and omits open-system experiments, error correction, and several closely related quantum-computing fields.
Stoquastic AQC: Stoquastic AQC presents a mixed picture: it can be more powerful than classical computation, yet many instances fail to outperform classical methods because gaps close rapidly.Schedule optimization, added Hamiltonian terms, and diabatic transitions are discussed as possible ways to avoid small-gap obstructions.

3. Arbitrarily small error

The review develops rigorous and refined views of adiabatic runtime, error, and quantum speedup, while classifying explicit algorithms according to the strength and reliability of their classical comparisons.

3. Arbitrarily small error: Adiabatic error can become exponentially small in runtime under suitable boundary and smoothness conditions, although the associated inverse-gap dependence may remain cubic.
3. Arbitrarily small error: Vanishing derivatives at the interpolation boundaries and boundary symmetry can further suppress adiabatic error, including a quadratic reduction in runtime-dependent error.
Path-based runtime bounds: For a black-box eigenpath, path length supplies a geometric runtime scale, with an estimate tf ∼O(maxs ∥˙H(s)∥/∆2) and a corresponding lower-bound perspective.
Path-based runtime bounds: A digital non-adiabatic method nearly achieves the lower bound with runtime O[(L/∆) log(L/ϵ)], without requiring path continuity or differentiability.
Quantum speedup classification: Quantum speedup classifications distinguish provable, strong, unqualified, and limited speedups according to the classical baseline and the strength of available evidence.A provable speedup rules out any better classical algorithm, whereas a limited speedup compares only corresponding classical implementations.
Quantum speedup classification: The review identifies explicit provable-speedup algorithms including Grover, Deutsch-Jozsa, Bernstein-Vazirani, and glued trees, plus an unqualified PageRank speedup.
Quantum speedup classification: Many adiabatic algorithms have only a scaling advantage over simulated annealing, while some have faster classical algorithms and therefore do not establish a general quantum speedup.
Quantum speedup classification: The adiabatic Grover algorithm finds a marked item in an unsorted database, contrasting classical query complexity that scales linearly in N with a provable quantum advantage.

2. Quadratic quantum speedup

Adiabatic Grover search achieves the expected quadratic speedup through schedules that slow near the minimum gap. The analysis also extends to multiple marked states and highlights limitations of the available error bounds and oracle constructions.

Grover search: The resulting runtime nearly recovers Grover’s quadratic speedup, with tf scaling as the square root of N.The stated condition is sufficient for keeping the adiabatic error small.
Grover search: The logarithmic factor in the sufficient adiabatic bound is attributed to non-tight bounds rather than the underlying algorithmic scaling.The review notes that tighter analyses exist, while the evidence that tf ∼ square root of N suffices for the displayed schedule is numerical.
Grover search: The locally optimized schedule slows near the minimum gap, where the adiabatic evolution is most constrained.Its normalization is chosen so the schedule reaches A(1) = 1.
Grover search: No alternative schedule can improve Grover’s scaling, consistent with Grover optimality in the circuit model and a general Hamiltonian-computation argument.The review states that this argument applies to any Hamiltonian quantum computation.
Multiple marked states: With M marked states, the analysis carries over after replacing 1/N by M/N in the relevant spectral expressions.The Hamiltonian evolves in an M+1 dimensional subspace, with M − 1 eigenvalues equal to 1 − s.
Deutsch–Jozsa algorithm: The unitary-interpolation Deutsch–Jozsa construction preserves a constant gap, yielding an adiabatic runtime O(1) independent of n.The unitary transformation preserves the spectrum of the initial Hamiltonian, so the gap remains ω.

C. Adiabatic Bernstein-Vazirani algorithm

The adiabatic Bernstein–Vazirani algorithm distributes the oracle action across two subsystems so that only one qubit needs to evolve adiabatically. It recovers the circuit-model scaling while encoding the unknown string in the final measurement state.

Performance: This construction achieves the same query scaling as the circuit model, where a is found with O(1) queries versus n classical queries.The comparison establishes a polynomial quantum speedup over the classical query procedure.
Construction: The algorithm encodes the Bernstein–Vazirani oracle in a Hamiltonian acting on an n-qubit subsystem A and a one-qubit subsystem B.For each state in A, subsystem B evolves independently, and its adiabaticity does not depend on A’s size.
Readout: A −1 measurement outcome on subsystem B prepares subsystem A in a product state whose qubits directly encode the bits of a.The process is repeated after a +1 outcome, which reveals no information.
Readout: The failure probability after m repetitions is 2^-m, making the failure exponentially small and independent of n.The two possible subsystem-B outcomes occur with equal probability.
Performance: The algorithm runs in O(1) time and matches the circuit-model depth scaling.Only subsystem B effectively undergoes the adiabatic evolution.

D. The glued trees problem

The glued-trees problem separates classical and quantum query complexity, while an almost-adiabatic algorithm exploits controlled transitions between eigenstates to find the distant root in polynomial time.

Problem: A glued-trees instance consists of two randomly connected binary trees, with the task of finding the right root from the left root using an adjacency oracle.Classical algorithms require a sub-exponential number of oracle calls, whereas a quantum-walk algorithm solves the problem in polynomial time.
Algorithm: The almost-adiabatic algorithm is not adiabatic throughout because it deliberately transitions from the ground state to the first excited state and back.The evolution follows the ground state where the gap is polynomially bounded and transitions in regions where the ground–first-excited gap closes exponentially.
Spectrum: The relevant gaps are bounded by c/n^3 and c′/n^3 outside the exponentially closing regions, with c,c′ > 0.The ground–first-excited and first–second-excited gaps remain polynomially bounded in the central region.
Result: A schedule with adiabaticity requirements based on a 1/n^3 gap yields total evolution scaling as n^6, so the target state can be found in polynomial time.The algorithm uses the spectrum’s symmetry and gap structure to arrange adiabatic and non-adiabatic segments.

3. Speedup

This section reviews adiabatic speedups for PageRank-related tasks and the equivalence between circuit and adiabatic quantum computation, emphasizing both useful speedups and their scope conditions.

PageRank speedups: The combined cost of state preparation and rank estimation is O[n2γi−1polylog(n)] versus O[n polylog(n)] classically, yielding a polynomial speedup whenever γi < 1.The result concerns estimating rank πi with additive error proportional to πi.
PageRank speedups: A PageRank state can support pre- and post-perturbation comparison in O[polylog(n)] preparation time before a quantum SWAP-test estimates their fidelity.The quantum procedure uses O(1) ancilla measurements for fixed precision, compared with O[n^2/3 log n] classical samples from each distribution.
Model equivalence: The circuit and adiabatic models can simulate one another with at most polynomial overhead.Circuit simulation of adiabatic evolution uses products of few-qubit unitaries, while history-state constructions establish the reverse direction.
Model equivalence: Circuit-model simulation of adiabatic evolution decomposes the time-dependent evolution into few-qubit unitaries whose number inherits the adiabatic runtime scaling.A phase-randomization method provides a more efficient alternative based on piecewise application of instantaneous Hamiltonians.

B. AQC can efficiently simulate the circuit model: history state proof

The history-state proof encodes a circuit’s computation into a Hamiltonian whose ground state evolves from an easy initial state to the circuit output, establishing efficient universality of AQC.

Universality: The construction is efficient because the adiabatic runtime scales polynomially with circuit depth, so the final ground state reproduces the circuit output with polynomial overhead.The proof therefore establishes universality of AQC rather than merely encoding a single computation.
History-state construction: The circuit-to-Hamiltonian construction makes the final ground state encode the entire temporal history of a quantum computation.A Feynman clock register records the number of gates applied at each computational time.
Hamiltonian terms: The Hamiltonian terms enforce a legal clock, correct input, and propagation corresponding to each circuit gate.The clock term penalizes illegal configurations, while propagation terms implement forward and backward transitions between consecutive computational steps.
Adiabatic evolution: The initial state is an easily prepared zero-energy ground state, and the interpolation preserves the legal history-state subspace.Within this subspace the ground state is unique throughout the evolution, and its gap has a polynomial lower bound.
Fermionic variant: Fermionic ground-state quantum computation provides an alternative spatial encoding, but its original gap analysis was incomplete.A later nullspace-projection result repaired the missing spectral argument, and the fermionic model was mapped to a two-dimensional space-time circuit Hamiltonian.

D. Space-time Circuit-to-Hamiltonian Construction

The space-time construction maps a universal quantum circuit onto particles moving along connected strings on a rotated grid. A Hamiltonian interpolation preserves the computational structure, maintains an inverse-polynomial gap, and enables efficient circuit simulation, though the initial construction uses four-body interactions.

Space-time mapping: A universal 2n-qubit circuit with n^2 two-qubit gates is represented on a rotated grid whose particle paths encode computational progress.Each particle has an internal two-state degree of freedom, and consistent configurations are connected strings with one occupied edge per horizontal line.
Readout: The construction localizes non-identity gates within a k × k interaction region, and successful readout checks particle positions for the horizontal lines crossing that region.The relevant particles must lie to the right of the interaction region after evolution.
Hamiltonian design: The Hamiltonian terms enforce connected strings, initialize particle states, and implement circuit gates through hopping moves that preserve string connectedness.Hstring penalizes disconnected configurations, while propagation terms move particle pairs across plaquettes and apply the corresponding gate or inverse gate.
Hamiltonian design: The initial Hamiltonian has an easily prepared ground state with all particles on the left boundary and internal states set to zero.The stated ground state is |02n⟩|0n1n⟩ with eigenvalue 1.
Performance: For k = √n/16, the required readout event has probability bounded below by a positive constant, while the interpolation gap remains at least 1/poly(n).These properties give an efficient simulation of the circuit up to polynomial overhead.
One-dimensional universality: Universal AQC can also be realized in one dimension using 9-state particles by distributing the clock and moving blocks of qubits between gate sets.The 1D construction uses a modified circuit and additional particle states to overcome locality and counting constraints.

F. Adiabatic gap amplification

Gap amplification seeks to accelerate adiabatic simulations by enlarging spectral gaps, especially for frustration-free Hamiltonians. The reviewed construction achieves quadratic amplification, but changes ground-state evolution into evolution of a middle-spectrum state and may sacrifice geometric locality.

Motivation: Universal AQC runtimes depend on the inverse minimum spectral gap, motivating general techniques for amplifying that gap.The review frames gap amplification as a way to reduce the runtime of adiabatic circuit simulations.
Amplification construction: For frustration-free Hamiltonians, a new Hamiltonian can preserve the original ground state as an eigenstate while achieving quadratic spectral-gap amplification.Frustration freeness means the ground state minimizes every positive semidefinite term in the Hamiltonian decomposition.
Limitations: The amplification is optimal in a suitable black-box model for frustration-free Hamiltonians, while general amplification is unavailable when frustration freeness is removed.The construction also replaces ground-state evolution with evolution of a state in the middle of the spectrum, so it does not satisfy strict AQC.
Amplification construction: The amplified Hamiltonian has eigenvalues paired as ±λ_j, and evolving under it simulates the original circuit with a quadratic speedup.The construction embeds the original ground-state evolution into a larger Hamiltonian with ancilla registers.
Locality: Unary encoding avoids log2(L)-local interactions but changes geometrically local Hamiltonians into ones with central-spin geometry.The ancilla index is represented in a single-particle unary subspace, while all projectors couple to one register qubit.
Related gap behavior: Some one-dimensional models and cluster-state preparations admit constant-gap schedules through straight-line interpolations that avoid quantum phase transitions.These examples illustrate that gap behavior depends strongly on the Hamiltonian family and interpolation path.

D. QMA-completeness of the k-local Hamiltonian problem and universal AQC

Hamiltonian quantum complexity theory connects universal AQC to QMA-complete local-Hamiltonian problems. Perturbative gadgets reduce locality while preserving low-energy spectra, enabling universality with increasingly restricted interactions and geometries.

QMA-completeness: The k-local Hamiltonian problem is QMA-complete for k ≥ 5, with reductions to 3-local and then 2-local Hamiltonians.The 1-local case is instead in P because each local term can be optimized independently.
One-dimensional complexity: One-dimensional local-Hamiltonian hardness persists with finite-state particles, improving from 12-state to 11-state and then 8-state constructions.The 1D result contrasts with the polynomial-time solvability of 1D MAX-2-SAT with p-state variables.
Locality reduction: Perturbative gadgets approximate a target Hamiltonian using additional ancillas, preserving the lowest 2^n eigenvalues within ε and the corresponding eigenstate overlap at least 1 − ε.The gadget combines an ancilla penalty Hamiltonian with a perturbation coupling ancillas to target qubits.
Connection to universal AQC: Because the reductions preserve the spectrum of the history-state Hamiltonian, the resulting 2-local Hamiltonian retains an inverse-polynomial energy gap relevant to universal AQC.This connects QMA-completeness reductions directly to the efficiency of adiabatic circuit simulation.
Restricted interactions: QMA-completeness extends to real-valued 2-local Hamiltonians built from restricted Pauli-product interaction sets.The review lists geometrically local square- and triangular-lattice versions among the simplifications of the general problem.
Restricted interactions: The ZZXX and ZX interaction families are QMA-complete after perturbative approximations generate the required mixed Pauli terms.The relevant sets are respectively {IX, XI, IZ, ZI, ZZ, XX} and {IX, XI, IZ, ZI, ZX, XZ}.

VI. STOQUASTIC ADIABATIC QUANTUM COMPUTATION

Stoquastic AQC restricts adiabatic computation to fixed-locality Hamiltonians with nonpositive off-diagonal entries in a chosen basis. Its complexity is captured by BStoqP, which lies between classical randomized computation and broader quantum classes, while ground-state and threshold constraints remain important.

Definition: A stoquastic Hamiltonian has real nonpositive off-diagonal matrix elements in the computational basis.The computational basis is used throughout the stoquastic discussion and often serves as the final measurement basis.
Complexity relations: StoqMA is StoqMA-complete for k-local stoquastic Hamiltonians, and the transverse Ising model on degree-3 graphs is also StoqMA-complete.The threshold probabilities in StoqMA have inverse-polynomial rather than constant separation, preventing standard majority-vote amplification.
Model: StoqAQC is AQC restricted to fixed-k local stoquastic Hamiltonians, with computation required to proceed through the ground state.This excludes stoquastic procedures whose algorithms are not subject to the ground-state restriction.
Evaluation problem: The StoqAQCEval promise problem asks whether the final ground-state energy is below a or all eigenvalues exceed b, with b − a > 1/poly(n).The Hamiltonian family is required to maintain a ground-state gap of at least 1/poly(n).
Complexity class: BStoqP is defined as the class of problems polynomial-time reducible to StoqAQCEval.This provides a complexity-theoretic class intended to capture stoquastic adiabatic computation.
Complexity relations: BStoqP is contained in both StoqMA and BQP and includes BPP.The figure summarizes these relations, while the text explains BPP containment through classical reversible circuits and BQP containment through circuit-model simulation.

A. Why it might be easy to simulate stoquastic Hamiltonians

Stoquastic AQC has structural and complexity-theoretic features suggesting classical simulation in important settings, but these do not establish a general absence of quantum speedup. Counterexamples show that classical simulations can still encounter exponential convergence or sampling difficulties, while relaxing ground-state restriction restores universality.

Classical-simulation motivation: Stoquastic Hamiltonians have ground states with only real nonnegative amplitudes, motivating classical simulation approaches without a sign problem.This structural property underlies the question of whether ground-state stoquastic AQC can achieve quantum speedup.
Classical-simulation motivation: For fixed k, stoquastic k-local Hamiltonian is contained in AM, so it is not QMA-complete unless QMA⊆AM.The review presents this as complexity-theoretic evidence for limitations of stoquastic Hamiltonians.
Classical-simulation motivation: Gapped StoqAQC can be simulated in PostBPP, which uses polynomial-time randomized computation with post-selection to sample from stoquastic ground states.This result applies specifically to gapped stoquastic Hamiltonians and does not cover every StoqAQC process.
Obstructions to efficient simulation: No general theorem rules out quantum speedup, and polynomial gaps do not guarantee efficient path-integral Monte Carlo equilibration.Examples include polynomially small gaps with exponential PI-QMC convergence due to topological obstructions, while other constructions create broader discrepancies between Monte Carlo and AQC behavior.
Obstructions to efficient simulation: Polynomial-time stoquastic adiabatic processes can nevertheless be hard for corresponding diffusion Monte Carlo simulations, which may require exponential cost to find the ground state with high probability.The cited constructions exploit differences between L1- and L2-normalized wavefunctions and walker distributions.
Beyond ground-state StoqAQC: Allowing excited-state evolution makes stoquastic computation as powerful as AQC, including a 3-local construction that is QMA-complete and universal.Universality arises because the relevant sector reproduces the spectrum of a universal non-stoquastic Hamiltonian, without requiring that sector to contain the overall ground state.
Scope and caveats: An exponentially small gap does not by itself imply exponentially long runtime, because adiabatic theorems provide upper bounds rather than runtime lower bounds.The inverse gap is often used as a runtime proxy, but equal scaling of inverse gap and runtime is not a general theorem; finite-size numerical extrapolation is also cautioned against.
Scope and caveats: A local-search-designed spike problem yields an exponentially small gap and exponential adiabatic time, showing that some problem structures defeat local quantum exploration.The problem has a narrow global-optimum basin and a broader local-optimum basin, producing the slowdown through the small gap.

1. The role of tunneling

Tunneling can accompany AQC speedups, but it is neither necessary nor sufficient in general, while entanglement and Hamiltonian choices add separate constraints and trade-offs.

The role of tunneling: In the Grover problem, the semiclassical potential develops two degenerate minima at s = 1/2, requiring O(n) spins to tunnel between them.The minimum shifts discontinuously from θ ≈π/2 to θ ≈0 at a first-order quantum phase transition.
The role of tunneling: The semiclassical spin-coherent approach captures features of permutation-symmetric StoqAQC, but its product-state ansatz limits applicability to problems lacking accessible bit symmetry.The approach uses a semiclassical potential derived from spin-coherent states.
The role of tunneling: Tunneling is neither necessary nor sufficient for speedups in permutation-symmetric perturbed Hamming-weight optimization problems.Thus, observing a barrier-crossing mechanism alone does not establish a quantum speedup.
The role of tunneling: Incoherent, thermally assisted tunneling may matter computationally in quantum annealing, but this open-system mechanism lies outside the review’s scope and has not yielded a scaling advantage in cited examples.Its role in those examples is limited to a prefactor.
The role of entanglement: Entanglement can improve ground-state success probability in two-dimensional Ising spin glasses, yet its role in generating AQC speedups remains unresolved.Even small entanglement improved success probability over mean-field models, while higher-dimensional entropy-gap connections remain unclear.
The role of entanglement: Grover’s adiabatic algorithm has entanglement entropy bounded by 1, whereas Exact Cover shows entropy scaling linearly with problem size for n ≤20 despite no known speedup.These contrasting cases do not establish a direct relation between entanglement and speedup.
Hamiltonian choices: With a uniform-superposition projector as the initial Hamiltonian and linear interpolation to a diagonal final Hamiltonian, improvement beyond Grover-like quadratic speedup is impossible.The cited lower bound applies to this restricted algorithmic form.

B. Quantum Adiabatic Brachistochrone

The quantum adiabatic brachistochrone formulates AQC path design as a variational, time-optimal problem, with geometry determined by the Hamiltonian gap. In Grover search, optimized paths reduce error while preserving the known scaling.

Variational formulation: The quantum adiabatic brachistochrone finds the shortest evolution connecting initial and final Hamiltonians while keeping the final state close to the desired ground state.Its objective balances total runtime against final fidelity.
Geometric formulation: The adiabatic-time functional induces a Riemannian metric, so its extrema are geodesics in the control-parameter manifold.The resulting optimal path is obtained from the Euler–Lagrange equations associated with the metric.
Optimization procedure: The optimization procedure first solves the geodesic equation for the path, then computes adiabatic error by evolving the Schrödinger equation along it.Computing the metric requires knowledge of the gap or an estimate of it.
Geometric formulation: The metric and its curvature depend strongly on the spectral gap: smaller gaps produce higher curvature.The stated scaling is Γ ∼ ∆^-1∂∆ and R ∼ ∆^-p−2.
Grover application: The optimal Grover schedule has a differential-geometric origin, and the two-parameter construction generalizes path optimization beyond the standard interpolation.The analysis includes both one-control and two-control Hamiltonian paths.
Grover application: For Grover search, a numerically optimized two-parameter path differs from the Roland–Cerf path, lowers adiabatic error, and has lower curvature.The two-parameter path follows a larger-gap, less-entangled route but cannot improve Grover’s already optimal scaling.

E. Adding a catalyst Hamiltonian

Catalyst Hamiltonians modify intermediate AQC evolution to remove or soften bottlenecks caused by degenerate minima and small gaps. Their effects depend on the catalyst’s stoquastic character and the problem family.

Catalyst construction: A catalyst Hamiltonian vanishes initially and finally, acts only during intermediate evolution, preserves the final interaction graph, and uses no instance-specific information.These conditions define the catalyst construction used in this section.
Removing bottlenecks: Without a catalyst, degenerate minima can force tunneling between potential wells and create an exponentially small gap; with one, a single global minimum can remain trackable in polynomial time.The analytically tractable example contrasts exponential runtime without HC with polynomial runtime with HC.
Numerical evidence: For MAX 2-SAT instances of size n = 20, both stoquastic and non-stoquastic catalysts improved success rates, but their difference was not decisive.The improvements were observed by directly solving the Schrödinger equation over many instances.
Numerical evidence: In fully connected Ising instances with n ≤17, stoquastic catalysts mainly improved easy instances, whereas non-stoquastic catalysts tended to improve very hard instances.The fraction of improved instances increased with size for stoquastic catalysts but remained constant for non-stoquastic ones.
Numerical evidence: Non-stoquastic catalysts did not generically increase the minimum gap, but additional anticrossings could recover population lost from the ground state at earlier anticrossings.This recovery mechanism increased success probability in the reported instances.
Analytical evidence: In infinite-range Ising models, non-stoquastic terms can sometimes change first-order transitions with exponentially small gaps into second-order transitions with polynomially small gaps.The result was obtained for ferromagnetic and random-interaction models using quantum statistical-mechanical analyses.

G. Avoiding perturbative crossings

Perturbative anticrossings can produce exponentially small gaps near the end of AQC, but changes to the Hamiltonian construction can avoid this specific obstruction. A stoquastic ancilla-based method removes perturbative crossings without establishing polynomial-time solutions.

The obstruction: Perturbative anticrossings near the end of evolution can create extremely small minimum gaps and thereby slow adiabatic algorithms.The crossings arise when perturbative expansions from the final Hamiltonian produce nearly crossing energy levels.
The obstruction: For Exact Cover, the Hamming distance between states involved in these crossings can be Θ(n), while the associated gap is exponentially small in that distance.The mechanism was related to Anderson localization, although one related high-probability claim was later rejected after accounting for extreme-value statistics.
Avoiding the obstruction: The perturbative-crossing problem depends on the Hamiltonian implementation: alternative choices can avoid it, and some avoiding choices can be constructed efficiently.This result does not address non-perturbative crossings.
Ancilla construction: The ancilla method changes final-spectrum degeneracies so the ground state is most degenerate and higher-energy states become progressively less degenerate.Its construction assumes no single-bit-flip degeneracies.
Ancilla construction: The added ancilla interactions preserve the original spectrum when ancillas point down and introduce only higher-energy ancilla-flip states, so no new local minima appear.Equivalent 2-local constructions require an additional ancilla for each term.
Result and scope: With a = b = n^2, first-order perturbation theory separates lower-energy states more strongly, allowing the method to remove perturbative crossings.The construction works for arbitrarily connected Ising models with local fields and is fully stoquastic.

H. Evolving non-adiabatically

Rapid, non-adiabatic evolution can redistribute population through avoided-level crossings, sometimes returning amplitude to the ground state. The review frames runtime optimization through repeated short runs and identifies open challenges for AQC.

Diabatic evolution: Rapid evolution can leak population from the ground state into the first excited state before an avoided-level crossing and return it afterward.The cited example shows this behavior near t/T = 0.65 for MAX-2-SAT.
Diabatic evolution: A diabatic cascade can transfer population through higher excited states and return it to the ground state across a series of avoided-level crossings.This phenomenon was observed for a large class of perturbed Hamming Weight problems.
Runtime optimization: Repeated rapid algorithm runs can reduce total time-to-solution even when shorter evolutions have lower single-run success probability.The optimal evolution time minimizes the time-to-solution tradeoff between runtime and repetition count.
Runtime optimization: Benchmarking determines scaling by evaluating optimized time-to-solution across increasing problem sizes.For each instance size n, TTSopt is calculated and its scaling with n is used to characterize the algorithm.
Algorithmic results: Quantum annealing exhibits a scaling advantage over simulated annealing for some oracle optimization problems, despite classical O(1)-time solutions.The cited examples include constant-gap perturbed Hamming Weight and spike problems.
Open challenges: The review identifies unresolved challenges including StoqAQC classical simulability, worst-case speedups for NP-hard optimization, and useful non-oracular speedups.It also notes that some non-stoquastic applications have unknown gap scaling and unknown speedup.
Algorithmic results: The review establishes quadratic quantum speedup for the adiabatic Grover problem and gives examples of constant or polynomially bounded gaps in analyzed constructions.The locally optimized schedule is asymptotically optimal when it is agnostic about the marked state.

Appendix D: Proof of the Amplification Lemma (Claim 1)

The appendix proves amplification using repeated verification and Chernoff bounds, then reviews perturbative gadgets that reproduce k-local Hamiltonians through low-energy effective dynamics. The constructions require convergence conditions and can impose implementation overhead.

Amplification Lemma: Repeating a verifier K = poly(|η|) times and taking a majority vote amplifies completeness and soundness parameters.The proof treats the cases Q(η) = 1 and Q(η) = 0 separately using Chernoff bounds.
Amplification Lemma: Chernoff-bound analysis shows that exponentially small error can be obtained while keeping the repetition count polynomial in |η|.The proof uses an expansion of the Kullback-Leibler divergence and chooses K = ϵ^-2−ε for small ε > 0.
Perturbative Gadgets: The effective Hamiltonian is built from projections and operators such as U and A, with perturbative expansions controlled by the gap γ of H0.The relevant series converges when ∥λV∥ < γ/4, under the stated perturbative conditions.
Perturbative Gadgets: Perturbative gadgets reduce interaction locality by constructing a 2-local Hamiltonian whose low-energy effective Hamiltonian approximates a k-local target Hamiltonian.The construction uses strongly bound ancillas and weaker target-ancilla couplings treated perturbatively.
Perturbative Gadgets: Ancilla operators commute with the gadget Hamiltonian, allowing block diagonalization into sectors labeled by their ±1 eigenvalues.For r terms, the Hamiltonian decomposes into 2^r blocks with the stated block dimensions.
Perturbative Gadgets: At k-th order, cross-terms split the ancilla ground-space degeneracy and reproduce the target Hamiltonian in the effective low-energy theory.The target interaction appears with diminished magnitude of order λ^k/(k − 1)! .
Perturbative Gadgets: The convergence condition can require stronger physical interactions than the effective interaction generated by the gadget.Weaker gadgets avoid this requirement at the cost of more ancillary qubits.