Optimal scaling quantum linear systems solver via discrete adiabatic theorem

I. INTRODUCTION

• The QLSP model assumes ∥A∥ = 1, ∥A^-1∥ = κ, a block encoding of A, and an oracle preparing |b⟩, leaving κ and ϵ as the algorithm’s relevant parameters.The target is a quantum state proportional to the solution of Ax = b.Source: §I · p. 2
• Earlier QLSP approaches used variable-time amplitude amplification or polynomial and Dyson-series approximations, whose recursive amplification or approximation overhead made implementation challenging or added polylog(κ) scaling.Prior adiabatic methods [15] offered near-linear κ dependence, while polynomial approximations and truncated Dyson series [15] incurred extra polylog(κ) factors.Source: §I · pp. 2–3
• O(κ log(1/ϵ)) query complexity gives the first strictly linear-κ QLSP algorithm and matches the known Ω(κ log(1/ϵ)) lower bound.The paper also states that the combined scaling in κ and ϵ is optimal.Source: §I · p. 3, Table I · p. 3
• The algorithm combines a qubitised quantum-walk adiabatic evolution with an improved eigenstate filter whose operations are easily determined, avoiding variable-time amplification and truncated Dyson-series subroutines.The filtering method is as efficient as singular value processing but avoids its numerically demanding rotation-sequence search.Source: §I · pp. 2–4

A. Background

• In the discrete model, T walk operators are applied sequentially, with sufficiently slow variation intended to keep the evolving state approximately in the selected eigenspace.The ideal evolution carries the initial eigenspace to the corresponding eigenspace of the walk operator at each step.Source: A. Background · p. 4
• O(κ/T) error yields T = O(κ) steps for fixed error; unlike DKS, the analysis tracks the spectral-gap dependence needed for QLSP.The gap in the QLSP adiabatic approach depends on κ.Source: §I · p. 3, A. Background · p. 4

B. Our result

• The simplified discrete theorem bounds error using first- and second-step differences and an adjusted gap, with terms scaling as 1/T and 1/T^2 and a cubic inverse-gap dependence in its first sum.It requires sufficiently smooth walk operators so c(s) can be chosen independently of T, and the schedule can vary more slowly where the gap is small.Source: B. Our result · pp. 5–6

III. THE FIRST ADIABATIC THEOREM

• The proof aims to show that the wave operator is close to identity, using a discrete summation-by-parts formula to bound its accumulated steps.Source: §III · p. 6
• Unlike the prior O(1/T) result in, the first discrete adiabatic theorem seeks explicit error bounds dependent on the spectral gap.Source: §III · p. 6

A. Operator definitions

• The wave operator describes the difference between actual and ideal adiabatic evolution; it is a product of ripple operators, while the kernel should be close to zero.Source: A. Operator definitions · p. 7

B. Sequence of Lemmas

• The proof decomposes the accumulated error into diagonal and off-diagonal sums, with the harder off-diagonal terms handled by Lemma 14’s summation-by-parts formula.Source: B. Sequence of Lemmas · p. 8
• Supporting lemmas propagate projector-difference bounds through VT, the ideal adiabatic walk, and the wave operator, then bound auxiliary A, B, and Z operators.Source: B. Sequence of Lemmas · p. 8

C. Properties of operators

• Proposition 4 states that the adiabatic walk and evolution operators are unitary and gives relations involving projectors onto the desired and orthogonal subspaces.Source: C. Properties of operators · p. 8
• Proposition 5 characterizes the ripple operator as a rotation of VT and gives a discrete Volterra equation for the wave operator.Source: C. Properties of operators · p. 9
• The auxiliary X̃, A, B, and Z operators are defined for later use in a summation-by-parts formula and to simplify notation.Source: C. Properties of operators · p. 9

D. Bounding the operators

