PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal scaling quantum linear systems solver via discrete adiabatic theorem

Pedro C. S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, Dominic W. Berry

arXiv:2111.08152v1quant-ph

TL;DR

Quantum linear system algorithms had not achieved optimal scaling in the condition number κ while retaining logarithmic precision dependence. The paper rigorously analyzes discrete adiabatic evolution and combines it with improved filtering, obtaining complexity O(κ log(1/ϵ)) and simpler implementation. This matches the known lower bound in the combined κ and ϵ scaling.

  • Problem

    The open problem was achieving optimal κ-scaling in QLSP while retaining the logarithmic dependence on solution precision ϵ.

  • Method

    The paper proves a discrete adiabatic theorem with explicit spectral-gap dependence and combines qubitised quantum walks with an improved eigenstate-filtering method.

  • Results

    O(κ log(1/ϵ)) complexity achieves strictly linear κ-scaling and matches the known lower bound for combined κ and ϵ dependence.

  • Takeaways & Limitations

    The approach provides an asymptotically optimal QLSP algorithm that avoids variable-time amplitude amplification and is simpler to implement than prior methods.

Abstract

from arXiv · show

Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number $κ$ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of $\log(κ)$. Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete time evolutions. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in $κ$, matching a known lower bound on the complexity. Our $\mathcal{O}(κ\log(1/ε))$ complexity is also optimal in terms of the combined scaling in $κ$ and the precision $ε$. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications.

I. INTRODUCTION

The paper addresses the unresolved challenge of achieving optimal condition-number scaling for quantum linear system solving. It introduces a rigorously analyzed discrete adiabatic approach combined with simpler eigenstate filtering to obtain a linear-system algorithm with optimal scaling.

  • Problem setting: QLSP prepares a quantum state proportional to the solution of Ax = b, with complexity depending chiefly on the condition number κ and error ϵ under the paper’s oracle assumptions.The analysis assumes ∥A∥ = 1, block-encoding access to A, and an operation preparing |b⟩.
  • Prior work: Previous methods improved κ-scaling but either used variable-time amplitude amplification or remained suboptimal by a logarithmic factor in κ.Earlier approaches achieved near-linear κ dependence or logarithmic precision dependence, but did not simultaneously provide optimal κ-scaling with a simple procedure.
  • Algorithm: The resulting algorithm combines qubitised quantum-walk steps with improved eigenstate filtering and avoids variable-time amplitude amplification and truncated Dyson-series evolution.The filtering sequence is efficiently determined without the numerically demanding rotation-search procedure used in prior singular-value-processing methods.
  • Core insight: The paper proves a discrete quantum adiabatic theorem that explicitly tracks spectral-gap dependence, correcting a key omission in the earlier DKS analysis.This matters because the QLSP spectral gap depends on κ, and the paper derives the error scaling needed to determine κ-dependence.
  • Analysis: The paper develops rigorous discrete adiabatic-theorem bounds, including a simplified theorem and explicit conditions on the smoothness of the walk operators.It presents two theorem forms and notes that higher-order differences may be required for applications.

III. THE FIRST ADIABATIC THEOREM

The section constructs the discrete adiabatic framework by comparing actual and ideal walk evolutions through spectral projectors, ripple operators, and a wave operator. A discrete summation-by-parts argument then organizes the error analysis.

  • Proof strategy: The proof bounds the accumulated kernel using discrete summation by parts, separating diagonal and off-diagonal terms.The off-diagonal terms require the summation-by-parts formula, while the diagonal terms are bounded directly.
  • Adiabatic operators: The adiabatic walk operator W_T^A(s) and evolution U_T^A(s) are constructed from unitary operators that preserve the relevant spectral subspaces.The corresponding identities relate the projected actual walk to the adiabatic walk.
  • Operator definitions: The wave operator measures the difference between the actual evolution U_T(s) and ideal adiabatic evolution U_T^A(s).The goal is to show that Ω_T(s) remains close to the identity.
  • Wave and ripple operators: A ripple operator decomposes the wave operator into one-step contributions, whose kernel should be small for near-adiabatic evolution.The resulting wave operator is a product of ripple operators over the discrete time steps.

D. Bounding the operators

