Adiabatic Quantum Computing

I. INTRODUCTION

• AQC interpolates between initial and final Hamiltonians so the evolving ground state encodes a solution, while non-stoquastic AQC is equivalent to circuit-model quantum computation with polynomial overhead.Optimization-oriented stoquastic AQC is a restricted setting, whereas the review uses AQC primarily in the general non-stoquastic sense.Source: §I · pp. 2–3
• Runtime depends on the minimum spectral gap: generic schedules require at worst 1/∆^3, smoother schedules can achieve O(1/∆^2) up to polylogarithmic factors, and gap estimation is difficult for many-body systems.Known cases include an adiabatic Grover process with quadratic speedup, but optimization speedups remain largely unresolved; small gaps can reflect quantum phase transitions.Source: §I · p. 4
• The review focuses on closed-system AQC, organizing adiabatic theorems, explicit speedups, universality, Hamiltonian complexity, stoquastic limitations, and gap-avoidance strategies.It excludes experimental open-system AQC, error correction and suppression, holonomic and topological computing, and adiabatic state preparation for quantum simulation.Source: §I · pp. 4–5

II. ADIABATIC THEOREMS

• The adiabatic theorem provides sufficient runtime conditions for tracking an instantaneous eigenstate, but its variants differ in smoothness assumptions, gap dependence, and fidelity guarantees.It supplies an upper bound rather than an exact runtime, and rigorous formulations quantify distance between actual and ideal evolutions under stated assumptions.Source: §II · p. 6, B. Rigorous versions · pp. 6–7

A. Approximate versions

• Approximate adiabatic criteria can fail when independent oscillatory timescales are present, so rigorous analysis assumes a dimensionless, tf-independent Hamiltonian path such as H(s)=A(s)H0+B(s)H1.For driven two-level systems, resonance can produce Rabi oscillations even when the usual adiabatic criterion is satisfied.Source: A. Approximate versions · p. 6

B. Rigorous versions

• Rigorous adiabatic theorems generally impose more severe gap conditions involving norms of Hamiltonian derivatives; the Jansen–Ruskai–Seiler framework establishes inverse-cubic gap dependence for generic twice-differentiable paths with a nonvanishing spectral separation.These results assume bounded operators and a spectral band separated from the remainder by ∆>0, while weaker gap-free forms provide only o(1) error as tf→∞.Source: B. Rigorous versions · p. 6, §1 · p. 7

1. Inverse cubic gap dependence with generic H(s)

• For generic H(s), the adiabatic condition uses norms of the first or second time derivative of H(s), rather than the traditional matrix element.Source: §1 · p. 7

2. Rigorous inverse gap squared

• Elgart and Hagedorn’s theorem achieves inverse gap-squared runtime scaling up to logarithmic correction when bounded H(s) belongs to a sufficiently regular Gevrey class.The assumptions constrain all higher derivatives, and the resulting projector error is o(1) throughout the evolution.Source: §2 · pp. 7–8
• The inverse-square dependence is essentially tight because Hamiltonians exist with a lower bound tf = O(∆−2/| ln ∆|), although the theorem’s error bound is not tight.Source: §2 · p. 8

3. Arbitrarily small error

• Gevrey smoothness with vanishing boundary derivatives yields adiabatic error exponentially small in tf, with cubic inverse-gap dependence (Ge et al., 2015).Final-time adiabatic bounds can be tighter than instantaneous bounds; related analytic constructions make error arbitrarily small as more boundary derivatives vanish.Source: §3 · p. 8
• A boundary-symmetry interference effect can further reduce adiabatic error quadratically in tf, while Landau–Zener scaling combines exponential error with inverse-gap-square dependence only for two-level systems.The Landau–Zener result is O(e−C∆2tf ) and is restricted to two-level systems.Source: §3 · p. 8

4. Lower bound

• In the black-box model, preparing the final eigenstate with bounded precision requires a time lower bound governed by the eigenpath length L.Bounding L by maxs ∥˙H(s)∥/∆ gives tf ∼O(maxs ∥˙H(s)∥/∆2), and a nearly achievable digital method scales as O[(L/∆) log(L/ϵ)].Source: §4 · pp. 8–9

III. ALGORITHMS

• The review classifies speedups as provable, strong, unqualified, or limited, and surveys adiabatic algorithms with provable speedups including Grover, Deutsch–Jozsa, Bernstein–Vazirani, and glued trees.Other algorithms show scaling advantages over simulated annealing in some cases, while faster classical algorithms exist in others.Source: §III · p. 9

A. Adiabatic Grover

• Adiabatic Grover search finds a marked item in an unsorted database through oracle queries, whereas classical strategies require an average number of queries scaling linearly in N.The oracle is treated as a black box, allowing complexity to be measured by query count.Source: A. Adiabatic Grover · p. 9

1. Setup for the adiabatic quantum Grover algorithm

• The Grover construction interpolates between a uniform-superposition initial Hamiltonian and a marked-state final Hamiltonian, with dynamics confined to a two-dimensional subspace.The marked state is the final Hamiltonian’s ground state, while the remaining N−2 states retain eigenvalue 1.Source: A. Adiabatic Grover · p. 10, §1 · p. 10
• For a linear schedule, the minimum gap occurs at s = 1/2 and becomes exponentially small with n, making a globally imposed adiabatic condition appear classically slow.The relevant gap-dependent quantity approaches N = ∆−2, motivating schedule adaptation.Source: §1 · p. 10
• An optimized schedule slows near the minimum gap and accelerates elsewhere, recovering the quadratic quantum speedup.This adapts the evolution rate to the local gap rather than constraining it uniformly throughout the computation.Source: §1 · p. 10

2. Quadratic quantum speedup

• The locally optimized schedule recovers the expected quadratic quantum speedup, although the rigorous adiabatic-error bound introduces a non-tight logarithmic factor.For p = 2, the schedule slows near the minimum gap; tighter analyses and numerical evidence support tf ∼ √N for small error (Roland and Cerf, 2002; Rezakhani et al., 2010b).Source: §2 · p. 11, §3 · p. 11