• The contours ΓT(s, k) enclose the relevant spectrum for k + 1 successive walk steps, maintaining a gap that prevents eigenvalues of interest from crossing between steps.The illustrated contour passes through spectral gaps and closes with a radius-2 arc; the closure is taken to infinity when the integrand permits it.Source: D. Bounding the operators · p. 9, Figure 2 · p. 10
• Direct calculations give bounds for DPT and D(2)PT, while subsequent lemmas bound the changes in VT, WA_T, and ΩT.The bounds are stated for discrete time; the WA_T bound assumes its definition in Eq. (24), and the ΩT bound uses its definition in Eq. (27).Source: D. Bounding the operators · pp. 9, 11, 12
• The summation-by-parts lemma collects bounds for the operators used in the formula, including Z(s), for any bounded operator X(s).The stated bound on Z(s) depends on gap terms Δ0(s) and Δ1(s), as well as differences of X(s) and VT(s).Source: D. Bounding the operators · pp. 12–13
• Lemma 13 gives an upper bound on ∥Z(s)∥ with contributions involving TΔ0(s), TΔ1(s), c1(s), ∥DX(s)∥, and ∥DVT(s − 1/T)∥.The bound also includes terms involving ∥FT(s) − I∥, ∥DPT(s)∥, and ∥FT(s)∥.Source: D. Bounding the operators · p. 13
• The summation-by-parts formula corrects the sign convention in Theorem 1 of: B is negated, while S is unchanged and appears with a minus sign in B − S/T.The authors state that the proof is given in Appendix C.Source: D. Bounding the operators · pp. 13–14

Theorem statement

• Theorem 15 bounds the difference between the product evolution and the ideal adiabatic evolution that maps the initial eigenstate to its corresponding eigenstate at time s.The theorem considers discrete times s and assumes the step operators satisfy the stated regularity conditions.Source: E. The first discrete adiabatic theorem · p. 14

Theorem conditions

• The theorem requires T ≥ max_s∈[0,1](2c1(s)/∆1(s)), with the gaps defined as in Definition 2.It also assumes first- and second-order difference bounds for the step operators, as specified in Definition 1.Source: E. The first discrete adiabatic theorem · p. 14

Proof

• The proof separates the summation into diagonal and off-diagonal terms and bounds corresponding contributions symmetrically for the target and complementary eigenspaces.It treats one representative term from each pair, noting that the same bounds apply to the paired terms.Source: E. The first discrete adiabatic theorem · pp. 15–16

F. Proof of the second adiabatic theorem

• Theorem 3’s proof simplifies Theorem 15 by accounting for neighboring steps in its coefficients and minimum gaps, and bounding higher-order terms under a stricter lower bound on T.The required condition is T ≥ max_s(4 ĉ1(s)/∆̌(s)).Source: F. Proof of the second adiabatic theorem · pp. 16–17

A. Preparing the walker

• The target is a normalized state approximating A^-1|b>/||A^-1|b>|| within precision ϵ, obtained from the discrete walk evolution.The setup assumes invertible A with ||A||=1 and normalized |b>.Source: A. Preparing the walker · p. 18
• For positive-definite Hermitian A, the walk aims to evolve |0,b>, a zero-energy state of H0, to a solution-encoding eigenstate of H1 [15].The orthogonal shared zero-energy state does not cross during the ideal adiabatic evolution using the walk.Source: A. Preparing the walker · p. 18
• A gap-adapted schedule slows evolution as the gap shrinks; the chosen schedule has increasing f(s) and decreasing f-dot(s) [15].The schedule satisfies the cited condition using a lower bound on the gap [15].Source: A. Preparing the walker · pp. 18–19
• For Hermitian but non-positive-definite A, two ancilla qubits enlarge the block, and the target becomes the zero-energy state |0,+,b>; the same schedule remains usable.The gap lower bound is (1 − f(s))^2 + (f(s)/κ)^2.Source: A. Preparing the walker · p. 19
• For non-Hermitian A, replacing σx ⊗ A by A avoids expanding the dimension while retaining the same lower bound on the spectral gap.The resulting gap lower bound is (1 − f(s))^2 + (f(s)/κ)^2, as in the Hermitian case.Source: A. Preparing the walker · pp. 19–20
• Using a qubitised quantum walk avoids the logarithmic complexity factor from Dyson-series Hamiltonian simulation, with block encodings of H0 and H1 selected by an ancilla rotation.The asymmetric component encodings are paired in reverse order so the full encoding is symmetric, as required for qubitisation.Source: A. Preparing the walker · p. 20

B. Choosing values for c1(s) and c2(s)

• Changes in W_T(s) have the same spectral norm as changes in R(s), because the s-dependence enters through R(s) in two cross-diagonal blocks.This reduction is used to bound the walk operator differences needed to estimate c1(s) and c2(s).Source: B. Choosing values for c1(s) and c2(s) · p. 20
• The first-difference bound uses the rotation derivative, whose norm with respect to f ranges from 1 to 2, and df/ds > 0.The section uses this bound to choose c1(s).Source: B. Choosing values for c1(s) and c2(s) · p. 21
• The second-difference bound applies Taylor’s theorem in two directions, bounds the second derivative of R(s), and uses ∥D2W(s)∥ = ∥D2R(s)∥ to choose c2(s).The resulting choice satisfies the requirement ∥D2W(s)∥ ≤ c2(s)/T^2.Source: B. Choosing values for c1(s) and c2(s) · pp. 21–22