This section bounds finite differences of spectral projectors and auxiliary adiabatic operators using contours that remain separated from the spectrum across successive walk steps. These estimates feed into bounds for the kernel and the summation-by-parts terms.

  • Spectral contours: Contours Γ_T(s,k) enclose the spectrum of interest across k+1 successive walk steps while remaining separated from the complementary spectrum.For multiple steps, the contour must be common to the relevant spectra and preserve a gap between eigenvalue groups.
  • Projector bounds: Finite differences of P_T and higher differences are bounded from corresponding differences of W_T.These projector estimates provide the starting point for controlling changes in the auxiliary operators.
  • Auxiliary operators: V_T(s)=F_T(s)[I+D P_T(s)(2P_T(s)−I)] expresses the auxiliary unitary V_T in terms of the spectral projector.This representation enables bounds on V_T−I and its finite difference.
  • Auxiliary operators: The norms of A, B, and Z are bounded using contour integrals, projector differences, and differences of the operator sequences.The resulting estimates include explicit dependence on the spectral gaps and T.
  • Summation by parts: The corrected summation-by-parts formula combines the operator bounds to control the off-diagonal contribution to the adiabatic error.The authors correct a sign typo in the corresponding theorem of Ref..

E. The first discrete adiabatic theorem

The first discrete adiabatic theorem gives an explicit gap-dependent error bound for products of slowly varying unitary walk operators. Its proof controls diagonal and off-diagonal contributions through the previously developed operator estimates.

  • Theorem statement: The theorem considers a product of unitary walk operators W_T(l/T) and compares its evolution with the corresponding ideal adiabatic evolution.The ideal evolution maps an eigenstate of W_T(0) to the corresponding eigenstate at time s.
  • Theorem statement: The theorem assumes bounded first and second discrete differences of W_T(s), spectral gaps Δ_k(s), and T≥max_s(2c_1(s)/Δ_1(s)).The smoothness and gap conditions specify when the discrete evolution changes sufficiently slowly.
  • Proof: The proof splits the error into diagonal and off-diagonal terms.The diagonal terms are bounded directly, whereas the off-diagonal terms use the discrete summation-by-parts formula.
  • Proof: The diagonal bounds are obtained symmetrically for the eigenspace of interest and its complementary eigenspace.The same estimate applies with P_T replaced by Q_T.
  • Proof: The overall error bound follows by combining the diagonal and off-diagonal estimates with bounds on the auxiliary functions and operators.The final bound is assembled from the preceding lemmas.

F. Proof of the second adiabatic theorem

The second theorem is obtained by simplifying the first theorem’s bound with neighboring-step gaps and stronger conditions on T. The resulting framework is applied to quantum linear systems using Hamiltonian interpolation, gap-aware scheduling, and qubitised walks.

  • F. Proof of the second adiabatic theorem: The simplified theorem replaces c_1(s) and c_2(s) with neighboring-step quantities and replaces Δ_k(s) by the minimum neighboring-step gap ˇΔ(s).Higher-order terms are bounded by lower-order terms under T≥max_s(4ĉ_1(s)/ˇΔ(s)).
  • F. Proof of the second adiabatic theorem: The proof bounds the functions D_k and G_T,k on the restricted range implied by the stronger assumption on T.It uses trigonometric inequalities to express the bounds in terms of the gap.
  • Application to quantum linear systems: The linear-system construction interpolates between H_0 and H_1 so that the final ground state encodes the normalized solution A^-1|b⟩/∥A^-1|b⟩∥.The schedule function f(s) controls the interpolation from the easily prepared initial ground state to the solution state.
  • Application to quantum linear systems: The schedule is monotone increasing with monotone decreasing derivative, slowing the evolution as the spectral gap becomes small.For Hermitian positive-definite systems, the gap is bounded using the condition number κ.
  • Application to quantum linear systems: For non-positive-definite Hermitian systems, enlarging the Hilbert space with two ancilla qubits supports a corresponding gap bound.The solution is obtained by preparing the zero-energy state of H_0.
  • Application to quantum linear systems: For non-Hermitian A, replacing σ_x⊗A with A yields the same lower bound on the gap without further expanding the dimension.The construction uses a symmetric block encoding for qubitisation.
  • Implementation: Qubitised quantum-walk implementation avoids the logarithmic complexity factor associated with Dyson-series simulation of continuous Hamiltonian evolution.Block encodings of H_0 and H_1 are selected using an ancilla-qubit rotation.

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