3. Multiple marked states

• With M marked states, the dynamics occupy an M+1-dimensional subspace, and the gap analysis changes from 1/N to M/N, preserving Grover’s quadratic speedup.The Hamiltonian has M−1 eigenvalues equal to 1−s, while the remaining relevant eigenvalues reproduce the single-marked-state analysis with 1/N replaced by M/N.Source: §3 · p. 12

B. Adiabatic Deutsch-Jozsa algorithm

• Adiabatic Deutsch–Jozsa algorithms match the circuit-model speedup, but require n-local Hamiltonians and also apply to arbitrary depth-one quantum circuits.Both unitary- and linear-interpolation implementations are presented as illustrative constructions.Source: B. Adiabatic Deutsch-Jozsa algorithm · p. 12

1. Unitary interpolation

• Unitary interpolation preserves the gap at ω, yielding an adiabatic runtime O(1) independent of n.The final Hamiltonian is obtained by conjugating the initial Hamiltonian with the oracle unitary, so the ground state encodes the Deutsch–Jozsa answer.Source: §1 · pp. 12–13

2. Linear interpolation

• Linear interpolation also gives adiabatic runtime O(1), using a gap lower bound determined by the overlap of the endpoint ground states.The overlap-based bound is minimized at η = 1/2, where the gap equals |a|; however, preparing the final Hamiltonian requires precomputing μ_f and effectively uses an overly powerful oracle.Source: §2 · p. 13

3. Interpretation

• The linear-interpolation algorithm certifies correct Deutsch–Jozsa outcomes by repeating inconclusive excited-state runs, with success probability p = 1 − q and q ∼ e−tf.Because tf is independent of n, the expected runs remain approximately 1 + e−tf, whereas classical certainty requires 2^(n−1) + 1 queries.Source: §3 · pp. 13–14
• A non-adiabatic Hamiltonian algorithm can solve Deutsch–Jozsa in constant time with a deterministic ground-state guarantee using a fine-tuned schedule.This contrasts with the adiabatic constructions, whose excited-state outcomes are inconclusive rather than incorrect.Source: §3 · pp. 13–14

• The construction encodes the oracle action f_a(w) in a Hamiltonian acting on n-qubit subsystem A and one-qubit subsystem B.Each state in subsystem A induces an independently evolving state in B, so adiabaticity in B does not depend on A’s size.Source: C. Adiabatic Bernstein-Vazirani… · p. 14
• A −1 measurement on subsystem B leaves subsystem A encoding every bit of a, while a +1 outcome yields no information and requires repetition.The k-th qubit is |+⟩ for a_k = 0 and |−⟩ for a_k = 1; after m tries, the failure probability is 2^-m and n-independent.Source: C. Adiabatic Bernstein-Vazirani… · p. 15
• The algorithm’s runtime is n-independent because only the single qubit in subsystem B effectively evolves.The construction also extends to an adiabatic version of Simon’s period-finding algorithm, preserving circuit-model depth scaling.Source: C. Adiabatic Bernstein-Vazirani… · p. 15
• The algorithm finds the unknown binary string a in O(1) time, matching the circuit-model depth and improving over the classical n-query requirement.The circuit model determines a with O(1) queries, whereas classical algorithms require n queries.Source: C. Adiabatic Bernstein-Vazirani… · pp. 14–15

D. The glued trees problem

• A polynomial-time quantum walk solves the glued trees problem, while the almost-adiabatic algorithm provides the reviewed example of a sub-exponential quantum speedup.Classical algorithms require at least a sub-exponential number of oracle calls; the almost-adiabatic procedure is not adiabatic throughout because it transitions between the ground and first excited states.Source: D. The glued trees problem · p. 15
• A polynomial evolution time suffices to find the right root, because the relevant adiabatic regions have gaps lower-bounded by c/n3 and c′/n3.The review concludes polynomial time from the schedule analysis, with an integral scaling as n6.Source: D. The glued trees problem · p. 16
• The glued-trees evolution follows the ground state, transitions to the first excited state across exponentially small gaps, then returns to the ground state before reaching the right root.The schedule is adiabatic in the polynomial-gap regions and non-adiabatic in the two exponentially closing-gap regions, producing both transitions with high probability.Source: D. The glued trees problem · pp. 15–16

E. Adiabatic PageRank algorithm

• The adiabatic PageRank algorithm prepares a state containing the same ranking information as the PageRank vector, but full-vector extraction is not generally more efficient than the best known classical algorithms.For particular graph topologies and tasks such as finding top-ranked entries, combining the algorithm with other quantum protocols may yield polynomial or exponential speedups.Source: E. Adiabatic PageRank algorithm · p. 16
• Its advantage is only a regular quantum speedup: it outperforms currently known classical algorithms, without ruling out better future classical methods.Unlike the previously reviewed algorithms, the PageRank result is not a provable quantum speedup against all classical algorithms.Source: E. Adiabatic PageRank algorithm · p. 16

1. Google matrix and PageRank

• PageRank is the unique positive eigenvector of the Google matrix with eigenvalue 1, while the power method computes it in O[sn log(1/ν)/log(1/α)] time.The Google matrix is irreducible and aperiodic, and its second eigenvalue modulus is at most α, determining power-method convergence.Source: §1 · p. 17

2. Hamiltonian and gap

• The non-local PageRank Hamiltonian has ground state |π⟩ equal to the normalized PageRank vector, interpolating from the complete-graph Hamiltonian’s uniform ground state.Equations (61)–(63) characterize the adiabatic algorithm apart from the schedule s(t).Source: §2 · p. 17
• For preferential-attachment and copying-model graphs, the numerically computed gap scales as (log n)^-b, yielding runtime governed by graph-dependent out-degree power laws.Here b > 0 is a small integer depending on graph parameters, and the gap behavior was attributed to the power-law distribution of out-degree nodes.Source: §2 · p. 17

3. Speedup

