Quantum Linear Algebra

The quantum linear-systems problem asks for useful information about the solution of $Ax=b$ when the coefficient matrix and right-hand side are exposed through specified coherent interfaces. For an invertible matrix, its standard quantum output is the normalized state

$$\lvert x\rangle := \frac{A^{-1}\lvert b\rangle} {\lVert A^{-1}\lvert b\rangle\rVert_2},$$

not a classical list of the entries of $x$. This distinction is decisive: a state can support selected observables, overlaps, samples, or a subsequent coherent computation, but reading all $N$ complex coordinates has an $\Omega(N)$-scale description burden even before precision is counted.

The algorithms on this page range from the phase-estimation construction of Harrow, Hassidim, and Lloyd to variable-time, Fourier/Chebyshev, singular-value-transformation, and discrete-adiabatic methods. Every comparison keeps the task, matrix and state access, normalization, condition number, output metric, success event, and counted oracle explicit. A matrix written on paper is not an executable coherent interface. Consequently, logarithmic dependence on $N$ is conditional on supplied access, and an oracle-query theorem is neither an end-to-end runtime theorem nor, by itself, an advantage theorem.

Required background. Quantum Phase Estimation supplies coherent spectral labeling, finite precision, and powered-control cost. Hamiltonian Simulation Algorithms supplies access-normalized controlled evolution and the qualifications needed to translate queries into executable resources.

Helpful background. The Quantum Algorithms and Complexity guide supplies the ten-field claim discipline. Algorithmic Primitives supplies reusable composition and amplitude processing. Singular Value Decomposition supplies singular values and the Moore–Penrose pseudoinverse, while Conditioning and Stability supplies sensitivity, residual, and forward-error concepts.

The Quantum Linear-Systems Problem

Begin with a finite-dimensional system

$$Ax=b, \qquad A\in\mathbb C^{N\times N}, \qquad b\ne0.$$

The data vector and the solution must be normalized separately:

$$\lvert b\rangle := \frac{b}{\lVert b\rVert_2}, \qquad \lvert x\rangle := \frac{A^{-1}\lvert b\rangle} {\lVert A^{-1}\lvert b\rangle\rVert_2}.$$

Multiplying $b$ by a nonzero scalar does not change either quantum state, and the solution-state output does not reveal $\lVert A^{-1}b\rVert_2$. A global phase is also unobservable. These facts make QLSP a state-preparation problem, not ordinary classical linear algebra with a different storage format.

If $N$ is not a power of two, use $n=\lceil\log_2N\rceil$ qubits and embed the system in a $2^n$-dimensional register. The algorithm must protect the unused subspace—for example, by defining an invertible extension with a separated spectrum and ensuring that preparation has no support on the padding basis states. Merely appending zero rows and columns would make the extended matrix singular and change the problem promise.

Throughout this page, successful output means a pure state satisfying the phase-aligned Euclidean guarantee

$$\min_{\varphi\in\mathbb R} \left\lVert \lvert\widetilde x\rangle -e^{i\varphi}\lvert x\rangle \right\rVert_2 \leq\epsilon,$$

conditional on a declared herald. A theorem must also give the heralding probability or adopt a stated constant-success convention and charge the amplification or repetition used to reach it. This metric is not interchangeable with a residual $\lVert A\widetilde x-b\rVert_2$, an operator error, infidelity, observable error, or entrywise classical error. Any translation needs its own inequality and hypotheses.

For a singular or rectangular matrix, $A^{-1}$ is not available. One must instead declare a singular-value cutoff, the input support, and whether the task prepares a truncated-pseudoinverse state or solves a specified least-squares problem. In particular, an inconsistent equation may not be silently redefined by projecting $b$ onto the column space.

The Ten-Field Quantum-Linear-Algebra Claim Record

A complexity formula becomes meaningful only as one field in a complete record. For a representative nonsingular QLSP theorem, the record reads as follows.

1. Problem family and size. Prepare a solution state for a family of $N\times N$ systems, with $n=\lceil\log_2N\rceil$ address qubits and the access, sparsity, conditioning, and precision parameters named separately.
2. Promise and instance. State whether $A$ is Hermitian, positive definite, square, or rectangular; give its spectral or singular-value interval, rank or cutoff, and the promised support of $\lvert b\rangle$.
3. Access and encoding. Supply executable matrix and right-hand-side interfaces, their normalizations and errors, plus every inverse and controlled use required by the procedure.
4. Output and use. Return a normalized state proportional to $A^{-1}\lvert b\rangle$ or to a declared pseudoinverse action, and name the observable, overlap, sample, decision, or coherent downstream operation.
5. Success and error. Give the phase-aligned Euclidean-state tolerance, heralding probability, allowed failure probability, confidence if measured, and the amplification or retry convention.
6. Algorithmic idea. Identify spectral inversion, polynomial filtering, singular-value transformation, or adiabatic transport as the mechanism; superposition is not simultaneous classical readout.
7. Executable procedure. Expand preparation, matrix calls, spectral or polynomial processing, inverses, controls, reflections, uncomputation, heralding, measurement, and stopping rule.
8. Resource ledger. Keep matrix-oracle calls, $U_b$ calls, successful preparations, logical gates, depth, width, ancillas, memory, preprocessing, synthesis, samples, classical work, and wall-clock cost in distinct units.
9. Classical comparator. Match matrix representation, right-hand-side access, preprocessing, conditioning, output, accuracy, success/confidence, memory, and included costs to a dated classical method.
10. Evidence and limits. Label an upper bound, lower bound, matching theorem, finite algebra audit, resource estimate, or frontier result, and state which costs and regimes it does not establish.

The record prevents a common category error: an upper bound under supplied oracles does not prove that those oracles are cheap to construct, nor that the state output answers a classical vector-output question. It also prevents a finite two-dimensional check from being cited as scaling evidence.

Matrix, Right-Hand-Side, and Block-Encoding Access

The right-hand side enters through a declared unitary

$$U_b\lvert0^n\rangle=\lvert b\rangle.$$

Whether $U_b^\dagger$ and controlled $U_b$ are available must be stated. An already-prepared copy of $\lvert b\rangle$ is weaker than a repeatable unitary: it cannot automatically be inverted to implement a reflection or coherently embedded in amplitude amplification. A classical array, a QRAM data structure, an amplitude-preparation circuit, and sample/query access likewise represent different inputs. Their setup time, update rules, precision, memory, and reversibility can dominate the advertised query count.

