Discrete adiabatic inversion

What it fills

• Quantum linear solve

  Given access to a matrix $A$ and a unitary that prepares $|b>$, produce a flagged quantum state that is $\varepsilon$-close in $l2$ to the normalised $A^{-1}b$. The deliverable is a state, not a classical vector.

When it applies

Needs the walk-operator (qubitization) form of access to the path Hamiltonians and a lower bound on the spectral gap along the path, which amounts to a known upper bound on $\kappa$. The authors' stated advantages are that the algorithm is simpler and easier to implement than the sub-optimal alternatives, and that the constant factors are determined, so gate counts can be worked out for a specific application.

Requires

These do not move the route along. The method needs each of them alongside its own work, and the cost of getting them is part of what the method costs.

• Prepare an input state

  Map $|0\ldots0⟩$ to a state whose amplitudes are proportional to a specified vector $b$, to within $\varepsilon$. The cost is set by which description of $b$ you hold, not by the algorithm that consumes it.

  This route uses the $|b>$ oracle $U_b$, with $U_b|0> = |b>$, in two places: to prepare the initial state $|0,b>$, which is the eigenvalue-zero eigenstate of $H_0$ that the walk is to carry to $|0, A^{-1}b>$, and to build the projector $Q_b = I_N - |b><b|$ from $U_b$ and $U_b^\dagger$, which sits inside every step's block encoding of $H(s)$. assumption: access to the oracles includes forward, reverse and controlled uses; only the reflection inside $Q_b$ has to be made controlled, not $U_b$ itself.

  assumption

Example

The run is a classical numerical simulation, and it covers the adiabatic half of the algorithm only: the walk is simulated and its output state compared against the ideal solution, while the filter of Section 4 is costed by formula and never executed, so every error quoted here is the adiabatic error $\Delta = \| |\tilde{x}\rangle - |x\rangle \|$ and not the final $\varepsilon$. For each condition number $\kappa \in \{10, 20, 30, 40, 50\}$, Costa, An, Babbush and Berry drew 100 independent random $16 \times 16$ non-Hermitian matrices, used the schedule function of the 2021 paper at $p = 1.4$, and measured complexity as the number of calls to the block encoding, which is the number of walk steps. Holding the step count fixed across all 100 instances at each $\kappa$, chosen so the root-mean-square error over those instances comes as close to $0.4$ as it can without exceeding it, gives 36 steps at $\Delta = 0.348$ for $\kappa = 10$, then 76 at $0.381$, 120 at $0.400$, 176 at $0.399$, and 232 steps at $\Delta = 0.397$ for $\kappa = 50$ (Table 1). Reading that last row through $T = \alpha \kappa / \Delta$ is where the practical constant $\alpha = 1.84$ comes from, about 1,250 times smaller than the $\alpha = 2305$ that this paper takes from page 16 of the published version of the 2021 work; the abstract rounds that ratio to about 1,200. The constant is not one number but a function of the target error: the same $\kappa = 50$ instances need 288 steps for $\Delta \approx 0.3$ and 344 for $\Delta \approx 0.2$, giving $\alpha = 1.66$ and $\alpha = 1.37$ (Table 3). Two application matrices from the SuiteSparse collection, both $32 \times 32$ and non-Hermitian, were run the same way: a directed graph (ID 168) with $\kappa = 4.041 \times 10^2$ reached $\Delta = 0.398$ in $2.416 \times 10^3$ walk steps, and a circuit simulation problem (ID 1199) with $\kappa = 6.302 \times 10^5$ reached $\Delta = 0.399$ in $3.980 \times 10^4$ steps (Table 2). Against the randomised solver on the same instances the walk is between 7.42 and 8.03 times cheaper on the random $16 \times 16$ matrices, though the comparison sets walk steps against the randomised method's total evolution time, which the authors argue lower bounds its true cost rather than equalling it. For the two SuiteSparse matrices Table 2's own ratio column gives 9.58 and 457, while the running text of Section 3.2 says 9.2 and 4.0 for those same two cases; this record transcribes both and reconciles neither.

Classical simulation · Tables 1-3 and Section 3.2 of arXiv:2312.07690

given  the walk-operator (qubitization) form of access to the path
       Hamiltonians and a lower bound on the spectral gap along the
       path, which amounts to a known upper bound on kappa

encode the solution as the null eigenstate of a Hamiltonian path built
    from A and |b>

follow that path with a sequence of qubitization walk operators to fixed
    precision
    # the record does not state how many walk operators that sequence
    # contains, only the complexity below

finish with an eigenstate filter implemented as a linear combination of
    walk operators
    # rather than by quantum signal processing

# the authors' framing is that the adiabatic route reaches near-linear
# kappa without a complicated variable-time amplitude amplification
# procedure

# O(kappa log(1/epsilon)) -- strictly linear in kappa, matching a known
# lower bound on the complexity, and also optimal in the combined
# scaling in kappa and the precision epsilon. The adiabatic theorem
# proved here is for intrinsically discrete-time evolutions, which is
# what removes the residual log(kappa) that continuous adiabatic
# treatments carried.