• O[n^(2γ_i−1)polylog(n)] versus O[n polylog(n)] gives a polynomial quantum speedup for top-ranked PageRank entries when γ_i < 1, based on average-case numerical evidence.The scaling is not a worst-case proof, and simulations reported in support it for the top log(n) entries.Source: §3 · p. 18
• O[polylog(n)] quantum access enables SWAP-test comparison of successive PageRank states, whereas classical closeness testing requires O[n^(2/3) log n] samples from each distribution.The quantum fidelity estimate requires measuring an ancilla O(1) times, with the count determined by the desired precision.Source: §3 · p. 18

IV. UNIVERSALITY OF AQC

• AQC is universal when its final ground state reproduces an arbitrary circuit output with probability greater than ϵ using poly(n) particles and evolution time poly(n, L).The resource bounds prevent blowup, while the ground-state requirement ensures that the adiabatic computation and circuit have the same output.Source: §IV · p. 18
• The review develops universal AQC constructions from six-state particles in two dimensions to qubits, two-local Hamiltonians, and one-dimensional nine-state particles.It also discusses gap amplification for frustration-free Hamiltonians, although that construction uses an excited state.Source: §IV · pp. 18–19

A. The circuit model can efficiently simulate AQC

• Circuit simulation approximates adiabatic evolution by a product of time-independent unitaries, whose discretization and Baker-Campbell-Hausdorff errors can be controlled.If the evolution is adiabatic, simulating U(tf, 0) suffices to map the initial ground state to the final ground state.Source: A. The circuit model can efficiently… · p. 19
• M scaling as t_f^2poly(n) approximates U(t_f, 0) with 2M unitaries, which can be decomposed into few-qubit gates for standard local Hamiltonians.For commuting single-qubit H0 terms this uses n one-qubit unitaries, while 2-local H1 terms use up to n^2 two-qubit unitaries; the adiabatic t_f scaling is inherited.Source: A. The circuit model can efficiently… · p. 19
• Randomized eigenpath traversal costs O[L^2/(ε∆)] on average and has worst-case cost max_s ||Ḣ(s)||^2/(ε∆^3), up to logarithmic factors.Random-time applications of H(t_j) induce eigenstate decoupling, allowing ground-state tracking while each evolution segment is decomposed into one- and two-qubit gates.Source: A. The circuit model can efficiently… · p. 19

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

• AQC can simulate any n-qubit circuit with at most polynomial overhead in its depth L, completing the first proof of AQC universality.The construction targets a final ground state equal to the circuit output.Source: B. AQC can efficiently simulate the… · pp. 19–20
• The circuit-to-Hamiltonian construction encodes the computation’s entire temporal trajectory in a history state using an L+1-qubit Feynman clock.The Hamiltonian interpolates from an easily prepared input ground state to the history-state ground state.Source: B. AQC can efficiently simulate the… · p. 20
• Clock, input, and propagation terms enforce legal clock configurations, initialize the computation, and implement each gate Uℓ through forward and backward propagation.Illegal clock states incur energy at least 1, while legal clock states have energy 0.Source: B. AQC can efficiently simulate the… · p. 20
• The adiabatic path has a unique ground state and polynomially bounded restricted and global spectral gaps, so the runtime tf scales polynomially with L.The initial state remains in the computation subspace S0 throughout the evolution.Source: B. AQC can efficiently simulate the… · pp. 20–21

C. Fermionic ground state quantum computation

• Fermionic GSQC spatially encodes a circuit’s trajectory with locally synchronized particles rather than a single global Feynman clock, while remaining universal for AQC (Mizel et al., 2001; Mizel et al., 2007).Each qubit uses local clock locations, and CNOT interactions synchronize the corresponding fermions.Source: C. Fermionic ground state quantum… · p. 21
• The fermionic construction uses 2-local interactions in two dimensions, with hopping terms implementing single-qubit gates and synchronized tunneling plus penalties implementing CNOT gates.The penalty term energetically suppresses configurations in which only one qubit has completed a CNOT.Source: C. Fermionic ground state quantum… · p. 21
• The original fermionic GSQC gap analysis was incomplete; Childs et al. (2013) supplied the Nullspace Projection Lemma, addressing the missing exclusion of zero-energy invalid time configurations.The unproven earlier claim concerned a lower bound on the total Hamiltonian’s spectral gap.Source: C. Fermionic ground state quantum… · p. 21
• A unitary mapping to the two-dimensional qubit space-time model made the gap analysis more convenient and established that the fermionic model is QMA-complete.The mapping connects the fermionic GSQC construction to a space-time circuit-to-Hamiltonian formulation.Source: C. Fermionic ground state quantum… · p. 22

D. Space-time Circuit-to-Hamiltonian Construction

• The space-time construction maps a universal 2n-qubit circuit onto particles on a rotated n × n grid, with non-identity gates confined to a k × k interaction region.The circuit uses n^2 two-qubit gates, and k = √n/16 in the described construction.Source: D. Space-time Circuit-to-Hamiltonian… · p. 22, Figure 3 · p. 22
• Connected string configurations encode computational paths as 2n bits of Hamming weight n, with particle internal states representing the circuit qubits.Each horizontal grid line contains one occupied edge, and the two bit values specify down-left or down-right motion.Source: D. Space-time Circuit-to-Hamiltonian… · p. 22
• The Hamiltonian combines input, string, and propagation terms so disconnected strings incur energy 2L −2, while valid connected strings have zero string energy and gates update internal states through Up or U†p.The initial ground state is |0^2n⟩|0^n1^n⟩ with eigenvalue 1, making it easily prepared.Source: D. Space-time Circuit-to-Hamiltonian… · pp. 22–23
• The ground state remains unique with gap at least 1/poly(n), and measuring particles crossing the interaction region yields the circuit output with probability bounded below by a positive constant.For k = √n/16, these properties enable efficient adiabatic simulation up to polynomial overhead.Source: D. Space-time Circuit-to-Hamiltonian… · p. 23
• The original implementation uses 4-body interactions, while Lloyd and Terhal (2016) reduce this to 2-local interactions using a first-order perturbation gadget and quadratically more qubits.First-order perturbation is significant because higher-order effective interactions can shrink gaps and increase overhead.Source: D. Space-time Circuit-to-Hamiltonian… · p. 23