The walk-operator variation is bounded through the scheduling rotation R(s), yielding explicit choices for c1(s) and c2(s) in the discrete adiabatic theorem.

  • The dependence of W_T(s) on s enters through the rotation R(s), so differences of walk operators can be bounded using differences of R(s).
  • The resulting bounds are selected so that W_T(s) satisfies the first- and second-difference conditions required by Definition 1.
  • The derivative norm of R with respect to f is bounded by 2, while its exact norm varies between 1 and 2.
  • Taylor expansion in two directions is used to bound the second difference of the walk operator and determine c2(s).

C. Linear κ for p = 3/2

For p = 3/2, the discrete adiabatic analysis establishes linear dependence on κ, which combines with filtering to give an overall O(κ log(1/ε)) QLSP algorithm.

  • C. Linear κ for p = 3/2: The p = 3/2 schedule is chosen to estimate constant factors because continuous AQC achieves κ/ε scaling for all 1 < p < 2.
  • C. Linear κ for p = 3/2: T ≥ κ walk steps suffice for the positive-definite Hermitian case, with the error bound obtained by summing six terms from the discrete adiabatic theorem.
  • C. Linear κ for p = 3/2: For general matrices, the spectral-gap bound introduces an additional factor into the corresponding error terms.
  • D. General p: Theorem 18 extends linear κ dependence to every 1 < p < 2, while its general proof produces a larger prefactor than the direct p = 3/2 analysis.
  • E. Numerical Results: The numerical error is approximately linear in κ, with the smallest observed error at p = 1.3; for p = 3/2, the estimated scaling is ∥U_T(s) − U^A_T(s)∥ ≲ 638κ/T.
  • V. Filtering for solving linear equations: Filtering uses a linear combination of unitaries that matches singular-value-processing efficiency, requires two ancilla qubits, and has an easily determined gate sequence.
  • V. Filtering for solving linear equations: The combined adiabatic and filtering procedure has complexity O(κ log(1/ε)); numerically, the adiabatic stage may require about 834κ steps.

VI. CONCLUSIONS

The paper develops a discrete-time adiabatic QLSP algorithm that achieves optimal condition-number scaling while avoiding prior continuous-time simulation overheads. It also identifies optimal combined scaling in condition number and precision, while leaving sparsity scaling as an open question.

  • VI. CONCLUSIONS: The algorithm directly discretizes adiabatic evolution with quantum walks, replacing the Dyson-series subroutine required for precise time-dependent Hamiltonian evolution.Its error is controlled using a discrete adiabatic theorem with new rigorous bounds.
  • VI. CONCLUSIONS: The result is of fundamental interest because it asymptotically matches the lower bound and may matter for future practical implementations of QLSP on error-corrected quantum computers.The authors therefore foresee practical value in the improved scaling.
  • VI. CONCLUSIONS: The algorithm achieves optimal scaling in the condition number and precision, matching the lower bound O(κ log(1/ϵ)).The logarithmic precision factor arises from filtering, while the initial adiabatic step is lower-complexity in practice.
  • VI. CONCLUSIONS: The paper leaves open the sparsity dependence when sparse matrices are accessed through nonzero-entry oracles rather than block-encoding queries.The stated complexity is in block-encoding calls, and obtaining the lower-bound sparsity factor depends on more efficient block encodings.
  • VI. CONCLUSIONS: The tighter discrete adiabatic analysis may also benefit other quantum algorithms based on continuous-time evolutions, including adiabatic optimization algorithms.The paper states that its analysis is tighter than prior discrete adiabatic analyses.

Appendix A: List of variables

The appendix defines notation for discrete walk operators, spectra, gaps, projectors, evolution operators, proof quantities, and QLSP-specific variables. It also specifies contour constructions and the block-encoding ingredients used in the analysis.

  • Appendix A: List of variables: WT(s) denotes the discrete walk operator, with s=n/T indexing discrete adiabatic time and T the number of walk operators.T* is a lower bound used in the definition of the gap condition.
  • Appendix A: List of variables: PT(s) and QT(s) project onto the spectra of interest and complementary spectra, while UT(s) is the product of actual walk operators.UA_T(s) and WA_T(s) denote ideal adiabatic evolution and ideal eigenstate-preserving walk operators.
  • Appendix A: List of variables: D and D(k) denote first and iterated difference operators, while ck(s) and ĉk(s) bound walk-operator differences.These quantities measure variation across discrete time steps.
  • Appendix A: List of variables: σP(s) and σQ(s) are the spectra of interest and complementary spectra, with Δk(s) and Δ(s) denoting gaps across successive steps.Δ̌(s) accounts for neighboring steps.
  • Appendix A: List of variables: The proof uses resolvents, contours, polar-decomposition unitaries, wave and ripple operators, kernel functions, and auxiliary quantities A(s), B(s), and Z(s).ΓT(s,k) encloses the spectrum of interest across k+1 successive walk steps.
  • Appendix A: List of variables: For QLSP, A is the coefficient matrix, κ its condition number, ϵ the allowable error, and |b⟩ the state encoding the input vector.The appendix also defines the Hermitian construction, interpolation Hamiltonian, scheduling variables, and filtering weights.
  • Appendix A: List of variables: The contour-integral analysis uses resolvent distance from the spectrum to bound projector differences and related terms.The resolvent is associated with WT(s), and the contour is separated into radial and arc components.
  • Appendix A: List of variables: The contour ΓT(s,1,a) passes through the two spectral gaps and closes with an arc of radius a+1; taking a→∞ removes the arc contribution for difference terms.For second-order differences, ΓT(s,2) passes through the gap over three consecutive steps.