C. Linear κ for p = 3/2

• Theorem 17 establishes strict linear dependence on κ for the discrete QLSP with p = 3/2, using T ≥ κ steps for positive-definite Hermitian A and giving bounds for general A.The p = 3/2 schedule is chosen to estimate algorithm constant factors.Source: C. Linear κ for p = 3/2 · p. 22
• Neither the degenerate zero eigenvalue nor the walk’s paired eigenstates alters the solution: the degenerate states do not cross, and no relative phase is introduced.Source: C. Linear κ for p = 3/2 · p. 23

D. General p

• For general A and 1 < p < 2, the discrete error scales as O(κ/T), implying O(κ/ε) complexity; the proof bounds discrete sums using integrals and quadrature errors.Theorem 18 gives a p-dependent constant that is much larger than Theorem 17’s for p = 3/2 because its general proof uses non-sharp inequalities.Source: D. General p · p. 23

E. Numerical Results

• In the numerical upper-bound calculation, the scaling constant was about 638, and Theorem 17’s estimated constant was around 9 times bigger.For initial in-spectrum probability at least 1/2, adiabatic evolution required about 834κ steps, versus ln(2/ϵ) about 20 when ϵ was one part in a billion.Source: E. Numerical Results · p. 24, §V · pp. 27–28

V. FILTERING FOR SOLVING LINEAR EQUATIONS

• The proposed LCU filter uses two ancillas rather than singular value processing’s one, but makes the gate sequence simpler to determine.Sequential measurements can flag failures early, reducing the average operations for failed runs by about half.Source: §V · pp. 24, 26, 27

E. Numerical Results

• At fixed T = 5 × 10^4, the error was approximately linear in κ across tested p values, and p = 1.3 gave the smallest error at κ = 40.The figures show the error bound versus κ and versus p, respectively.Source: Figure 3 · p. 24, E. Numerical Results · p. 24, Figure 4 · p. 25

V. FILTERING FOR SOLVING LINEAR EQUATIONS

• The Dolph–Chebyshev window minimizes the maximum off-spectrum amplitude, and the resulting filter uses ℓ block-encoding calls versus 2ℓ for singular value processing.Source: §V · pp. 25–26
• O(κ log(1/ε)) total complexity follows by combining O(κ) fixed-precision adiabatic evolution with filtering, with success probability at least 1/2 and an average of two attempts.The successful output is within norm-distance ε of the solution.Source: §V · p. 27

VI. CONCLUSIONS

• Quantum walks directly discretize adiabatic evolution without Dyson-series simulation, while a discrete adiabatic theorem bounds error and yields the first QLSP algorithm optimal in κ.The work also establishes rigorous new error bounds for discrete adiabatic theorems.Source: §VI · p. 28
• The authors expect their approach to outperform other QLSP methods in asymptotic scaling and finite-instance constant factors.They note that numerical results differ by over an order of magnitude from analytically proven scaling constants, which could be tightened through more careful accounting, but was not pursued.Source: §VI · p. 28
• The algorithm achieves optimal O(κ log(1/ϵ)) complexity, matching the lower bound.The log(1/ϵ) factor comes only from filtering, which the authors expect to have lower practical complexity than the initial adiabatic step.Source: §VI · p. 28
• The algorithm’s complexity is expressed in block-encoding calls, while the sparsity-oracle lower bound includes a multiplicative factor d.Achieving that sparsity scaling would require block encoding with complexity d; standard methods are linear in d.Source: §VI · p. 28
• Discrete adiabatic methods may benefit other continuous-time quantum algorithms, including optimization algorithms based on adiabatic evolution.Prior analysis of discrete adiabatic evolution is described as less tight; unlike Trotter-based digital adiabatic simulation, this approach introduces no discretization error because it invokes the discrete adiabatic theorem directly.Source: §VI · p. 28

Appendix A: List of variables

• Appendix A provides a list of variable names linked to their definitions.Source: Appendix A · p. 29

1. List of variables presented in Section II

• Section II notation covers the walk operators, indexed evolution steps, spectrum projectors, and the discrete-time schedule from s = 0 to 1.It also defines difference operators and bounds, spectra, and gaps over successive steps.Source: §1 · pp. 29–30

2. List of variables presented in Section III