E. Universal AQC in 1D with 9-state particles

• Universal AQC is possible in one dimension with 9-state particles, because quantum history states encode an additional time dimension despite classical 1D limitations.The construction requires a spectral gap tending to zero; the corresponding quantum local-Hamiltonian analogy is 2D classical MAX-k-SAT, which is NP-complete.Source: E. Universal AQC in 1D with 9-state… · p. 23
• The 1D construction distributes the clock, moves n-qubit blocks between gate sets, and penalizes invalid histories through propagation errors or locally detectable illegal configurations.A translation-invariant version used 20 states, improving on earlier 56-state and 20-state constructions.Source: E. Universal AQC in 1D with 9-state… · pp. 23–24

F. Adiabatic gap amplification

• Universal AQC simulates quantum circuits with frustration-free, local Hamiltonians whose final ground state overlaps the circuit output and whose inverse minimum gap is polynomial in circuit size.The construction uses polynomially many nearest-neighbor two-body interactions on one- or two-dimensional lattices.Source: F. Adiabatic gap amplification · p. 24
• Quadratic gap amplification for frustration-free Hamiltonians can yield a quadratic adiabatic speedup, but generally evolves a middle-spectrum state rather than satisfying strict AQC.The amplification is optimal in a suitable black-box model, while no general amplification exists without frustration freeness.Source: F. Adiabatic gap amplification · p. 24
• The amplified construction introduces ancilla registers, central-spin geometry, and penalty terms to create a unique zero-energy state while preserving a gap of quadratic order.Unary encoding reduces locality but destroys geometric locality, and additional penalties address degeneracies from single- and many-particle subspaces.Source: F. Adiabatic gap amplification · pp. 24–25

V. HAMILTONIAN QUANTUM COMPLEXITY THEORY AND UNIVERSAL AQC

• QMA-completeness studies promise-gap decisions about whether a local Hamiltonian’s ground-state energy lies below a threshold or above a larger threshold, while 2-local Hamiltonians naturally arising in AQC are QMA-complete.Perturbative gadgets used in locality reductions also support universality proofs for different Hamiltonian families.Source: §V · p. 25

3. The k-local Hamiltonian Problem

• 3-SAT maps to a 3-local Hamiltonian whose ground energy is zero for satisfiable formulas and at least one for unsatisfiable formulas.Each clause becomes a projector penalizing its unsatisfying assignments.Source: §3 · p. 26

4. Motivation for Adiabatic Quantum Computing

• Adiabatic evolution can decide k-local Hamiltonian instances by preparing an easy ground state, evolving to the target Hamiltonian, and measuring the resulting energy, motivating early AQC algorithms.This approach was proposed as a route to determining answers to NP-complete problems such as 3-SAT.Source: §4 · p. 26

B. MA and QMA

• QMA is the quantum analogue of MA, and the class inclusions MA ⊆ QCMA ⊆ QMA formalize the progression from classical to quantum witnesses.QMA verification uses an efficient quantum circuit and a polynomial-size quantum witness, with amplification applying to the acceptance gap.Source: B. MA and QMA · p. 27

C. The general relation between QMA completeness and universal AQC

• Universal AQC and QMA-completeness are closely related but neither formally implies the other: universality analyzes a continuous spectral gap with a chosen easy initial state, whereas QMA checks adversarial states for one Hamiltonian.Because AQC can select a convenient invariant subspace, proving QMA-completeness is generally harder despite their frequent correspondence.Source: C. The general relation between QMA… · p. 27

Locality reductions

• The k-local Hamiltonian problem is in QMA for constant k and is QMA-hard for k ≥5, while reductions establish QMA-completeness for 3-local and 2-local Hamiltonians; the 1-local case is in P.Thus, five-local Hamiltonians are QMA-complete, whereas one-local terms can be optimized independently.Source: D. QMA-completeness of the k-local… · pp. 27–28

Geometric and dimensional restrictions

• QMA-completeness persists under restrictions including nearest-neighbor 2D lattices, selected Heisenberg and XY interactions, interacting fermions, and one-dimensional multi-state systems, reaching 8-state particles; further dimensionality reduction remains open (Piddock and Montanaro, 2015).A translationally invariant 1D system has ground-state energy complete for QMAEXP.Source: D. QMA-completeness of the k-local… · p. 28

Perturbative gadgets

• Perturbative gadgets approximate an n-qubit target Hamiltonian using polynomially many ancillas, preserving the lowest 2^n eigenvalues within ϵ and the corresponding eigenstate overlaps to at least 1 − ϵ.The ancillas are governed by a penalty Hamiltonian, while the perturbation couples them to the target system.Source: D. QMA-completeness of the k-local… · p. 28

Universal AQC

• The gadget reduction preserves an inverse-polynomial energy gap and keeps computation in the ground subspace while penalizing illegal clock states, supporting universality of the resulting 2-local AQC Hamiltonian.This follows because the 2-local construction preserves the spectrum of the 5-local Hamiltonian used in the universality proof.Source: D. QMA-completeness of the k-local… · p. 28

Restricted interactions

• QMA-completeness extends to restricted 2-local Hamiltonians formed from real-valued sums of specified pairwise Pauli products, including ZZXX Hamiltonians that perturbatively approximate σz ⊗σx and σx ⊗σz terms.ZX Hamiltonians, defined as linear combinations with real coefficients of a specified restricted set, are also QMA-complete.Source: D. QMA-completeness of the k-local… · p. 29

Stoquastic Hamiltonians

• Stoquastic Hamiltonians have real nonpositive off-diagonal matrix elements in a fixed basis, including important models such as ferromagnetic Heisenberg, XY, and transverse-field Ising systems.The discussion fixes the standard computational basis and notes its connection to the basis used for final measurement.Source: §VI · p. 29