A block encoding makes one matrix interface precise. An $(\alpha,a,\epsilon_A)$ block encoding is a unitary $U_A$ on $a+n$ qubits such that $\alpha\geq\lVert A\rVert_2$ and

$$\left\lVert A- \alpha (\langle0^a\rvert\otimes I) U_A (\lvert0^a\rangle\otimes I) \right\rVert \leq\epsilon_A.$$

The scaling $\alpha$, ancilla width $a$, and block error $\epsilon_A$ are part of the input contract. So are calls to $U_A^\dagger$, controlled calls, and the reflection about the signal ancillas. A block query may expand into many sparse-oracle calls, selected unitaries, arithmetic operations, or memory lookups; the appropriate conversion theorem and its error must be charged.

Sparse access instead often supplies coherent position and value oracles. A row index and an integer label identify a possible nonzero position, and a second reversible operation writes a finite-precision entry. The model needs a sparsity bound, a convention for duplicates or padding, and access to rows and columns where the reduction requires both. A formula for $A_{jk}$ or a promise that $A$ is sparse does not implement either oracle. Similarly, a sum of unitaries, controlled Hamiltonian evolution, and a projected-unitary encoding are not interchangeable names for access.

The Quantum Oracles page owns the general semantic audit for such interfaces. Here the obligation is operational: report the reversible data structure, finite precision, ancillas, normalization, controls, inverse calls, and conversion count used by the chosen linear solver. A query theorem may treat these operations as units, but an executable estimate must expand them.

Conditioning, Scaling, and Spectral Promises

For an invertible matrix, the intrinsic spectral condition number is

$$\kappa_2(A) := \lVert A\rVert_2\lVert A^{-1}\rVert_2 = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}.$$

This quantity describes sensitivity of the mathematical inverse in the spectral norm. An access model introduces additional scaling. Choose and declare an inverse normalization

$$\alpha_{A^{-1}} \geq \lVert A^{-1}\rVert_2$$

and define the block condition number

$$\kappa_{\mathrm{block}} := \alpha\alpha_{A^{-1}} \geq \kappa_2(A).$$

For an exact invertible instance with tight inverse normalization, $\alpha_{A^{-1}}=1/\sigma_{\min}(A)$ and therefore $\kappa_{\mathrm{block}}=\alpha/\sigma_{\min}(A)$. Over-normalizing the same matrix can enlarge this access-induced parameter without changing $\kappa_2(A)$ or the normalized solution state. It should not be renamed an “effective condition number”: that phrase is also used for an instance- and tolerance-dependent spectral-truncation quantity.

The matching instance amplitude is

$$p_b := \frac{ \lVert A^{-1}\lvert b\rangle\rVert_2^2 }{ \alpha_{A^{-1}}^2 }.$$

It can be much larger than its worst-case lower bound, and modern two-oracle results exploit that distinction. A theorem using a loose but proved $\alpha_{A^{-1}}$ must retain the same normalization in both $p_b$ and $\kappa_{\mathrm{block}}$.

Representation error can be amplified by inversion. If $\lVert E\rVert<\sigma_{\min}(A)$, the resolvent identity gives the exact sensitivity shield

$$\left\lVert (A+E)^{-1}-A^{-1} \right\rVert \leq \frac{ \lVert E\rVert }{ \sigma_{\min}(A) \left[ \sigma_{\min}(A)-\lVert E\rVert \right] }.$$

Thus block-encoding error, right-hand-side preparation error, reciprocal or polynomial approximation, Hamiltonian simulation, phase or gate synthesis, and final measurement need separate budgets. A small residual does not by itself imply a small forward error for an ill-conditioned system, and even a forward-vector bound needs normalization control before it implies the state metric used here. Conditioning and Stability develops those general numerical distinctions.

HHL as a Spectral Inversion Procedure

The historical HHL construction is clearest for Hermitian $A$, rescaled so that $\lVert A\rVert_2=1$. In this specialization only, write

$$\kappa := \kappa_2(A) = \lVert A^{-1}\rVert_2,$$

so the supported eigenvalues obey

$$\lambda_j \in [-1,-1/\kappa]\cup[1/\kappa,1], \qquad \lvert b\rangle = \sum_j\beta_j\lvert u_j\rangle.$$

Controlled Hamiltonian simulation and phase estimation coherently attach an estimate of $\lambda_j$ to each eigencomponent. A reversible reciprocal step then controls a flag-qubit rotation. With a declared $0<C\leq1/\kappa$, its selected amplitude is $C/\lambda_j$, including the sign of a negative eigenvalue. Before uncomputation, the flag-one branch is proportional to

$$\sum_j \beta_j\frac{C}{\lambda_j}\lvert u_j\rangle = C A^{-1}\lvert b\rangle.$$

Uncomputing the eigenvalue register removes the spectral estimate from the ideal branch; measuring the flag heralds the solution state. The sequence is not “invert every eigenvalue in parallel” in the sense of returning them as a classical list. It implements a coherent, nonunitary spectral filter by embedding it in a larger unitary and conditioning on one outcome.

Finite phase estimation matters because the reciprocal is steep near the spectral gap. If $|\widetilde\lambda-\lambda|\leq\delta_\lambda$, $|\lambda|\geq1/\kappa$, and $\delta_\lambda\leq1/(2\kappa)$, then $|\widetilde\lambda|\geq1/(2\kappa)$ and

$$\left| \frac{1}{\widetilde\lambda} - \frac{1}{\lambda} \right| = \frac{|\widetilde\lambda-\lambda|} {|\widetilde\lambda\lambda|} \leq 2\kappa^2\delta_\lambda.$$

This elementary check connects eigenvalue precision to reciprocal error, but it is not a full output proof. Simulation, phase estimation, reversible arithmetic, rotation synthesis, uncomputation, postselection, and normalization must fit one state-error budget. Harrow, Hassidim, and Lloyd’s 2009 result established the paradigm under efficient sparse access and state preparation; its historical precision dependence should not be presented as the best modern bound.

Success Probability, Amplification, and Variable Time

The ideal flag probability follows directly from the branch norm:

$$p_C = C^2 \left\lVert A^{-1}\lvert b\rangle \right\rVert_2^2.$$

Choosing $C=1/\alpha_{A^{-1}}$ makes $p_C=p_b$. With tight normalization this is $C=1/\lVert A^{-1}\rVert_2=\sigma_{\min}(A)$. Plain repetition therefore uses $O(1/p_C)$ complete state-preparation attempts in expectation. Coherent Amplitude Amplification can reduce the dependence to $O(1/\sqrt{p_C})$, but only if the full preparation and its inverse, the success test, and the needed reflections and controls are executable. A copy of a prepared input state does not supply that contract.

