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.

An access model for $A$ — sparse row/column entry oracles, or a block-encoding; a unitary preparing $\lvert b\rangle$; a known upper bound $\kappa$ on the condition number; the normalisation $\lVert A\rVert \le 1$; and a target state error $\varepsilon$.

1. Linear system Ax = b → Block-encodingBlock-encode a matrix

   The slot must encode not $A$ alone but the path Hamiltonian $H(s) = (1-f(s))H_0 + f(s)H_1$, assembled from a block encoding $U_A$ with $<0|U_A|0> = A$, the $|b>$ oracle inside $Q_b$, four ancilla qubits, and a one-qubit rotation $R(s)$ — the only operation through which the step index $s$ enters. A reflection on the control qubits then turns that encoding into the walk operator $W_T(s)$. assumption: the block encoding must be symmetric and its operator sequence self-inverse, which is what qubitisation requires, and $U_A$ must be applicable in a selected way — either $U_A$, $U_A^\dagger$, or the identity. approximation: using $R(s)$ at the start and a Hadamard rather than $R(s)^\dagger$ at the end block-encodes $A(f(s))/\sqrt{2[(1-f(s))^2+f(s)^2]}$ in place of $A(f(s))$; that prefactor lies between $1/\sqrt{2}$ and $1$, and reduces the gap.

   approximationassumption

   Open this step

2. Block-encoding → Block-encoding of f(A)Matrix function

   What this slot supplies here is not an approximation of $1/x$ but a filter on the walk's eigenphases, applied as a linear combination of $\ell$ walk steps with weights $w_j$ prepared symmetrically before and after, giving $\tilde{w}(\phi) = \sum_j w_j e^{ij\phi} / \sum_j w_j$. approximation: the ideal filter is replaced by the Dolph–Chebyshev window $\tilde{w}(\phi) = T_\ell(\beta\cos\phi)$ with $\beta = \cosh(\ell^{-1}\cosh^{-1}(1/\varepsilon))$, which minimises the largest leakage, and the error of the filtered state is bounded by $\max_{k \in \perp} \tilde{w}(\phi_k)$ over the eigenphases outside the spectrum of interest. Setting the width of the peak equal to the gap $1/\kappa$ gives $\ell = \cosh^{-1}(1/\varepsilon)/\cosh^{-1}(1/\cos(1/\kappa)) \le \kappa\ln(2/\varepsilon)$, so the cost is $\ell$ calls to the block-encoded matrix rather than the $2\ell$ of the singular-value-processing filter, at the price of one extra ancilla qubit. assumption: the initial probability of the state on the spectrum of interest is at least $1/2$ — which is what running the preceding walk to a fixed precision is for.

   approximationassumption

   Open this step

3. Block-encoding of f(A) → Solution as a statewalk the eigenpath to the solution

   The eigenpath is $H(s) = (1-f(s))H_0 + f(s)H_1$, whose eigenvalue-zero eigenstate is carried from $|0,b>$ to $|0, A^{-1}b>$, and it is walked with $T$ qubitisation steps, $U_T(s) = \prod_n W_T(n/T)$, rather than simulated as a continuous evolution. The schedule satisfies $\dot{f}(s) = d_p \Delta_0^p(s)$, slowing the walk where the gap is small. approximation: $\Delta_0(s) = 1 - f(s) + f(s)/\kappa$ stands in for the exact gap — it is a lower bound, written as an equality — and for a general $A$ the relation $\sqrt{(1-f)^2 + (f/\kappa)^2} \ge (1 - f + f/\kappa)/\sqrt{2}$ is what lets the same schedule function be kept. The discrete adiabatic theorem then bounds the departure from the ideal path as $\|U_T(s) - U_T^A(s)\| \le 5632\,\kappa/T + O(\sqrt{\kappa}/T)$ for positive-definite Hermitian $A$ and $15307\,\kappa/T + O(\sqrt{\kappa}/T)$ for general $A$, so a fixed error is reached in $T = O(\kappa)$ steps. assumption: $\|A\| = 1$ with $\|A^{-1}\| = \kappa$, and $T \ge \kappa$ steps of the walk under the $p = 3/2$ schedule.

   approximationassumption

A flagged state $\varepsilon$-close in $\ell_2$ to $A^{-1}\lvert b\rangle/\lVert A^{-1}\lvert b\rangle\rVert$. It does not return $\lVert x\rVert$, any entry of $x$, or any classical functional of $x$ — those cost extra and are decided a layer above.

• 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

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.

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.

Constant factors in this family are unsettled. Costa, An, Babbush and Berry (arXiv December 2023; Quantum 9, 1887 (2025)) report numerical testing on random matrices showing the discrete adiabatic solver's constant factor is in practice 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 that comparison was made against the 2023 version of that work, whose published 2025 version postdates it. The ranking therefore rests on a 2023 comparison; the published Quantum version of the discrete-adiabatic benchmark still cites the 2023 preprint of the randomized solver.

• Discrete-adiabatic QLSP solver, classical simulation in MATLAB

  • 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 · 2023

  About

  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.

  Methods

  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$.

  Data

  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.

  Code

  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.

  Results

  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

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

  About

  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.

  Methods

  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.

  Data

  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.

  Code

  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.

  Results

  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.