Appendix C: Proof of Lemma 14

The proof of Lemma 14 rewrites projector and evolution relations using discrete differences, then sums them while isolating boundary, diagonal, and off-diagonal contributions. Correction terms account for endpoint mismatches in the finite discrete sum.

  • Appendix C: Proof of Lemma 14: The proof begins from an identity expressing a commutator with the projector PT(s) and the auxiliary operator X(s).The identity is combined with the definition of the ideal adiabatic walk operator.
  • Appendix C: Proof of Lemma 14: Substituting PT(s)=UA_T(s) into the identity introduces the auxiliary operators A(s) and B(s) used in the subsequent bound.These quantities organize the discrete adiabatic evolution terms.
  • Appendix C: Proof of Lemma 14: Summation by parts converts the discrete evolution relation into a finite sum involving a boundary correction B for the initial and final indices.The correction accounts for the extra term at n=0 and the missing term at n=l.
  • Appendix C: Proof of Lemma 14: The resulting expression separates terms that are later bounded as diagonal and off-diagonal contributions.The proof then treats the diagonal term after projecting onto P0 and uses relations among neighboring projectors.
  • Appendix C: Proof of Lemma 14: For projector products, the proof uses the projection identity p(p−q)p=p(p−q)^2p and bounds FT(s)−I using an earlier lemma.These steps control the remaining correction terms in the discrete estimate.

2. Off-diagonal term

The off-diagonal-term analysis bounds discrete differences of auxiliary operators and then assembles them into an explicit estimate. The implementation section constructs a self-inverse block encoding of H(s) from the matrix and input-state oracles.

  • 2. Off-diagonal term: The off-diagonal bound is developed by bounding X(s), its contour-integral transform, Z(s), and the discrete derivative of the wave operator.These bounds are combined through previously established lemmas and summation by parts.
  • 2. Off-diagonal term: The analysis uses GT,j(s) functions to replace bounds on discrete differences of X(s), VT(s−1/T), and related operators.The functions organize explicit dependence on the discrete evolution quantities.
  • 2. Off-diagonal term: The estimates assume T≥max(4ĉ1(s)/Δ̌(s)) and use trigonometric gap inequalities to obtain explicit bounds.These bounds are inserted into the main theorem to produce the final off-diagonal estimate.
  • 2. Off-diagonal term: The block encoding of H(s) combines a block encoding of A, controlled applications of Qb, rotations, and the state-preparation oracle for |b⟩.The sequence selects between A(f(s))Qb and QbA(f(s)) using controlled operations.
  • 2. Off-diagonal term: The resulting block-encoding sequence is self-inverse, as required for qubitisation, because its component operations are self-inverse and cancel under composition.The construction uses four ancilla qubits in addition to the block-encoding ancillas.
  • 2. Off-diagonal term: The complete construction uses Hadamards, controlled Qb operations, controlled rotations, UA(f), and a final ancilla bit flip.The listed sequence contains eight operations.

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