Worst-case analysis replaces the actual spectral support of $\lvert b\rangle$ by the smallest allowed singular value and can thereby obscure easy instances. Variable-time algorithms partition branches according to the precision or evolution time they require, stop well-resolved branches early, and amplify a procedure with multiple stopping times. Ambainis’s 2012 analysis improved the isolated historical dependence from $O(\kappa^2\log N)$ to $O(\kappa\log^3\!\kappa\log N)$ in its model. That statement neither supplies a modern precision-resolved end-to-end runtime nor makes early stopping, clocks, inverse operations, or state preparation free.

Success probability and approximation error answer different questions. One can have a highly accurate conditional branch that is almost never observed, or a constant-probability branch implementing a poor reciprocal. A complete solver fixes both, allocates an allowed failure probability, and says whether the reported cost is an average, a worst-case cap, or an expected number of attempts.

Polynomial, Fourier, and QSVT Linear Solvers

Later methods replace a high-precision binary eigenvalue register by a direct approximation to the reciprocal on a promised spectral domain. Childs, Kothari, and Somma construct Fourier- and Chebyshev-based linear combinations in a sparse-access model, obtaining polylogarithmic rather than polynomial dependence on $1/\epsilon$ after the full success procedure is included. Gilyén, Su, Low, and Wiebe formulate singular-value transformation, which applies an admissible polynomial to the singular values exposed by a projected unitary encoding. Lin and Tong use polynomial filtering and a Zeno-style construction, while Subaşı, Somma, and Orsucci develop a randomized-adiabatic family. These methods share a spectral-inversion goal, not a single access or resource theorem.

For a projected unitary encoding with a singular-value gap $\delta$, the QSVT pseudoinverse construction approximates the scaled operator $(\delta/2)A^+$ with degree and encoded-operator call count

$$O\!\left( \frac{1}{\delta} \log\frac{1}{\epsilon} \right).$$

The factor $1/2$ belongs to this conventional bounded polynomial transform; it is not the largest admissible HHL reciprocal-rotation scale. Applying the transform to $\lvert b\rangle$, heralding or amplification, $U_b$, construction of the block encoding, and readout remain separate. For a singular matrix, the approximation also needs a cutoff and transition band, so the theorem prepares a truncated-pseudoinverse action only on the promised support.

Block Encodings and QSVT owns the general projected-unitary and block-encoding calculus, QSVT admissibility and singular-value transformation, composition and error rules, and the query and ancilla ledger; this page retains the QLSP-specific pseudoinverse application, success and error guarantees, normalized solution-state output, and readout limits.

Qubitization and Quantum Signal Processing retains the signal-walk construction, polynomial admissibility, phase conventions, synthesis, and validation workflow. This page uses only the QLSP-specific pseudoinverse theorem and the access costs needed to interpret its solution-state claim.

The following ledger deliberately keeps model-specific statements separate. Here $P_A$ and $P_B$ denote the Childs–Kothari–Somma sparse-matrix and right-hand-side oracles, while $O_A$ and $O_b$ denote the encoded-matrix and state-preparation oracles of the final row.

family	supplied access	counted call	output / error / success	bound and scope
HHL phase estimation	Efficiently row-computable $s$-sparse Hermitian $A$ and efficient $\lvert b\rangle$ preparation, with controlled finite-precision simulation	Sparse-access simulation, phase estimation, reciprocal rotation, uncomputation, and postselection within the historical runtime model	State proportional to $A^{-1}b$ at state error $\epsilon$ after the declared herald; readout is excluded	Rough historical $\widetilde O(s^2\kappa^2\log N/\epsilon)$ runtime; model-specific, not a current best bound or classical-vector theorem
Ambainis variable time	The paper’s sparse linear-system and preparable-input model, including reversible variable stopping branches	Calls and work in that historical model, with the stopping-time amplification procedure	Heralded approximate solution state under the paper’s bounded-error convention	Improves the isolated $O(\kappa^2\log N)$ dependence to $O(\kappa\log^3\!\kappa\log N)$; not a fully precision-resolved end-to-end bound
Fourier/Chebyshev LCU	Hermitian $\lVert A\rVert=1$, condition bound $\kappa$, at most $d$ nonzeros per row and column, coherent in-place $P_A$, and unitary $P_B\lvert0\rangle=\lvert b\rangle$	$P_A$ and $P_B$ queries are counted separately; inverses and variable-time amplification are included as specified by the theorem	Heralded solution state within Euclidean error $\epsilon$ and success at least $1/2$ in the gate-efficient theorem	Direct method: $O((d\kappa^2/\epsilon)\,\mathrm{polylog}(d\kappa/\epsilon))$ $P_A$ calls and $O(d\kappa\,\mathrm{polylog}(d\kappa/\epsilon))$ $P_B$ calls. Fourier: $O(d\kappa^2\log^{2.5}(\kappa/\epsilon))$ $P_A$ calls and $O(\kappa\sqrt{\log(\kappa/\epsilon)})$ $P_B$ calls. Chebyshev: $O(d\kappa^2\log^2(d\kappa/\epsilon))$ $P_A$ calls and $O(\kappa\log(d\kappa/\epsilon))$ $P_B$ calls. With variable time: $O(d\kappa\,\mathrm{polylog}(d\kappa/\epsilon))$ calls to both; oracle construction and loading remain excluded
QSVT pseudoinverse	Projected unitary encoding of $A$ with singular-value gap $\delta$, its inverse, signal reflections, and phase data	Encoded-operator and inverse calls, equivalently polynomial degree; application and success processing are separate	Operator approximation to $(\delta/2)A^+$ on the promised singular subspace with error $\epsilon$; solution-state success depends on the input	$O(\delta^{-1}\log(1/\epsilon))$ encoded-operator calls; block construction, $U_b$, heralding or amplification, cutoff bias, and readout are excluded
Discrete adiabatic solver	Supplied block encoding of $\lVert A\rVert=1$ with $\lVert A^{-1}\rVert=\kappa$, supplied $\lvert b\rangle$ preparation, and required controlled and inverse calls	Average calls to the block-encoding and preparation interfaces under the theorem’s oracle convention	Constant-success output within Euclidean state error $\epsilon$	Costa et al.: $O(\kappa\log(1/\epsilon))$ average oracle calls; sparse reduction, block construction, gates, loading, and readout are outside the bound
Tunable variable time	Low–Su block encoding $O_A$ with declared $\alpha$ and inverse normalization, and repeatable $O_b$, including the adjoint and controlled capabilities required for reflections and variable-time amplification	Queries to $O_A$ and $O_b$ are separate	Constant-success state within phase-aligned Euclidean error $\epsilon$ under the theorem’s normalization and $p_b$ convention	$\Theta(p_b^{-1/2})$ $O_b$ queries and $O(\kappa_{\mathrm{block}}\log(1/p_b)[\log\log(1/p_b)+\log(1/\epsilon)])$ $O_A$ queries; in the exceptional constant-$p_b$ regime use the theorem’s constant-case interpretation rather than substituting $p_b=1$ literally