Stoquastic complexity

• The k-local stoquastic Hamiltonian problem is StoqMA-complete, including the transverse Ising model on degree-3 graphs, with MA ⊆ StoqMA ⊆ QMA.StoqMA differs from MA because its verifier may measure in the {|+⟩, |−⟩} basis; its threshold gap is inverse-polynomial rather than constant and therefore is not amplified by majority voting.Source: §VI · p. 29

StoqAQC

• StoqAQC restricts adiabatic computation to fixed-k local stoquastic Hamiltonians and therefore requires computation to remain in the ground state.The glued-trees algorithm is excluded because it lacks this ground-state restriction, while another stoquastic model is considered later without that restriction.Source: §VI · pp. 29–30

Motivation

• Experimental implementations of stoquastic Hamiltonians are advanced, motivating the study of StoqAQC and its associated complexity class.The section frames StoqAQC as a natural complexity-theoretic model based on experimentally relevant stoquastic evolution.Source: §VI · pp. 29–30

StoqAQCEval

• StoqAQCEval asks whether the final Hamiltonian’s ground-state energy is below a or all eigenvalues exceed b, under an inverse-polynomial gap promise throughout the evolution.The Hamiltonian path is continuous, fixed-k local, stoquastic, polynomially specified, and has Δ[H(s)] ≥1/poly(n) for every s, with b −a > 1/poly(n).Source: §VI · p. 30

BStoqP

• BStoqP, defined by polynomial-time reducibility to StoqAQCEval, satisfies BStoqP ⊆ StoqMA and lies in the intersection of StoqMA and BQP.The known relations also include BPP ⊆ BStoqP, while NP- and MA-hardness are not expected for polynomial-time StoqAQC.Source: §VI · p. 30, Figure 4 · p. 30

A. Why it might be easy to simulate stoquastic Hamiltonians

• Stoquastic ground states have real, nonnegative computational-basis amplitudes, enabling an associated classical probability distribution but motivating questions about quantum speedup.Complexity evidence places stoquastic k-local Hamiltonians in AM, gapped StoqAQC in PostBPP, and stoquastic frustration-free paths in BPP; these results suggest limitations but do not rule out all speedups.Source: A. Why it might be easy to simulate… · pp. 30–31
• These limitations apply specifically to ground-state evolution: excited-state stoquastic evolution can be as powerful as universal adiabatic quantum computation.The review also notes that gapped StoqAQC universality would imply unlikely complexity collapses, while excited-state evolution avoids that ground-state restriction.Source: A. Why it might be easy to simulate… · p. 31

B. Why it might be hard to simulate stoquastic Hamiltonians

• Monte Carlo simulations need not track stoquastic adiabatic evolution efficiently, even when the adiabatic gap is only polynomially small or large.The conjecture that small schedule steps preserve equilibrium can fail for both path-integral and diffusion quantum Monte Carlo.Source: B. Why it might be hard to simulate… · p. 31, §1 · p. 31, §2 · p. 32

1. Topological obstructions

• Topological obstructions can make PI-QMC take exponential time to equilibrate despite polynomial-gap adiabatic evolution.Winding-number sectors obstruct transitions, while bouquet-of-circles constructions additionally exploit L1/L2 discrepancies to suppress convergence even with open boundary conditions.Source: §1 · pp. 31–32

2. Non-topological obstructions

• L1/L2 normalization discrepancies can make D-QMC require exponential effort even when the adiabatic process reaches the ground state in polynomial time.The constructions arrange that walkers do not learn about a solution-containing potential well until an exponential number of steps-times-walkers, despite a polynomial minimum gap.Source: §2 · pp. 32–33

C. QMA-complete problems and universal AQC using stoquastic Hamiltonians with excited states

• A 3-local stoquastic Hamiltonian is QMA-complete and universal for AQC when computation is allowed to remain in an excited sector rather than the ground state.The construction preserves a universal spectrum in an invariant sector, but making that sector the ground state would require a non-stoquastic term.Source: C. QMA-complete problems and universal… · p. 33

D. Examples of slowdown by StoqAQC

• StoqAQC slowdowns arise in small-gap examples, but an exponentially small gap does not by itself prove exponentially long runtime because adiabatic theorems give upper rather than lower bounds.Finite-size numerical scaling claims, including exponential behavior, remain conjectural unless supported by analytical arguments.Source: D. Examples of slowdown by StoqAQC · p. 34

1. Perturbed Hamming Weight Problems with Exponentially Small Overlaps

• Perturbed Hamming-weight problems defeat local-search heuristics and induce exponentially small adiabatic gaps through exponentially small overlap with the marked all-one state.The global optimum lies in a narrow basin, while the analysis constructs a critical point where the gap vanishes and bounds the Hamiltonian gap using the overlap.Source: §1 · pp. 34–35
• Exponentially small overlap between initial and final ground states forces exponential runtime, reflecting local quantum search's inability to explore a non-local energy landscape effectively.This occurs in perturbed Hamming-weight problems, where local fluctuations fail to reach the relevant final state.Source: §1 · p. 35

2. 2-SAT on a Ring

• The 2-SAT ring has a polynomial minimum gap and polynomial adiabatic runtime, yet offers no quantum speedup because a classical satisfying assignment costs at most n.The example is exactly solvable using Jordan-Wigner and Fourier transformations, and demonstrates that polynomial gaps do not guarantee speedup.Source: §2 · pp. 35–36

3. Weighted 2-SAT on a chain with periodicity

• Weighted 2-SAT chains develop exponentially small gaps across constant s intervals, with exponentially many nearby excitations, because heavy sectors order before light sectors and local dynamics create domain-wall traps.The mechanism is associated with a Griffiths phase: local spin flips cannot coordinate ordering across sectors within subexponential time.Source: §3 · p. 37

4. Topological slowdown in a dimer model or local Ising ladder