• Section III notation names the resolvent, spectrum-mapping operators, wave and ripple operators, and contours used in the discrete adiabatic theorem proof.The list also includes auxiliary variables and functions used in the proof.Source: §2 · p. 30

3. List of variables presented in Section IV

• Section IV notation identifies the QLSP matrix, dimension, and condition number, along with the Hermitian matrix and Hamiltonian used in the adiabatic evolution.It also defines the input vector and the allowable solution error.Source: §3 · pp. 30–31

4. List of variables presented in Section V

• Section V notation covers the filtering weights and their Fourier transform, walk-operator eigenvalue labels, and the Chebyshev polynomial order.Source: §4 · p. 31

Appendix B: Proof of Lemma 6

• The proof bounds projector differences using resolvent contour integrals, with the second-order difference using a contour through the gaps for three consecutive steps.The contour arc contribution vanishes as its radius tends to infinity; the resulting bounds are then combined.Source: Appendix B · pp. 31, 33, 34

Appendix C: Proof of Lemma 14

• The proof of Lemma 14 begins from an identity expressing a term as the commutator [P_T(s), X(s)].The identity is then used as the starting point for substitutions into Eq. (C1).Source: Appendix C · p. 34
• Using the definition of W_A^T(s) in Eq. (24) and substituting into Eq. (C1), then setting P_T(s) = U_A^T(s) in Eq. (C2), the passage identifies A(s) via Eq. (39).Source: Appendix C · p. 34
• To complete the proof, the expression in Eq. (C3) is multiplied on the right by Y(s) and summed from 1/T to l/T.The boundary term is derived from the first part of the right-hand side of Eq. (C3).Source: Appendix C · p. 35
• The sums are combined using Y(s) = −DY(s) + Y(s + 1/T), with B correcting for the extra n = 0 and missing n = l terms.The resulting expression is substituted into Eq. (C3).Source: Appendix C · p. 35

1. Diagonal term

• The diagonal term in Eq. (88) is bounded by considering, without loss of generality, only its projection onto P0.The derivation invokes Eq. (30) and Lemma 7.Source: §1 · p. 36
• The diagonal-term bound proceeds from the second term in the last inequality and replaces P_T(n−/T) by P_T(n/T) − D P_T(n−/T).The replacement is made in the last term of Eq. (D2).Source: §1 · p. 36
• For any two projections p and q, the derivation uses p(p − q)p = p(p − q)^2p.This equality is used in the last calculation of the diagonal-term bound.Source: §1 · p. 37
• The bound on ∥F_T(s) − I∥ uses Lemma 6 and the definition of F_T(s).Source: §1 · p. 37

2. Off-diagonal term

• The off-diagonal-term estimate uses summation by parts and norm and unitarity properties to control its error.The derivation invokes Lemma 14 and uses that projectors and unitaries have spectral norm 1 and Y_T is unitary.Source: §2 · pp. 37–38
• Bounds for X(s), ˜X(s), Z(s), and DY(s) are assembled from the cited lemmas to bound the off-diagonal term.The derivation uses Lemmas 8 and 6 for X(s), Lemma 12 for ˜X(s), Lemma 13 for Z(s), and Lemma 11 for DY(s).Source: §2 · pp. 38–39
• The Z(s) bound first controls DX(s) and DVT(s −1/T), then substitutes bounds for these terms and X(s).The derivation uses Lemmas 9 and 6 and the functions GT,2, GT,3, and GT,4.Source: §2 · pp. 38–39

3. Upper bounds for the functions of Theorem 15

• Assuming T ≥ max(4ĉ1(s)/ˇΔ(s)), the function bounds are substituted into Theorem 15 to obtain the error bound used in the paper.The derivation also uses 1 − cos(θ/2) ≥ θ^2/π^2 for 0 ≤ θ ≤ π.Source: §3 · pp. 39–40

Appendix E: Block encoding of H(s)

• The block encoding assigns four ancilla qubits to selecting blocks in A(f), combining σz ⊗ I with A, implementing Qb, and selecting blocks in H(s).The construction uses a block-encoding unitary UA for A and an oracle Ub for preparing |b⟩.Source: Appendix E · p. 41
• The construction forms the block encoding using selected UA operations and a projector construction for Qb.It uses ancilla a2 to select the terms of A(f), and ancilla a4 to block encode the projector used for Qb.Source: Appendix E · p. 41
• The H(s) sequence applies controlled Qb before and after A(f(s)), with controlled rotations and ancilla operations to select the required terms.The listed sequence includes the Hadamard operations, controlled Qb operations, rotations, UA(f), and a final σx on a4.Source: Appendix E · pp. 41–42
• The complete block-encoding operation is self-inverse, as required for qubitisation.The argument uses that each operation is self-inverse and that the control can be switched between 0 and 1 by flipping a4.Source: Appendix E · p. 42