Costa and collaborators’ 2022 discrete-adiabatic theorem reaches the joint $O(\kappa\log(1/\epsilon))$ query scaling in its supplied-block model. Their 2025 comparison shows lower constant factors than the randomized-adiabatic solver under the paper’s matched oracle construction; this is a comparison of those algorithms, not a universal hardware ranking. Low and Su’s 2026 theorem sharpens the two-oracle ledger: it makes the optimal $\Theta(p_b^{-1/2})$ preparation-oracle dependence visible while retaining a different matrix-oracle bound. None of these statements prices a classical database, a fault-tolerant implementation, or a downstream measurement unless those costs are separately expanded.

Non-Hermitian, Rectangular, and Least-Squares Problems

HHL’s Hermitian presentation is not a license to discard non-Hermitian structure. For an invertible square matrix, one standard reduction uses the Hermitian dilation

$$\mathcal A := \begin{pmatrix} 0&A\\ A^\dagger&0 \end{pmatrix}.$$

With compatible ordering of the two block registers,

$$\mathcal A^{-1} \begin{pmatrix} b\\0 \end{pmatrix} = \begin{pmatrix} 0\\A^{-1}b \end{pmatrix}.$$

The nonzero eigenvalue magnitudes of $\mathcal A$ are the singular values of $A$, so this dilation preserves the intrinsic spectral condition number. It does not preserve every implementation constant for free. The register is larger, access to $A^\dagger$ is required, a block or sparse interface for $\mathcal A$ must be constructed, and its normalization, sparsity convention, controls, and precision enter the resource and error ledgers.

For a rectangular matrix with singular-value decomposition $A=U\Sigma V^\dagger$, the input and output inhabit different singular-vector spaces. With cutoff $\delta>0$, define

$$A_\delta^+ := \sum_{\sigma_j\geq\delta} \frac{1}{\sigma_j} \lvert v_j\rangle\langle u_j\rvert.$$

The right-hand side is supplied in the left-singular space and the output is proportional to $A_\delta^+\lvert b\rangle$ in the right-singular space. A component of $b$ below the cutoff or outside the column space must be handled explicitly: reject it as invalid input, project it and disclose the lost norm, or define a least-squares objective whose minimizer uses that projection. The cutoff causes bias, changes the success amplitude, and sets the relevant condition parameter. Singular Value Decomposition owns the factorization and pseudoinverse definitions; this page owns the access-aware state-preparation claim.

Regularization changes the task again. Replacing $1/\sigma$ by, for example, $\sigma/(\sigma^2+\mu)$ can suppress unstable small singular values, but the output is then a regularized solution state. Its approximation interval, regularization bias, normalization, and downstream statistic must be stated; it is not an exact QLSP with a mysteriously improved condition number.

Outputs, Observables, and Readout

The solution register is useful when the application can remain quantum or asks for a low-dimensional functional. If $M$ is a bounded observable, a natural target is

$$\mu_M := \langle x\rvert M\lvert x\rangle.$$

For phase-aligned unit vectors separated by at most $\epsilon$, the preparation contribution obeys the simple bound

$$\left| \langle\widetilde x\rvert M\lvert\widetilde x\rangle - \langle x\rvert M\lvert x\rangle \right| \leq 2\lVert M\rVert\epsilon.$$

Statistical error is additional. If $M$ is measured with outcomes in $[-1,1]$, ordinary independent sampling uses fresh successful preparations; Hoeffding’s inequality gives a sufficient shot count $m\geq2\ln(2/\eta)/\delta^2$ for additive statistical error $\delta$ and failure probability at most $\eta$. Each shot therefore expands to another preparation, herald check, and possible retry. Coherent amplitude-estimation improvements require a repeatable preparation unitary, its inverse, reflections, and controlled uses, so they invoke a stronger access contract than independent samples.

A computational-basis measurement yields one index distributed according to $|x_j|^2$; it does not reveal phases, normalization of the unnormalized solution, or all coordinates. Tomography or dense classical output inherits an $\Omega(N)$-scale description requirement before accuracy and confidence are included. A meaningful application should instead name the overlap, expectation, sample, threshold decision, or subsequent coherent transformation that consumes $\lvert x\rangle$.

Lower Bounds and Limitations owns the general loading, explicit-output, tomography, and query-to-runtime barriers; this page retains QLSP-specific access, conditioning, quantum-state output, observables, verification, and theorem bounds.

Verification is not automatic either. In the black-box model analyzed by Somma and Subaşı, constant-distance coherent verification requires $\Omega(\kappa)$ uses of $U_b$, $U_b^\dagger$, or controlled variants in the worst case and typically $\Omega(\sqrt\kappa)$. A prepare-and-measure strategy requires $\Omega(\kappa^2)$ copies in the worst case and typically $\Omega(\kappa)$. Special structure can provide a cheaper residual, energy, observable, or application-specific certificate, but its measurement and the inequality linking it to the desired state guarantee must be supplied. Preparing a candidate does not certify it.

Complexity Bounds and Matched Classical Comparisons

Dimension, conditioning, precision, sparsity, input overlap, and success are independent asymptotic variables. A statement that is polylogarithmic in $N$ may still be polynomial in $\kappa$, $1/\epsilon$, sparsity, or inverse success amplitude. It may also count only ideal oracle calls. Query Complexity owns the general distinction between upper bounds, reductions, and query lower bounds; the ledger here keeps the relevant QLSP regimes attached to their access models.

In the block-encoding parity-reduction regime, a proved lower bound requires

$$\Omega\!\left( \kappa\log\frac{1}{\epsilon} \right)$$

encoded-matrix queries. It matches the joint condition-and-precision scaling of the discrete-adiabatic upper bound within that oracle setting. Mori, Kikuchi, Benedetti, and Rosenkranz proved a different 2026 lower bound, $\Omega(\kappa\sqrt{s})$, for sparse queries at constant error. These bounds cannot be multiplied or merged: their interfaces and error regimes differ. As of 2026-08-22, the joint $\kappa$, $s$, and $\epsilon$ dependence remains open. Neither query result is a universal gate-count, circuit-depth, physical- runtime, or wall-clock lower bound.