• In the dimer model or dual frustrated Ising ladder, local moves preserve topological winding sectors, causing a first-order transition and an exponentially small gap when K ≫ U.The strong-field ground state lies in the w = 0 sector, while the final ground states have w = ±1, so tunneling between sectors becomes exponentially slow.Source: §4 · pp. 37–38, Figure 5 · p. 38

5. Ferromagnetic Mean-field Models

• For ferromagnetic p-spin models with p > 2, tuning Γ produces a first-order transition whose degenerate double-well free energy yields an exponentially small gap.The discontinuity in the minimizing magnetization and instanton analysis establish the exponential gap scaling with system size.Source: §5 · p. 38

6. 3-Regular 3-XORSAT

• Random 3-regular 3-XORSAT shows an exponentially small median minimum gap and a first-order transition at s = 1/2, while both StoqAQC and WalkSAT require exponential time despite polynomial solvability by Gaussian elimination.The numerical evidence extends to n = 24 and n = 40; however, first-order transitions do not universally imply exponential gaps, since polynomial-gap counterexamples exist.Source: §6 · pp. 38–39

7. Sherrington-Kirkpatrick and Two-Pattern Gaussian Hopfield Models

• In the two-pattern Gaussian Hopfield model, O(log n) spin-glass bottlenecks have stretched-exponential gaps e−cΓ_m^3/4 n^3/4, causing slowdown although angle sorting and exhaustive search solve it in O[n log(n)].The bottlenecks arise after the polynomial gap closing and reflect self-similar structure in the free-energy landscape, showing that complexity is governed by small-gap bottlenecks rather than the phase transition itself.Source: §7 · p. 39

E. StoqAQC algorithms with a scaling advantage over simulated annealing

• The reported StoqAQC advantages are qualified because comparisons generally use only single-spin simulated annealing, leaving cluster updates and parallel tempering largely unresolved.The broader construction of tunneling gadgets and small-and-thin barriers is primarily numerical, making asymptotic extrapolation difficult.Source: E. StoqAQC algorithms with a scaling… · p. 40

1. Spike-like Perturbed Hamming Weight Problems

• For spike-like Hamming-weight barriers, StoqAQC can run in polynomial time while single-spin simulated annealing requires exponential time, including generalized barriers with polynomially closing gaps.For barrier width n^α and height n^β, the gap scales as n^(1/2−α−β) when α + β ≥ 1/2, α < 1/2, and 2α + β ≤ 1, while simulated annealing scales exponentially in n^α.Source: §1 · p. 40

2. Large plateaus

• Large plateaus also yield a polynomial StoqAQC advantage over single-spin simulated annealing, but diabatic evolution, spin-vector dynamics, and quantum Monte Carlo can match or exceed it.On plateaus, simulated annealing performs a random walk with runtime O(n^(u−l−1)), whereas the quantum minimum gap is constant and the adiabatic runtime is O(n^1/2).Source: §2 · p. 41

1. Number partitioning

• For number partitioning, StoqAQC simulations scale as 2^0.8n versus simulated annealing’s 2^0.98n, but state-of-the-art classical algorithms reach 2^0.291n and the encoding requires exponentially large inputs for NP-hardness.The hard phase has a rugged energy landscape, while bounded inputs permit polynomial-time dynamic programming.Source: §1 · p. 41

2. Exact Cover and its generalizations

• For Exact Cover and related satisfiability problems, large-instance gaps are exponentially small, so whether StoqAQC provides even a polynomial speedup remains open.Exact Cover’s initially polynomial-looking gap scaling changes asymptotically through a first-order phase transition, and locked 1-in-3 and 1-in-4 SAT also exhibit exponentially small gaps.Source: §2 · p. 42

3. 3-Regular MAXCUT

• For 3-regular MAXCUT, the first gap minimum closes polynomially, but a second minimum inside the spin-glass phase closes exponentially or possibly stretched-exponentially, implying exponential adiabatic runtime.The associated glass transition is not traversed faster than simulated annealing under a linear schedule.Source: §3 · pp. 42–43, Figure 7 · p. 42

4. Ramsey numbers; 5. Finding largest cliques in random graphs; 6. Graph isomorphism; 7. Machine learning

• For Ramsey numbers, largest cliques, graph isomorphism, and machine learning, StoqAQC formulations exist but quantum speedup or computational superiority remains unknown or unsupported asymptotically.Ramsey simulations correctly determine selected values; clique results on graphs up to 18 vertices appear quadratic but likely miss exponentially small gaps; graph-isomorphism complexity is unknown, and machine-learning benefits may instead concern speculative classification accuracy.Source: §4 · p. 43, §5 · p. 43, §6 · p. 44

G. Speedup mechanisms?; 7. Sherrington-Kirkpatrick and Two-Pattern Gaussian Hopfield Models

• The section frames tunneling and entanglement as two potential mechanisms for StoqAQC advantage, while the Sherrington-Kirkpatrick and Gaussian Hopfield examples include additional spin-glass-phase gap minima.In the Gaussian Hopfield model, the spin-glass phase contains log n additional minima in the gap.Source: Figure 6 · p. 39, G. Speedup mechanisms? · p. 44

1. The role of tunneling

• In the Grover problem, following the instantaneous ground state requires coherent tunneling involving O(n) spins across the minimum gap at s = 1/2, despite the final cost landscape being flat except for a marked-state well.At the transition, the semiclassical potential has two degenerate minima and the Hamming-weight difference between them is n/2.Source: Figure 8 · p. 45, §1 · pp. 45–46
• Tunneling is neither necessary nor sufficient for speedups in perturbed Hamming-weight problems with qubit-permutation symmetry.The discussion concerns coherent tunneling; thermally assisted tunneling is outside this closed-system review and contributes only a prefactor rather than a scaling advantage in the cited examples.Source: §1 · p. 46

2. The role of entanglement