# the authors' stated advantages: the algorithm is simpler and easier to
# implement than the sub-optimal alternatives, and the constant factors
# are determined, so gate counts can be worked out for a specific
# application

# and yet constant factors in this family are unsettled. Numerical
# testing on random matrices reports this solver's constant factor about
# 1,200 times smaller than the published upper bound, and about an order
# of magnitude better than the randomized adiabatic approach of
# arXiv:2305.11352 -- but against the 2023 version of that work, whose
# published 2025 version postdates it. The ranking rests on a 2023
# comparison.

Cost, as the source states it

Costa, An, Sanders, Su, Babbush and Berry state a complexity of $O(\kappa \log(1/\varepsilon))$ — strictly linear in $\kappa$, matching a known lower bound on the complexity, and also optimal in the combined scaling in $\kappa$ and the precision $\varepsilon$. Their framing is that the adiabatic route reaches near-linear $\kappa$ without a complicated variable-time amplitude amplification procedure.

Implementations

• Discrete-adiabatic QLSP solver, classical simulation in MATLAB

  • The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver

  Built to settle a costing question rather than a correctness one. The upper bound proved from the discrete adiabatic theorem combines several separate approximations, and the constant it yields for $T = \alpha\kappa/\Delta$ is loose enough that the authors say it serves only for a rough estimate of the walk steps a given error needs. A competing randomised solver had been given a tighter bound and argued on that basis to be faster in practice, so both were run on the same matrices to find out what each actually costs.

  The interpolating Hamiltonian $H(s) = (1-f(s))H_0 + f(s)H_1$ is block encoded by selecting between block encodings of $H_0$ and $H_1$ under a one-qubit rotation $R(s)$, and a reflection turns that into the qubitised walk operator. The non-Hermitian case doubles the dimension by embedding $A$ in a Hermitian matrix carrying $A$ and $A^\dagger$ off the diagonal, and uses four further ancillas beyond the one the block encoding of $A$ needs: one selecting between the blocks of $A(f)$, one preparing the combination of $\sigma_z \otimes I$ and $A$, one implementing $Q_b$, and one selecting between the blocks of $H(s)$, of which the first and last count as part of the system the Hamiltonian acts on. The schedule is the family $\dot f(s) = d_p \Delta_0^p(s)$ of the 2021 paper, taken at $p = 1.4$. Two protocols are run: for the figures the step count is raised gradually until the norm distance between the actual and the ideal state falls below the target $\Delta = 0.4$, and for the tables a single step count is applied to all 100 instances at a given $\kappa$ and chosen to bring the root-mean-square error as close under $0.4$ as it will go. The filtering stage is not simulated at all; Section 4 costs it analytically from $\kappa \ln(2/\varepsilon_f)$ together with the repetition factor $[1-\delta(1-\varepsilon_f^2)]^{-2}$, where $\delta = \Delta^2 - \Delta^4/4$.

  For the random tests, 100 independently generated matrices per condition number at $\kappa = 10, 20, 30, 40, 50$, in dimensions $4 \times 4$, $8 \times 8$ and $16 \times 16$, in a Hermitian positive-definite family and a general non-Hermitian family; the paper reports that dimension does not significantly alter the complexity, as theory expects. How those matrices are generated is not stated in the text and lives only in the source code. For the application cases, two non-Hermitian $32 \times 32$ matrices from the SuiteSparse Matrix Collection of Davis and Hu, a directed graph with ID 168 and a circuit simulation problem with ID 1199, the collection recorded as accessed on 2024-10-23.

  Reference 15 of the paper is a public GitHub repository, PcostaQuantum/QLSP-via-discrete-adiabatic-method, holding MATLAB scripts; the citation points at the file Walk_error_Herm.m inside it and records access on 2025-01-24. The randomised solver used as the comparison arm has a separate repository of its own, cited as reference 17, which is code for that other method and not for this one.

  Nothing was run on quantum hardware and no quantum simulator backend is named: the reported complexity is a count of block-encoding calls read off a classical computation of the state. For non-Hermitian $16 \times 16$ matrices the practical constant is $\alpha = 1.84$ at $\kappa = 50$ and a target error of $0.4$, which the paper places about 1,200 times below the published upper bound's constant. The positive-definite case is far cheaper again, 4 to 24 walk steps across the same range of $\kappa$, which Section 4 reads as $\alpha = 0.17$. The walk beats the randomised method by factors of 7.42 to 8.03 on the random non-Hermitian instances, and the scatter plots record that across every instance tested there was no case where the randomised method surpassed the walk, the maximum cost of the walk staying below the minimum cost of the randomised method at fixed condition number and matrix type. Because the walk's advantage is measured as steps against evolution time, the authors state it would grow further once the cost of implementing that time evolution is included.