Classical comparison begins by matching the task. The conjugate-gradient method introduced by Hestenes and Stiefel is a natural comparator for sparse Hermitian positive-definite systems when a classical vector is wanted. Its iteration behavior depends on conditioning, while each iteration charges a sparse matrix–vector product and classical vector operations. That is not the same output contract as preparing $\lvert x\rangle$. Conversely, comparing a quantum state-output theorem only with the cost of printing a classical dense vector can manufacture a separation by requiring the classical method to solve a stronger problem.

The Classical Information Review supplies the representation and access matching needed here. A dense-memory quantum interface or length-square sample/query access may require substantial preprocessing and can enable stronger classical algorithms too. The comparison must therefore use the same matrix data structure, update model, right-hand-side access, condition and rank promises, output functional, accuracy, confidence, preprocessing, memory, and hardware boundary.

An end-to-end claim then adds state preparation, oracle or block-encoding construction, controlled and inverse operations, phase or polynomial synthesis, fault-tolerant gates, retries, measurement, classical postprocessing, and verification. Algorithmic Benchmarking owns empirical comparison design; Verification of Quantum Advantage owns evidence needed for an advantage conclusion; Claims, Hype, and Evidence Standards owns claim calibration; and Resource Estimation Tools owns the translation to implementation resources. Polylogarithmic dimension dependence in a supplied-oracle theorem, standing alone, establishes no generic exponential quantum advantage.

Two Reproducible Finite Audits

These audits are deterministic exact-algebra checks. They validate the stated two-dimensional instances, not asymptotic scaling, hardware performance, or a quantum advantage.

Audit 1 — HHL rotation and postselection ledger

Take

$$A = \operatorname{diag}\!\left(1,\frac12\right), \qquad \lvert b\rangle = \frac{\lvert0\rangle+\lvert1\rangle}{\sqrt2}, \qquad C=\frac12.$$

Then

$$\kappa_2(A)=2, \qquad A^{-1}\lvert b\rangle = \frac{\lvert0\rangle+2\lvert1\rangle}{\sqrt2}, \qquad \lvert x\rangle = \frac{\lvert0\rangle+2\lvert1\rangle}{\sqrt5}.$$

The two reciprocal-rotation flag amplitudes are $1/2$ and $1$, so

$$p_C = \frac12 \left[ \left(\frac12\right)^2+1^2 \right] = \frac58.$$

quantity	exact value	interpretation
$\kappa_2$	$2$	intrinsic condition number
flag amplitude for $\lambda=1$	$1/2$	$C/\lambda$ on $\lvert0\rangle$
flag amplitude for $\lambda=1/2$	$1$	$C/\lambda$ on $\lvert1\rangle$
$p_C$	$5/8$	ideal herald probability
$P(0)$	$1/5$	postselected computational-basis probability
$P(1)$	$4/5$	postselected computational-basis probability
$\langle Z\rangle$	$-3/5$	one observable, not both coordinates

The complete audit record is:

1. Problem family and size. One two-dimensional Hermitian QLSP instance with one solution qubit and exact rational data.
2. Promise and instance. The diagonal matrix is invertible with spectrum $\{1,1/2\}$, and the input has equal support on both eigenvectors.
3. Access and encoding. The check licenses one exact $\lvert b\rangle$ preparation interface and exact diagonal spectral processing; it does not infer an oracle from the displayed matrix.
4. Output and use. The heralded output is $(\lvert0\rangle+2\lvert1\rangle)/\sqrt5$, from which a $Z$ expectation or basis sample may be obtained.
5. Success and error. The ideal algebra has zero approximation error and flag probability $5/8$; finite implementation error is outside this audit.
6. Algorithmic idea. Reciprocal rotation multiplies the two eigenbasis amplitudes by $1/2$ and $1$ before normalization.
7. Executable procedure. Prepare, label the spectrum, rotate the flag, uncompute, and either postselect the herald or supply the reflections needed for amplification.
8. Resource ledger. Count preparation, spectral processing, controlled rotation, uncomputation, successful preparations, and any amplification as separate resources.
9. Classical comparator. Direct rational two-by-two algebra checks the finite identities; it is not a scalable comparator to an oracle problem.
10. Evidence and limits. The calculation proves the listed values only. A single run does not return both solution coordinates or establish scaling.

Audit 2 — Block normalization and readout remain separate

Now take

$$A = \operatorname{diag}\!\left(1,\frac14\right), \qquad \lvert b\rangle = \frac{\lvert0\rangle+\lvert1\rangle}{\sqrt2}, \qquad \alpha_{A^{-1}}=4 \quad\text{(tight)}.$$

Exact inversion gives

$$\kappa_2(A)=4, \qquad \lvert x\rangle = \frac{\lvert0\rangle+4\lvert1\rangle}{\sqrt{17}}, \qquad p_b = \frac{17}{32}.$$

quantity	exact value	interpretation
$\kappa_2$	$4$	intrinsic condition number
$p_b$	$17/32$	tight HHL-style success with $C=1/4$
$P(0)$	$1/17$	one basis probability
$P(1)$	$16/17$	the other basis probability
$\langle Z\rangle$	$-15/17$	selected observable output
block condition number for $\alpha=1$	$4$	tight matrix normalization
block condition number for $\alpha=2$	$8$	over-normalized access to the same $A$

The HHL-style scale $C=1/4$ produces success $17/32$. By contrast, the conventional QSVT pseudoinverse theorem applies the extra factor $1/2$ to the encoded inverse. For $\delta=1/4$ and tight $\alpha=1$, the implemented scale is $A^{-1}/8$, so its unamplified success is $17/128$. Combining that transform with the larger HHL success probability would mix two normalization conventions.

The complete audit record is:

1. Problem family and size. One two-dimensional diagonal QLSP compares two exact encodings of the same matrix and one selected observable.
2. Promise and instance. The spectrum is $\{1,1/4\}$, the inverse normalization is tightly $4$, and the right-hand side has equal eigenbasis amplitudes.
3. Access and encoding. Two supplied exact block encodings use $\alpha=1$ and $\alpha=2$; their construction costs are not assumed equal.
4. Output and use. Both encode the same normalized solution state, while a basis sample or $Z$ expectation is the declared classical use.
5. Success and error. Exact HHL-style heralding has probability $17/32$; the differently scaled QSVT transform has probability $17/128$ before amplification.
6. Algorithmic idea. Separating intrinsic conditioning from access normalization prevents an over-normalized block from changing the mathematical problem.
7. Executable procedure. Prepare $\lvert b\rangle$, apply the selected inverse transform, herald success, and repeat successful preparations for the chosen measurement.
8. Resource ledger. Keep block-oracle calls, $U_b$ calls, successful states, observable shots, confidence, and construction costs distinct.
9. Classical comparator. Exact rational arithmetic verifies this instance; no finite table demonstrates an asymptotic speedup.
10. Evidence and limits. The audit proves the normalization and readout distinctions. It does not compare physical implementations of the two block encodings.

One deterministic program reproduces all values in both audits:

const TOL = 1e-14;
const assert = (condition, label) => {
  if (!condition) throw new Error(label);
};
const close = (actual, expected, label) => {
  assert(Math.abs(actual - expected) <= TOL,
    `${label}: ${actual} != ${expected}`);
};
const vectorClose = (actual, expected, label) => {
  assert(actual.length === expected.length, `${label}: length`);
  actual.forEach((value, index) =>
    close(value, expected[index], `${label}[${index}]`));
};
const norm2 = (vector) => Math.sqrt(
  vector.reduce((sum, value) => sum + value * value, 0),
);
const normalize = (vector) => {
  const norm = norm2(vector);
  return vector.map((value) => value / norm);
};
const diagonalMatVec = (diagonal, vector) =>
  diagonal.map((value, index) => value * vector[index]);

const b = [1 / Math.sqrt(2), 1 / Math.sqrt(2)];
close(norm2(b), 1, 'right-hand-side norm');

// Audit 1.
const diagonal1 = [1, 1 / 2];
const inverseApplied1 = b.map((value, index) =>
  value / diagonal1[index]);
vectorClose(
  inverseApplied1,
  [1 / Math.sqrt(2), 2 / Math.sqrt(2)],
  'audit 1 inverse vector',
);
vectorClose(
  diagonalMatVec(diagonal1, inverseApplied1),
  b,
  'audit 1 linear equation',
);
const x1 = normalize(inverseApplied1);
vectorClose(x1, [1 / Math.sqrt(5), 2 / Math.sqrt(5)], 'audit 1 x');
close(norm2(x1), 1, 'audit 1 unit norm');
const kappa1 = Math.max(...diagonal1) / Math.min(...diagonal1);
close(kappa1, 2, 'audit 1 intrinsic condition');
const C1 = 1 / 2;
const flag1 = diagonal1.map((lambda) => C1 / lambda);
vectorClose(flag1, [1 / 2, 1], 'audit 1 flag amplitudes');
const pC = b.reduce((sum, beta, index) =>
  sum + beta * beta * flag1[index] * flag1[index], 0);
close(pC, 5 / 8, 'audit 1 success');
close(x1[0] ** 2, 1 / 5, 'audit 1 P(0)');
close(x1[1] ** 2, 4 / 5, 'audit 1 P(1)');
close(x1[0] ** 2 - x1[1] ** 2, -3 / 5, 'audit 1 Z');

// Audit 2.
const diagonal2 = [1, 1 / 4];
const inverseApplied2 = b.map((value, index) =>
  value / diagonal2[index]);
vectorClose(
  inverseApplied2,
  [1 / Math.sqrt(2), 4 / Math.sqrt(2)],
  'audit 2 inverse vector',
);
vectorClose(
  diagonalMatVec(diagonal2, inverseApplied2),
  b,
  'audit 2 linear equation',
);
const x2 = normalize(inverseApplied2);
vectorClose(x2, [1 / Math.sqrt(17), 4 / Math.sqrt(17)], 'audit 2 x');
close(norm2(x2), 1, 'audit 2 unit norm');
const kappa2 = Math.max(...diagonal2) / Math.min(...diagonal2);
close(kappa2, 4, 'audit 2 intrinsic condition');
const alphaInverse = 4;
assert(alphaInverse >= 1 / Math.min(...diagonal2), 'inverse normalization');
const pB = norm2(inverseApplied2) ** 2 / alphaInverse ** 2;
close(pB, 17 / 32, 'audit 2 p_b');
close(x2[0] ** 2, 1 / 17, 'audit 2 P(0)');
close(x2[1] ** 2, 16 / 17, 'audit 2 P(1)');
close(x2[0] ** 2 - x2[1] ** 2, -15 / 17, 'audit 2 Z');
const alphaTight = 1;
const alphaLoose = 2;
assert(alphaTight >= Math.max(...diagonal2), 'tight alpha validity');
assert(alphaLoose >= Math.max(...diagonal2), 'loose alpha validity');
const blockKappaTight = alphaTight * alphaInverse;
const blockKappaLoose = alphaLoose * alphaInverse;
close(blockKappaTight, 4, 'tight block condition');
close(blockKappaLoose, 8, 'loose block condition');
assert(blockKappaTight === kappa2, 'tight block versus intrinsic');
assert(blockKappaLoose !== kappa2, 'loose block versus intrinsic');
const qsvtScaled = inverseApplied2.map((value) => value / 8);
const qsvtSuccess = norm2(qsvtScaled) ** 2;
close(qsvtSuccess, 17 / 128, 'QSVT scaled success');

console.log('Quantum-linear-algebra audits: PASS');

Common Quantum-Linear-Algebra Claim Failures

Treating stored data as coherent access. A displayed matrix or classical array is not a sparse oracle, block encoding, or controlled evolution. Name the implemented interface, its precision, inverse and control capabilities, construction cost, and memory.

Equating intrinsic and block conditioning. The mathematical $\kappa_2(A)$ is unchanged by rescaling an encoding, whereas $\kappa_{\mathrm{block}}=\alpha\alpha_{A^{-1}}$ depends on declared access normalizations. Keep both quantities and do not hide block error.

Suppressing the success branch. A reciprocal or pseudoinverse filter is nonunitary and therefore appears inside a heralded construction. State its success amplitude and charge retries or the preparations, inverses, reflections, and controls used by amplification.

Reporting a quantum state as a classical vector. Measuring $\lvert x\rangle$ once yields one sample, not $N$ coordinates, their relative phases, or $\lVert A^{-1}b\rVert_2$. Specify a downstream functional and measurement protocol.

Using residual as state error without conditioning. A small residual can coexist with appreciable forward error when small singular values are present. Provide the stability inequality, cutoff, and normalization step that connect the reported metric to the desired state.