Appendix F: Upper bounds of Theorem 3 with p = 3/2

• The proof splits the bound into three terms without sums, sums involving c1, and a sum involving c2, replacing the three gaps with their minimum.The replacement uses the minimum gap defined in Eq. (14).Source: Appendix F · p. 43
• Monotonicity of f and its derivatives supports the bounds: f′ is positive and decreasing, f′′ is negative with decreasing magnitude, and f′′′ is positive.These properties let the c1 and c2 bounds use larger differences at smaller s.Source: Appendix F · p. 43
• The block-encoding walk operator has a gap at least as large as the Hamiltonian gap because the eigenvalue mapping applies arcsine to the gap.The solution eigenvalue 0 maps to ±1, while Hamiltonian eigenvalues map to ±e^±i arcsin λ.Source: Appendix F · p. 43

1. Single components

• αn = O(√κ/T) for the first single-component term, under the condition T > κ.This is the bound reported as Eq. (144).Source: §1 · p. 43
• At s = 1, the gap is 1/κ and c1(1) = 2(1 − f(1 − 1/T)), yielding the upper bounds reported in Eqs. (145) and (146).The two bounds use different powers of the endpoint gap.Source: §1 · p. 44

2. c1(s) summations

• 16κ/T^2 is the leading-order upper bound for each term in the c1 sum, yielding the total bound reported in Eq. (147).The sum runs from n = 1 to T − 1.Source: §2 · pp. 44–45
• 16/T^2 is the leading-order bound for each term in the second c1 sum except n = 0, yielding the total bound reported in Eq. (148).The endpoint cases s = 1 − 1/T and s = 1 − 2/T are also upper-bounded.Source: §2 · pp. 45–46

3. c2(s) summation

• The T − 1 terms are each upper bounded by 22κ/T^2 to leading order, giving the Eq. (149) bound.The proof uses Eqs. (F2) and (F4) for 1 ≤ s ≤ 1 − 3/T and treats s = 1 − 1/T separately.Source: §3 · pp. 46–47

Appendix G: Phase factors in the adiabatic evolution

• The discrete adiabatic theorem applies separately to the ±1 eigenvalue groups, so their superposition evolves correctly despite the separated spectral parts.Source: Appendix G · p. 47
• The positive superposition of the ±1 walk eigenstates yields the solution state, so adiabatic evolution must preserve their relative phase.Source: Appendix G · p. 47
• Exact adiabatic evolution cannot switch between orthogonal eigenstates in the spectrum of interest, preventing solution-state leakage into the non-solution state.Source: Appendix G · pp. 47–48
• Successive-step overlaps may contribute a phase, but it is identical for the +1 and −1 eigenvectors; an even step count cancels sign flips.The schedule can be slightly adjusted to make the number of steps even without changing the asymptotic scaling.Source: Appendix G · p. 48
• The walk method applies beyond linear systems when the Hamiltonian's target eigenvalue is zero, or is known and can be shifted to zero.Source: Appendix G · p. 48

• The proof relates finite-difference coefficients to continuous schedule derivatives, whose gap dependence cancels denominators in the error bound.Source: Appendix H · pp. 48–49
• To resolve the different-time-point issue in the error estimate, the lemma bounds the spectrum-gap ratio by ∆0(s)/∆0(s + 4/T) ≤ 4/3.Source: Appendix H · pp. 49–50
• The proof bounds gap-power sums by approximating their Riemann sums with integrals and controlling discretization errors; monotonicity also covers p = 1.5, when 2p − 3 = 0.Source: Appendix H · pp. 51–53
• T = O(κ/ϵ) follows because each term in the adiabatic error bound can be bounded by O(κ/T).Source: Appendix H · p. 54

Appendix I: Additional details for filtering

• With the filter zero on the desired spectrum and initial desired-spectrum probability at least 1/2, the proof bounds the normalized desired probability and the norm difference from the desired state.The derivation separates desired and undesired spectral components before applying the initial-probability assumption.Source: Appendix I · pp. 54–55
• A pair of controlled rotations followed by projection onto 1 on the first ancilla maps the remaining qubit amplitudes to the filtering weights.For an eigenstate target, the resulting |0⟩ component has the desired weights, while |1⟩ flags the remainder of the linear combination still to be obtained.Source: Appendix I · pp. 55–56