• Original construction with determined constant factors

  • Optimal scaling quantum linear systems solver via discrete adiabatic theorem

  The paper that defines the method, and it is written to be implementable rather than only asymptotic. Costa, An, Sanders, Su, Babbush and Berry prove an adiabatic theorem for intrinsically discrete time evolutions and build the linear-systems algorithm directly on the walk operator, which is what removes the Dyson-series overhead the continuous adiabatic treatments carried. Beyond the scaling, its stated aim is to determine the constant factors in the algorithm so that complexity can be worked out in terms of gate counts for a specific application.

  Block encodings of $H_0$ and $H_1$ are combined into one of $H(s)$, and a reflection on the ancillas turns it into the walk operator $W_T(s)$. The schedule obeys $\dot f(s) = d_p \Delta_0^p(s)$ with $1 < p < 2$, and the theorems are proved at $p = 3/2$. Filtering is by a linear combination of walk steps rather than by singular value processing: the window is the Chebyshev polynomial $\tilde{w}(\varphi) = T_\ell(\beta \cos \varphi)$ with $\beta = \cosh(\ell^{-1} \cosh^{-1}(1/\varepsilon))$, and matching its width to the gap $1/\kappa$ gives $\ell \le \kappa \ln(2/\varepsilon)$ calls to the block-encoded matrix, against $2\ell$ for the singular-value-processing filter. The price is one extra ancilla, two rather than one, and the advantage claimed for it is that the gate sequence is much simpler to determine than the rotation angles quantum signal processing needs.

  A Hermitian positive matrix, with the error bound evaluated as a function of the condition number and of the schedule exponent $p$ at a fixed number of walk steps. No instance ensemble and no matrix collection enter it: the quantity computed is an operator-norm bound, not a solution error measured over samples.

  The arXiv v1 read here publishes no source artefact and names no repository. The only published code for this solver is the MATLAB repository recorded on the other implementation.

  Its numerics measure a bound rather than a run, and this record says so plainly instead of dressing it up. Rather than taking the upper bounds on the first and second differences of the walk operator, the authors compute $\|DR\|$ and $\|D^{(2)}R\|$ exactly to fix the coefficients $c_1(s)$ and $c_2(s)$ in their error theorem, and evaluate the resulting bound at a fixed $T = 5 \times 10^4$ walk steps. The bound comes out approximately linear in $\kappa$, which is what makes the overall complexity linear in $\kappa$; at $\kappa = 40$ it is smallest at $p = 1.3$, below the $p = 3/2$ the theorems use. At $p = 3/2$ the fitted bound is $\|U_T(s) - U_T^A(s)\| \lesssim 638\kappa/T$, about nine times smaller than the constant the corresponding theorem proves. The paper reads $638$ as needing roughly $834\kappa$ walk steps to keep the probability on the spectrum of interest at least $1/2$, against a filter factor $\ln(2/\varepsilon)$ of only about 20 at an $\varepsilon$ of one part in a billion, and concludes that there is over an order of magnitude between its numerics and its analytically proven scaling constants.

What it needs

1. Block-encode a matrix 4 methods

   Wrap an operator $A$ inside a larger unitary $U$ so that $A/α$ sits in $U$'s top-left block, giving every routine above it one uniform way to touch the matrix. The subnormalization $α$ and the ancilla count are outputs of this layer, not free parameters.

2. Matrix function 2 methods

   Given a block-encoding of $A$ and a target function $f$ bounded on $[-1,1]$, produce a circuit whose designated block is an $\varepsilon$-approximation of $f$ applied to the singular values (or eigenvalues) of $A$.

Other ways to fill the same slot

Different approaches

• HHL: eigenvalue inversion by phase estimation

  Prepare $|b>$, run phase estimation against $e^{-iAt}$ to write eigenvalue estimates into an ancilla register, apply a controlled rotation with amplitude proportional to $1/λ̃$, uncompute the estimation and post-select on the rotation ancilla. The success amplitude is about $1/κ$, so the procedure is amplified $O(κ)$ times.

• QSVT matrix inversion

  Block-encode $A$, apply the quantum singular value transformation with an odd polynomial approximating a scaled $1/x$ away from the origin, then amplify. Because it acts on singular values, $A$ need not be Hermitian or sparse — only block-encodable.

• Chebyshev LCU inversion

  Expand an approximation of $1/x$ in Chebyshev polynomials and implement that expansion directly through the quantum walk associated with a sparse $A$, rather than through Hamiltonian simulation. Phase estimation is never used, which is what removes the $\mathrm{poly}(1/\varepsilon)$ bottleneck.

• Eigenstate filtering inversion

  Construct the minimax-optimal polynomial that is 1 at a target eigenvalue and uniformly small outside a spectral gap, and apply it through quantum signal processing. For a linear system $|x>$ is the null eigenstate of a Hamiltonian built from $A$ and $|b>$, so one application of the filter solves it once a starting state with non-trivial overlap is supplied.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• 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 · 2021theory yes · simulation yes · hardware no
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver↗Pedro C. S. Costa, Dong An, Ryan Babbush, Dominic Berry · 2023theory yes · simulation yes · hardware no