For p = 3/2, the appendix bounds the discrete adiabatic theorem’s error terms by analyzing endpoint contributions and finite sums involving the spectral gap. These estimates provide explicit upper bounds used in the complexity analysis.

  • Gap and coefficient bounds: The analysis replaces the theorem’s three gaps with their minimum and uses monotonicity properties of the schedule function and its derivatives.The relevant properties are f′(s) > 0, f′′(s) < 0, and f′′′(s) > 0.
  • Boundary contributions: O(√κ/T) bounds the initial coefficient contribution when T > κ.This estimate is identified with Eq. (144) in the main text.
  • Boundary contributions: The endpoint estimates at s = 1 use the gap value 1/κ and produce the bounds reported in Eqs. (145) and (146).The two bounds differ in whether the endpoint gap appears squared.
  • Summation bounds: 16κ/T^2 bounds each term in one finite sum to leading order, yielding the total estimate reported in Eq. (147).The sum runs from n = 1 to T − 1.
  • Summation bounds: 16/T^2 bounds nearly every term in the second sum, with a separate treatment for n = 0, producing Eq. (148).There are T terms in the sum.

3. c2(s) summation

The c2(s) analysis controls finite-difference contributions in the discrete adiabatic evolution and verifies that qubitisation preserves the relevant spectral-gap behavior. It also resolves phase and eigenspace issues caused by walk eigenvalues at ±1.

  • c2(s) summation: The c2(s) bounds are evaluated separately near the endpoint and over the interior, with the final sum bounded by 22κ/T^2 per term to leading order.The endpoint cases s = 1 − 1/T and nearby points require separate estimates.
  • Phase factors: The solution and non-solution states occupy the two ±1 walk eigenspaces, so maintaining their positive superposition is necessary to recover the solution state.A negative superposition produces the non-solution state.
  • Phase factors: The exact adiabatic walk updates eigenstates through overlapping spectral projectors while cancelling the magnitude of successive-state overlaps, leaving only their phase.This construction prevents leakage between orthogonal eigenstates in the eigenspace of interest.
  • Phase factors: The successive-step inner product is independent of choosing the +1 or −1 eigenvectors, so both sectors acquire the same possible phase factor.An even total number of walk steps cancels the remaining sign flip.
  • Conclusion: The qubitised adiabatic walk therefore remains valid despite separated ±1 eigenvalues and can extend to Hamiltonians with another known eigenvalue after shifting it to zero.The argument uses no special Hamiltonian properties beyond the zero target eigenvalue.

Appendix H: Upper bounds of Theorem 18 with 1 < p < 2

Appendix H derives the error bound for discrete adiabatic evolution when 1 < p < 2 by relating finite differences to schedule derivatives and bounding gap-dependent sums. The resulting estimate implies T = O(κ/ε).

  • Proof strategy: The proof connects discrete finite-difference coefficients c_k(s) with continuous derivatives of the schedule function to establish linear κ-dependence.It also addresses the different discrete time points appearing in the adiabatic theorem.
  • Gap estimates: The spectrum gap is written as Δ0(s) = 1 − f(s) + f(s)/κ, and its variation over four time steps is bounded by Δ0(s)/Δ0(s + 4/T) ≤ 4/3.The proof uses monotonicity of the gap and schedule function.
  • Summation estimates: Riemann-sum estimates convert the gap-dependent summations into integrals plus difference terms, under the assumption that the relevant function remains positive.The functions used are powers of Δ0(t).
  • Summation estimates: The derivative calculations for powers of Δ0(t) provide the bounds needed for the two principal summation regimes, including the special case p = 1.5.Monotonicity determines whether endpoint or shifted terms bound each summand.
  • Final error bound: The proof collects boundary, finite-difference, and summation contributions into an explicit constant factor C_p in the adiabatic error bound.The constant is defined as the largest factor appearing in the resulting estimate.
  • Final error bound: T = O(κ/ε) follows because every term in the adiabatic error is bounded by O(κ/T).This is the second part of Theorem 18.

Appendix I: Additional details for filtering

The filtering construction uses controlled rotations and postselection to concentrate amplitude on the desired spectral subspace. Its error bound depends on the initial desired-subspace probability and the implemented rotation sequence.

  • Filtering bound: The filtering analysis assumes the filter vanishes on the desired spectrum and that the initial desired-subspace probability is at least 1/2.The squared norm of the undesired component is then bounded through the filtering transformation.
  • Filtering bound: The normalized desired-spectrum probability is lower bounded after filtering, and the norm distance from the desired state is then bounded from that probability.The lower bound uses the assumed initial probability condition.
  • Rotation sequence: The explicit implementation begins with a state-preparation rotation followed by controlled rotations applied across successive ancilla qubits.The appendix also considers the reverse order of the rotations.
  • Rotation sequence: Controlled rotations between neighboring ancilla qubits assign the desired weights while flagging the remaining linear combination on the |1⟩ state.The construction is described recursively for general qubit indices.
Loading 2111.08152v1…