Silently changing a singular problem. Truncation, projection, least squares, and regularization define different outputs. State the chosen support, cutoff bias, and treatment of components outside the column space.

Calling a query bound an end-to-end advantage. Oracle construction, loading, gates, successful repetitions, measurement, verification, and the matched classical baseline remain outside a bare matrix-query formula. A polylogarithmic $N$ dependence does not erase them.

Exercises

1. Normalize a Quantum Linear-System Instance

Let

$$A=\operatorname{diag}(2,1), \qquad b=\begin{pmatrix}3\\4\end{pmatrix}.$$

Compute $\lvert b\rangle$, the unnormalized vector $A^{-1}\lvert b\rangle$, and the normalized solution state. Explain why solving with $b$ or with $\lvert b\rangle$ produces the same final quantum state but not the same classical solution vector.

Solution

Because $\lVert b\rVert_2=5$,

$$\lvert b\rangle = \frac35\lvert0\rangle+\frac45\lvert1\rangle.$$

Applying the inverse gives

$$A^{-1}\lvert b\rangle = \frac{3}{10}\lvert0\rangle+\frac45\lvert1\rangle, \qquad \left\lVert A^{-1}\lvert b\rangle\right\rVert_2 = \frac{\sqrt{73}}{10}.$$

Therefore

$$\lvert x\rangle = \frac{3\lvert0\rangle+8\lvert1\rangle}{\sqrt{73}}.$$

The classical solutions to $Ax=b$ and $Ax=b/\lVert b\rVert_2$ differ by the factor $5$. Normalization removes that nonzero scalar, so their solution states coincide. The state consequently does not retain the magnitude needed to reconstruct the original classical vector.

2. Derive the HHL Flag Probability

Assume the ideal Hermitian HHL setting with $\lvert b\rangle=\sum_j\beta_j\lvert u_j\rangle$ and flag amplitude $C/\lambda_j$. Derive the heralding probability. Then evaluate it for $A=\operatorname{diag}(1,1/3)$, equal input amplitudes, and $C=1/3$; also give the two postselected basis probabilities.

Solution

Orthogonality of the eigenvectors makes the squared norm of the selected branch

$$p_C = \sum_j \lvert\beta_j\rvert^2 \frac{C^2}{\lvert\lambda_j\rvert^2} = C^2\lVert A^{-1}\lvert b\rangle\rVert_2^2.$$

For the stated instance, the flag amplitudes are $1/3$ and $1$. Hence

$$p_C = \frac12\left(\frac19+1\right) = \frac59.$$

The unnormalized inverse action is proportional to $(1,3)$, so the successful state is $(\lvert0\rangle+3\lvert1\rangle)/\sqrt{10}$. Its basis probabilities are $1/10$ and $9/10$. They require separate successful shots to estimate; the heralding calculation does not output the pair as a classical record.

3. Separate Intrinsic and Block Condition Numbers

Let $A=\operatorname{diag}(1,1/5)$ and use the tight inverse normalization $\alpha_{A^{-1}}=5$. Compare exact block encodings with $\alpha=1$ and $\alpha=3$. Find the intrinsic and block condition numbers, and state what does and does not change for a fixed $\lvert b\rangle$.

Solution

The singular values are $1$ and $1/5$, so

$$\kappa_2(A)=5.$$

The two valid matrix normalizations satisfy $\alpha\geq\lVert A\rVert_2=1$ and give

$$\kappa_{\mathrm{block}}(\alpha=1)=1\cdot5=5, \qquad \kappa_{\mathrm{block}}(\alpha=3)=3\cdot5=15.$$

The matrix, its intrinsic condition number, $A^{-1}\lvert b\rangle$, and its normalized direction are unchanged. The encoded block amplitude and the access-induced condition parameter change. Consequently, a query theorem expressed in $\kappa_{\mathrm{block}}$ can assign different bounds to the two interfaces even though they represent the same mathematical system.

4. Propagate Eigenvalue-Estimation Error

Suppose $\lVert A\rVert_2=1$, $\kappa=5$, an eigenvalue is $\lambda=1/5$, and phase estimation returns $\widetilde\lambda=0.21$. Verify the hypotheses of the reciprocal stability bound, compute the actual reciprocal error, and compare it with the bound. What error sources remain before a state guarantee follows?

Solution

Here $\delta_\lambda=0.01$ and $1/(2\kappa)=0.1$, so the required inequality $\delta_\lambda\leq1/(2\kappa)$ holds. The actual error is

$$\left| \frac{1}{0.21}-5 \right| = \frac{5}{21} \approx0.238095,$$

whereas the elementary bound gives

$$2\kappa^2\delta_\lambda = 2\cdot25\cdot0.01 = 0.5.$$

The bound is valid but not tight for this value. A final state guarantee must also budget Hamiltonian-simulation error, reversible reciprocal arithmetic, rotation synthesis, imperfect uncomputation, input preparation, block error, postselection or amplification error, and the change caused by normalizing the approximate inverse-applied vector.

5. Build a Hermitian Dilation

For

$$A= \begin{pmatrix} 1&1\\ 0&1 \end{pmatrix}, \qquad b= \begin{pmatrix} 0\\1 \end{pmatrix},$$

write the $4\times4$ Hermitian dilation and verify its inverse action on $(b,0)^T$. Name two implementation costs that the algebraic identity does not remove.

Solution

Because

$$A^\dagger = \begin{pmatrix} 1&0\\ 1&1 \end{pmatrix},$$

the dilation is

$$\mathcal A = \begin{pmatrix} 0&0&1&1\\ 0&0&0&1\\ 1&0&0&0\\ 1&1&0&0 \end{pmatrix}.$$

Also $A^{-1}b=(-1,1)^T$. Direct multiplication verifies

$$\mathcal A \begin{pmatrix} 0\\0\\-1\\1 \end{pmatrix} = \begin{pmatrix} 0\\1\\0\\0 \end{pmatrix} = \begin{pmatrix} b\\0 \end{pmatrix}.$$

The reduction needs an extra block-label qubit and coherent access to both $A$ and $A^\dagger$. It also requires a constructed normalization and may alter sparse-oracle constants, ancilla use, controls, and gate cost. Those costs do not vanish because the nonzero singular values are preserved.

6. Design an Observable Readout

A solver prepares $\lvert\widetilde x\rangle$ within Euclidean distance $\epsilon_{\mathrm{prep}}$ of $\lvert x\rangle$ after phase alignment. You want $\langle Z\rangle$ to total additive error at most $\Delta$ and failure probability at most $\eta$. Allocate half the error to preparation and half to sampling, and give a sufficient number of successful shots. How does a raw herald probability $p$ affect attempts?