• The relationship between entanglement and AQC efficiency remains open because its connection to spectral gaps and its computational role are not understood.Circuit-model results do not settle the AQC question, and even when entanglement is present its contribution to computation remains unclear.Source: §2 · pp. 46–47
• Entanglement can improve ground-state success probability in two-dimensional Ising spin-glass representations, but this does not establish a speedup mechanism.In MPS and PEPS representations, success probability increased with entanglement, and even small entanglement outperformed mean-field models; however, the link to speedup remained unresolved.Source: §2 · pp. 46–47
• Performance and entanglement are not generally correlated: Grover search has entanglement entropy ≤1, Exact Cover has entropy linear in n for n ≤20, and large entropy had little significance in a trapped-ion optimization simulation.A higher-success two-dimensional Grover path even used less negativity than the standard path, while adding entanglement does not overcome known limits without marked-state dependence.Source: §2 · p. 47

A. Avoiding poor choices for the initial and final Hamiltonians

• Choosing a uniform-superposition projector as the initial Hamiltonian with linear interpolation cannot achieve better-than-quadratic speedup when the final Hamiltonian is computational-basis diagonal.The lower bound applies to measuring the final ground state with probability p and depends on N = 2^n and ground-state degeneracy k.Source: A. Avoiding poor choices for the… · p. 47
• Removing structure from the final Hamiltonian likewise prevents constant-probability success for even a fraction of permutations when the runtime is o(√N).The analysis motivates avoiding both an unstructured projector initial Hamiltonian and an unstructured final Hamiltonian.Source: A. Avoiding poor choices for the… · p. 48

B. Quantum Adiabatic Brachistochrone

• The quantum adiabatic brachistochrone formulates time-optimal evolution as a variational problem balancing total runtime against final-state fidelity.The optimal path is obtained by extremizing an adiabatic-time functional, with the resulting equations interpreted as geodesics in a Riemannian metric.Source: B. Quantum Adiabatic Brachistochrone · pp. 48–49
• Smaller spectral gaps produce higher geometric curvature, linking difficult adiabatic regions to sharply curved control manifolds.The curvature scales as R ∼ Δ^(-p−2), while computing the metric requires knowledge of, or an estimate for, the gap.Source: B. Quantum Adiabatic Brachistochrone · p. 49
• For Grover search, the analytically derived p = 4 geodesic schedule is equivalent to the known optimal schedule, revealing its differential-geometric origin.This equivalence holds under the Grover identification α0 = 1/√N despite differing norm choices and p values.Source: B. Quantum Adiabatic Brachistochrone · p. 49
• The two-parameter QAB path lowers adiabatic error relative to the Roland–Cerf path without improving its already-optimal N scaling.It also has lower curvature, implying a path with a larger gap and less entanglement; Fig. 9 compares the error and curvature behavior.Source: B. Quantum Adiabatic Brachistochrone · pp. 49–50, Figure 9 · p. 50

C. Modifying the initial Hamiltonian

• Randomizing the initial Hamiltonian with coefficients ci ∈ {1/2, 3/2} removes the standard algorithm’s small gap with high probability for the constructed 3-SAT instances.Because the randomization does not use instance-specific information, the algorithm can be repeated with different initial Hamiltonians on a single instance.Source: C. Modifying the initial Hamiltonian · p. 50
• Warm-start repetitions use an initial solution guess and measured diabatic outputs as successive starting states, improving 3-SAT performance on 6- and 7-qubit instances.The reported improvement was limited to relatively small system sizes.Source: C. Modifying the initial Hamiltonian · p. 50

D. Modifying the final Hamiltonian

• For EC3, adding permissible positive pairwise terms to the final Hamiltonian may avoid Anderson localization, showing that failure of one representation does not establish universal algorithmic failure.Numerical evidence up to 15 bits supports this possibility, while the added parameters Dij are arbitrary positive values.Source: D. Modifying the final Hamiltonian · p. 50

E. Adding a catalyst Hamiltonian

• A catalyst vanishes at the initial and final times, uses local terms matching H1’s qubit-interaction graph, and is independent of instance-specific information.Source: E. Adding a catalyst Hamiltonian · p. 51
• With an analytically tractable non-stoquastic catalyst, the potential retains one global minimum throughout evolution, avoiding tunneling and reducing runtime from exponential to polynomial.Source: E. Adding a catalyst Hamiltonian · p. 51, Figure 10 · p. 52
• Catalysts improved success rates across many n = 20 MAX 2-SAT instances, but stoquastic and non-stoquastic catalysts differed inconclusively.Source: E. Adding a catalyst Hamiltonian · p. 51
• For fully connected Ising instances, stoquastic catalysts mainly helped easy cases through larger gaps and fewer anticrossings, whereas non-stoquastic catalysts helped hard cases via recovery across more anticrossings.Source: E. Adding a catalyst Hamiltonian · p. 51

F. Addition of non-stoquastic terms

• Analyses of infinite-range ferromagnetic and random Ising models found that non-stoquastic terms can sometimes change first-order transitions with exponentially small gaps into second-order transitions with polynomially small gaps.Source: F. Addition of non-stoquastic terms · p. 52
• For p ≥4, an appropriately chosen path with a two-local non-stoquastic XX term changes the ferromagnetic transition order; in Hopfield models, fixed-pattern cases require p ≥5.Source: F. Addition of non-stoquastic terms · p. 52

Problem

• Perturbative crossings can produce gaps exponentially small in the Hamming distance between crossing states, including Θ(n) separations in Exact Cover instances.The proposed high-probability mechanism for random NP-complete problems was later undermined by extreme-value statistics, but exponentially small late-evolution gaps remain possible.Source: G. Avoiding perturbative crossings · pp. 52–53

Avoidance strategy

• Different adiabatic implementations can avoid perturbative crossings, and suitable initial and final Hamiltonians can be found efficiently in polynomial time, space, and energy (Choi, 2010; Dickson and Amin, 2011; Dickson, 2011).This result excludes perturbative crossings but not non-perturbative ones.Source: G. Avoiding perturbative crossings · p. 53

Construction