Solution

Because $\lVert Z\rVert=1$, preparation contributes at most $2\epsilon_{\mathrm{prep}}$. Allocate $\Delta/2$ to it by requiring $\epsilon_{\mathrm{prep}}\leq\Delta/4$. Allocate the other $\Delta/2$ to the sample mean. Since $Z$ outcomes lie in $[-1,1]$, Hoeffding’s bound is met by

$$m \geq \frac{8}{\Delta^2} \ln\frac{2}{\eta}$$

successful, independent preparations. Without coherent amplification, a herald probability $p$ makes the expected number of full attempts $m/p$. Using amplitude estimation would change the sampling dependence, but it would also require coherent preparation inverses, reflections, controls, and its own error and success ledger.

7. Scope a Polylogarithmic-Dimension Claim

A manuscript says: “The QLSP query count is $\operatorname{polylog}(N)$, so the algorithm solves dense linear systems exponentially faster than every classical method.” Identify the missing assumptions and give a defensible replacement statement.

Solution

The claim omits how the dense matrix and right-hand side are loaded, the cost of constructing and controlling their oracles, condition and rank promises, precision and success dependence, and whether the output is a state or a classical vector. It also omits preprocessing, repeated preparation, measurement, verification, and a classical comparator with the same data access and output functional.

A defensible replacement is conditional: under a supplied coherent matrix interface and repeatable state preparation whose costs are excluded, a named QLSP theorem may use only polylogarithmically many address-dependent operations in $N$ while retaining its stated dependence on conditioning, precision, and success. Whether that yields an end-to-end advantage for a selected observable requires explicit oracle construction, readout, and a matched dated classical comparison. No conclusion about every dense system follows.

8. Repair a Quantum-Linear-Algebra Advantage Claim

Repair the sentence “HHL returns the solution of any linear system exponentially faster than classical algorithms.” Give a complete record for a claim that could be evaluated rather than merely replacing “any” by “some.”

Solution

A defensible statement concerns a declared family and a useful state-derived quantity, not unrestricted classical vector output. For example: a selected QLSP algorithm can prepare an approximate normalized solution state with its proved query scaling when all stated coherent interfaces and promises are supplied; an end-to-end advantage remains a separate, application-specific claim. The complete record is:

1. Problem family and size. Specify an $N\times N$ family and whether the task is nonsingular solution-state preparation, truncated pseudoinversion, or least squares; name every scaling parameter.
2. Promise and instance. Declare Hermiticity or dilation, rank or spectral interval, condition bound, sparsity or other structure, input support, and any distributional promise.
3. Access and encoding. Give executable matrix and $U_b$ interfaces, normalizations, errors, data structures, preprocessing, inverses, controls, and construction costs.
4. Output and use. Require a normalized state and identify the particular observable, overlap, sample, decision, or coherent subroutine that consumes it; do not promise an unmeasured classical vector.
5. Success and error. State phase-aligned Euclidean error, herald probability, failure and confidence budgets, and the repetition or amplification method.
6. Algorithmic idea. Name phase-estimation inversion, polynomial or singular-value transformation, variable time, or adiabatic transport and explain why it implements the desired filter.
7. Executable procedure. Expand preparation, oracle calls, arithmetic or polynomial phases, inverses, controls, reflections, uncomputation, heralding, retries, measurement, verification, and stopping.
8. Resource ledger. Report matrix and preparation queries separately from logical gates, depth, width, ancillas, memory, preprocessing, synthesis, successful shots, classical work, fault-tolerant overhead, and wall time.
9. Classical comparator. Select a dated algorithm with the same matrix and input access, promises, preprocessing, requested output, accuracy, confidence, memory, parallelism, and hardware boundary.
10. Evidence and limits. Cite the applicable upper and lower theorems, finite audits, and implementation evidence; exclude unsupported loading, readout, verification, gate, runtime, and universal-advantage conclusions.

This record can support a conditional oracle or end-to-end comparison once its entries are filled with evidence. It cannot support the original universal claim merely from a logarithmic-sized address register.

References

• A. Ambainis, “Variable Time Amplitude Amplification and Quantum Algorithms for Linear Algebra Problems,” in 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), 636–647 (2012), doi:10.4230/LIPIcs.STACS.2012.636.
• A. M. Childs, R. Kothari, and R. D. Somma, “Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision,” SIAM Journal on Computing 46, 1920–1950 (2017), doi:10.1137/16M1087072.
• P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, and D. W. Berry, “Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem,” PRX Quantum 3, 040303 (2022), doi:10.1103/PRXQuantum.3.040303.
• P. C. S. Costa, D. An, R. Babbush, and D. W. Berry, “The Discrete Adiabatic Quantum Linear System Solver Has Lower Constant Factors Than the Randomized Adiabatic Solver,” Quantum 9, 1887 (2025), doi:10.22331/q-2025-10-20-1887.
• A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, “Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 193–204 (2019), doi:10.1145/3313276.3316366.
• A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum Algorithm for Linear Systems of Equations,” Physical Review Letters 103, 150502 (2009), doi:10.1103/PhysRevLett.103.150502.
• M. R. Hestenes and E. Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems,” Journal of Research of the National Bureau of Standards 49, 409–436 (1952), doi:10.6028/jres.049.044.
• L. Lin and Y. Tong, “Optimal Polynomial Based Quantum Eigenstate Filtering with Application to Solving Quantum Linear Systems,” Quantum 4, 361 (2020), doi:10.22331/q-2020-11-11-361.
• G. H. Low and Y. Su, “Quantum Linear System Algorithm with Optimal Queries to Initial State Preparation,” Quantum 10, 2041 (2026), doi:10.22331/q-2026-03-23-2041.
• H. Mori, Y. Kikuchi, M. Benedetti, and M. Rosenkranz, “Sparsity-Dependent Complexity Lower Bound of Quantum Linear System Solvers,” Quantum Science and Technology 11, 035063 (2026), doi:10.1088/2058-9565/ae89e0.
• R. D. Somma and Y. Subaşı, “Complexity of Quantum State Verification in the Quantum Linear Systems Problem,” PRX Quantum 2, 010315 (2021), doi:10.1103/PRXQuantum.2.010315.
• Y. Subaşı, R. D. Somma, and D. Orsucci, “Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing,” Physical Review Letters 122, 060504 (2019), doi:10.1103/PhysRevLett.122.060504.