• The construction changes final-spectrum degeneracies so the ground state is most degenerate and excited states have progressively fewer degeneracies, using ancilla interactions that preserve the original ground-state energy.Ancilla flips raise energy, preserve the original spectrum when all ancillas point down, and introduce no new local minima.Source: G. Avoiding perturbative crossings · p. 53

Mechanism

• For a = b = n^2, lower-final-energy states acquire more negative first-order slopes, causing competing states to separate for λ > 0 and thereby avoiding the perturbative crossing.Higher-order corrections do not depend on a, so the first-order correction controls the relevant behavior.Source: G. Avoiding perturbative crossings · p. 54

Scope and limitation

• The method applies to arbitrary Ising models with local fields and is fully stoquastic, so all NP-complete problems can be addressed without perturbative crossings, though polynomial-time solvability is not established.Any remaining exponential runtime must arise from an effect other than unavoidable perturbative crossings.Source: G. Avoiding perturbative crossings · p. 54

H. Evolving non-adiabatically

• Diabatic evolution can improve performance by transferring population through avoided-level crossings, including cascades through higher excited states that return population to the ground state.Rapid evolution improved success on hard n = 20 MAX-2-SAT instances and produced diabatic cascades for perturbed Hamming Weight problems.Source: H. Evolving non-adiabatically · p. 54, Figure 11 · p. 54
• The time-to-solution metric optimizes evolution time against repetition count, with TTS scaling linearly with tf near the adiabatic limit but potentially decreasing for shorter runs.For single-run success probability pS, the failure probability after R repetitions is (1−pS)^R, and the optimal tf minimizes TTS(tf).Source: H. Evolving non-adiabatically · pp. 54–55
• Quantum annealing exhibits a scaling advantage over single-spin-update simulated annealing on constant-gap perturbed Hamming Weight and spike problems, despite classical O(1)-time algorithms for those oracular problems.The comparison is expressed through the TTS scaling of QA versus SA, rather than through the minimum-gap scaling alone.Source: H. Evolving non-adiabatically · p. 55

VIII. OUTLOOK AND CHALLENGES

• The review leaves open whether non-stoquastic quantum-chemistry Hamiltonians yield a speedup because the minimum-gap scaling of the adiabatic state-preparation procedure is unknown.The review also excludes open-system AQC, error correction, fault tolerance, and experimental AQC for separate treatment.Source: §VIII · p. 55
• The review identifies StoqAQC’s classical simulability and the existence of worst-case, non-oracular, physically realizable AQC speedups among ten central theoretical challenges.Additional challenges concern efficient non-stoquastic ground-state preparation, native AQC formulations, diabatic-versus-adiabatic speedups, schedule prediction, tunneling, and entanglement.Source: §VIII · pp. 55–56

Appendix C: Technical details for the proof of the universality of AQC using the History State construction

• The construction identifies ground states of the initial and final Hamiltonians, preserves dynamics in S0 spanned by {|γ(ℓ)⟩}, and proves that for s < 1/3 the ground state is unique with minimum gap at least 1/6.Source: §1 · p. 58, §2 · p. 58, §3 · p. 58

b. Bound for s ≥1/3

• For s ≥ 1/3, monotonicity of the ground state implies monotonicity of Π, enabling the conductance bound to establish condition (C21).G(s) preserves monotonicity, and Perron’s theorem identifies the positive leading eigenvector with the monotone ground state.Source: b. Bound for s ≥1/3 · p. 60

4. Gap bound in the entire Hilbert space

• The global gap over the entire Hilbert space is bounded below by Ω(1/L^3).The Hamiltonian separates into legal and illegal clock-state blocks; illegal states lie at energy at least one, while the legal-sector bound follows from the Geometrical Lemma and an angle estimate.Source: §4 · pp. 60–61

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

• Majority amplification converts MA(2/3, 1/3) to exponentially small completeness and soundness errors using K = poly(|η|) verifier repetitions.The construction repeats V(η, X) K times and takes a majority vote; Chernoff bounds handle both Q(η) = 1 and Q(η) = 0 cases.Source: Appendix D · p. 61
• For p = c − 1/|η|^g, choosing ϵ = 1/|η|^g and K = ϵ^-2−ε exponentially suppresses Merlin’s ability to fool Arthur while keeping K polynomial.The argument expands the Kullback-Leibler divergence as D(p + ϵ∥p) = ϵ^2/[2p(1−p)] + O(ϵ^3).Source: Appendix D · p. 62

1. Degenerate Perturbation Theory `a la (Bloch, 1958)

• Degenerate perturbation theory constructs an effective Hamiltonian for H = H0 + λV by projecting perturbed low-energy states onto H0’s degenerate ground subspace.The perturbative series converges when ∥λV∥ < γ/4, where γ is the gap to H0’s first excited state.Source: §1 · pp. 62–63

2. Perturbative Gadgets

• Perturbative gadgets use strongly bound ancillas and weaker target-ancilla couplings so that a k-local target Hamiltonian emerges in the low-energy effective theory of a 2-local Hamiltonian.The construction introduces k ancillas per target term and analyzes the effective Hamiltonian within the appropriate ancilla symmetry sector.Source: §2 · pp. 63–64
• The ancilla-induced perturbation shifts the ground-subspace energy, while its first nontrivial degeneracy splitting occurs at k-th order and reproduces the target interaction.Lower-order processes either return ancillas to their original states and contribute identity-proportional shifts or cancel through projection.Source: §2 · p. 64
• Convergence requires λ < (k −1)/(4k), while the generated interaction scales as λ^k, making strong couplings potentially difficult to implement.Weaker gadgets avoid this strength mismatch by repeating interactions with classical ancillas, at the cost of additional ancillary-qubit overhead; further simplifications and resource reductions were proposed in (Cao et al., 2015).Source: §2 · pp. 64–65
• The target Hamiltonian appears as the leading effective-Hamiltonian term, but its interaction strength is reduced to order λ^k/(k −1)! .For multiple target terms, only products acting on one ancilla register can contribute the required k-fold splitting, yielding the corresponding sum of target terms.Source: §2 · pp. 64–65