WorksPhysics and Astronomy
Extending Sample-based Quantum Diagonalization to Systems of Linear Equations
Abstract
Solving systems of linear equations, , is a ubiquitous task in computational science. The Harrow-Hassidim-Lloyd algorithm requires phase estimation, controlled rotations, and post-selection, impractical on noisy intermediate-scale quantum hardware. We extend sample-based quantum diagonalization (SQD), developed for quantum chemistry, to linear systems. Following the sample-based Krylov variant, the Hermitian matrix is decomposed in the Pauli basis, the Trotterized time evolution of is sampled at several times to select computational-basis configurations, and the system is solved classically by a Galerkin projection onto the selected subspace. We prove that the subspace solution is exact when the sampled configurations contain the Krylov support of and optimal in the energy norm for symmetric positive-definite matrices, so that noise-induced configurations cannot degrade it as long as they do not displace the ideal ones. On IBM Quantum hardware, the sampled distribution of a example deviates from the exact one by eleven times the shot-noise level, yet the solution is recovered exactly. For a localized problem of dimension , SQD selects 33 configurations, reaches a relative error of , and its truncated subspaces coincide with the optimal choice; readout errors enlarge the subspace without degrading the accuracy. The tests also show the limitations: the selected subspace coincides with that of inexpensive classical selection, banded matrices require exponentially many Pauli terms in the binary encoding, and Trotter errors populate spurious configurations unless the circuits are deep. An MIT-licensed Python package and notebooks that reproduce the numerical results are provided.
Introduction
Solving systems of linear equations efficiently is a fundamental problem in both classical and quantum computing[7]. Several classical algorithms exist, but their cost typically scales polynomially with the dimension . The Harrow–Hassidim–Lloyd (HHL) algorithm, a well-known quantum algorithm for solving linear systems, prepares a state proportional to with a cost logarithmic in the dimension , but it relies on quantum phase estimation, eigenvalue-controlled ancilla rotations, and post-selection[1]. Moreover, the cost can scale poorly with the condition number of and the desired accuracy, so that the resulting circuits are deep, in particular for applications that require high precision, such as expectation values of observables. Such circuits are difficult to execute reliably on current noisy intermediate-scale quantum (NISQ) devices, and before fault-tolerant quantum computers become available it is essential to develop algorithms that can be executed natively within the limitations of present hardware[2]. This motivates the search for alternative quantum algorithms that can achieve similar goals with shallower circuits and potentially lower overall cost.
A class of hybrid algorithms that is well suited to such hardware uses the quantum computer only to sample computational-basis configurations, and solves the problem classically in the subspace spanned by the sampled configurations. Sample-based quantum diagonalization, which has recently gained attention, follows this strategy for electronic ground states, without the parameter optimization of variational eigensolvers and without the deep circuits of phase estimation; SQD has been applied to chemical systems beyond the reach of exact diagonalization[3, 8, 9]. In the sample-based Krylov variant (SKQD), the sampled states are time-evolved states , which endows the selected subspace with the convergence properties of Krylov methods[5, 10]. Sample-based approaches have very recently been applied to linear systems as well. Ahn and Park measure quantum Krylov states and reconstruct the solution of positive-definite systems arising from elliptic partial differential equations by a Galerkin solve on the sampled basis states[4]. Preliminary results of the present work were presented at the Quantum AI 2026 Conference (Indianapolis, 14–16 August 2026)[11], independently of and before the appearance of Refs. 4 and 6; the approaches are complementary.
In this work, we extend this approach to linear systems. We sample the time-evolved states following the SKQD protocol and solve the linear system by a Galerkin projection onto the sampled configurations. Two differences from SQD for chemistry should be stated at the outset: the classical step is a linear solve rather than an eigenvalue problem, and no configuration recovery is required, since a general linear system has no particle-number or spin symmetry to restore. Throughout, is Hermitian (symmetric positive-definite for the optimality statements) and has small support, e.g. a single basis state; a non-Hermitian would require the Hermitian dilation, which is indefinite and is not treated here.
Relative to Refs. 4 and 6, our contributions are: (i) a characterization of the configurations reachable by exact time evolution, the support of equals the Krylov support of except at countably many times, which implies that the Galerkin solution is exact whenever the sampled set contains this support (Proposition 1); (ii) an analysis of the cost of the method in the Pauli-string encoding used by SKQD, showing that banded matrices require Pauli strings in the binary encoding and that Lie-Trotter errors populate configurations outside the Krylov support, so that the compression is lost before the accuracy; (iii) an open-source Qiskit implementation with a single interface to noiseless and noisy simulators and to IBM Quantum hardware; and (iv) a comparison with classical Krylov, residual-greedy, and oracle selection on a localized model problem, using exact sampling distributions. We find that the method selects near-optimal subspaces and is robust to readout noise but, consistent with Ref. 4, that its natural regime (exponentially large , a matrix given as a sum of polynomially many Pauli strings, and a solution concentrated on few configurations) is also a regime in which classical residual-based selection is efficient, so that a quantum advantage requires additional structure. Identifying such structure on available hardware and on more structured problem instances is the subject of ongoing work.
Theoretical procedure
The workflow of the procedure is summarized in Figure 1; the individual steps are derived below.

Figure 1. Workflow of sample-based quantum diagonalization for linear systems. Steps 1–2 (classical) decompose into Pauli strings and choose the time grid; Steps 3–4 (quantum) prepare , apply the Trotterized evolution for , and sample all circuits in one batched job on a noiseless simulator, a noisy simulator, or IBM Quantum hardware; Steps 5–7 (classical) form the configuration set, solve the projected system, and evaluate the solution. Names in typewriter font refer to the functions of the accompanying code.
Pauli decomposition
For , the tensor products form an orthogonal basis for Hermitian matrices , with :
The number of non-zero terms controls the circuit cost. For a real symmetric , strings with an odd number of factors are purely imaginary and do not contribute, so a generic real symmetric matrix has terms and a generic complex Hermitian matrix has , whereas a diagonal matrix has only terms. These are the maximum numbers of non-zero terms for the respective classes. As in Hamiltonian simulation, truncating the expansion reduces the circuit cost at the expense of an approximation error, and this trade-off has to be tested for the problem at hand. Equation (1) can be evaluated in operations with the tensorized Pauli decomposition[12]. We typically use symmetric positive-definite (SPD) matrices in our numerical experiments. If is not SPD, the decomposition still applies, but the classical solve requires additional care for negative (or zero) eigenvalues, as discussed in the Galerkin step below.
State preparation and Trotterized evolution
This step involves the encoding of the vector into a quantum state and the subsequent Trotterized evolution under the Hamiltonian . The normalized state is expanded in the eigenbasis ,
with overlap amplitudes
and evolves as
The propagator is approximated by the first-order Lie-Trotter product formula[13, 14],
whose error is bounded by the commutators of the terms[15],
hence the formula is exact when all terms commute. Since , each factor is exactly a Pauli rotation,
which for a string of weight costs CNOT gates; the identity string contributes a global phase only. A circuit therefore contains at most rotations and CNOT gates.
Sampling and the configuration set
Measuring in the computational basis yields configuration with probability . Since depends only on the eigenvalues through their differences, it is a trigonometric polynomial in whose angular frequencies lie in , with . Sampling it on a uniform grid of step without aliasing requires
This is a heuristic criterion rather than a guarantee: it excludes aliasing of the sampled distribution, but it does not by itself ensure that every relevant configuration is sampled. Rigorous support-discovery guarantees for finite nonnegative- and signed-time grids are derived in Ref. 6.
Ref. 6. For sparse , an inexpensive upper bound on follows from the Gershgorin theorem,
with . is the expectation value of in the computational basis state :
In this work, we label the computational basis states by the bit strings . The usual integer index is read as a binary number, and is the entry in row and column , which is off-diagonal when . Evaluating Eq. (9) requires the rows of ; when is given as a Pauli sum, the bound can be evaluated in operations.
The SKQD choice , where , the operator (spectral) norm, i.e. the largest absolute eigenvalue, is related but not equivalent to Eq. (8)^{5}: for positive semidefinite one has , so that it satisfies Eq. (8) automatically (and is much finer than necessary when ), whereas in general , so that it can exceed the bound of Eq. (8) by at most a factor of two. Amplitude propagates through the sparsity graph of , so the configurations sampled up to form a light cone around whose radius, and hence the subspace size, is controlled by as we expect to see in the computational examples.
Components of whose frequencies differ by less than are, moreover, not resolved within the time window, and each is only estimated up to shot noise . As in SQD and SKQD3,5, the completeness of the configuration set is therefore not guaranteed a priori; it can be monitored a posteriori through the residual and improved by increasing , , or . This is tested numerically in Sec. IV.
The exact aggregated distribution can be defined as the average over the sampling times,
which differs from the long-time average of Remark 2. Pooling the samples of each of the circuits gives its empirical estimate and the configuration set
The support of , which is known classically, is always included: a set that misses it gives below and hence a vanishing solution. More explicitly, under amplitude encoding, is the set of configurations occupied by at , the initial state. That is, the time evolution spreads amplitude from these configurations through the couplings of .
A configuration is missed only if it is absent from all independent samples, so that, using ,
Hence arises only from configurations of weight below or from explicit truncation. The Trotterized propagator does not preserve the sparsity pattern of , since individual Pauli strings can couple configurations that does not couple; by Eq. (13), with now the distributions of the Trotterized circuits, Trotter errors therefore populate spurious configurations unless their weight is below . The sampling step is summarized in Algorithm 1.
Algorithm 1. Trotterized time-evolution sampling
Require: Hermitian with Pauli decomposition ; initial state corresponding to ; number of time samples ; Trotter steps ; maximum time ; shots per circuit
Ensure: Empirical aggregated distribution over ,
for all
for to do
▷ time grid
normalize the state
initialize circuit on qubits in state
for to do ▷ Trotter steps
for to do
append to
end for
end for
measure all qubits of in the computational basis, times
record counts ; set
for all
end for
return
Total gate count follows directly from the nested loops: rotations per Trotter step, steps per circuit, independent circuits, for rotation gates overall—all circuits are independent and are submitted as a single batched job in the implementation below, so affects total shot count and job size but not per-circuit depth. The implementation is described in Sec. III.
Galerkin solution
Let and let
be the corresponding isometry (; the orthogonal projector onto the subspace is ). The system is restricted to the subspace,
which in practice amounts to selecting rows and columns of . For SPD , is SPD and the reduced system is solved directly. The spectral decomposition gives
with , replaced for indefinite by a pseudo-inverse or the Tikhonov filter . This is the diagonalization step of the method; it carries out classically the inversion that HHL performs coherently. The approximate solution is , and its accuracy is quantified by the fidelity and the relative error,
and by the energy-norm error , where , hats denote normalization, and . Unlike a comparison of alone, these metrics are sensitive to the signs of the components.
Exactness, optimality, and targeting
We denote by the set of configurations on which is non-zero and assume invertible.
Proposition 1 (Krylov support). Let be the Krylov support of . Then (i) ; (ii) for all outside a countable set; (iii) if and is invertible, then exactly.
Proof. (i) By the Cayley–Hamilton theorem, is a polynomial of degree at most in , so . (ii) Each amplitude is an entire function of ; it vanishes identically for (coefficients with are combinations of those with ), and otherwise has isolated zeros only. (iii) By (i), and , so and . □
By (ii), the states explore exactly the configurations that can carry weight in the solution. If the graph of is connected, generically contains all configurations, so arises only from finite sampling Eq. (13) or truncation, and the accuracy depends on how fast the solution decays away from the sampled configurations. A Trotterized propagator need not preserve $S_{\mathrm{Kr}} ({xref}Sec. IV C`).
Remark 1 (Galerkin optimality). For SPD , minimizes over all supported in , so the error cannot increase when is enlarged; this is the standard Galerkin property, and quantitative bounds under random sampling are given in Ref. 4. Noise-induced configurations therefore cannot increase the energy-norm error as long as ; noise degrades the accuracy only when this nesting fails or when is truncated.
Remark 2 (Sampling distribution). For a non-degenerate spectrum, the long-time average of is , whereas . Sampling weights each eigencomponent by , the solution by , so the most frequently sampled configurations need not carry the solution, increasingly so for large condition numbers[6]; on a finite grid, cross terms with are not averaged out. Residual-based selection is a natural alternative (Sec. IV F).
Relation to HHL and to SQD
Compared with HHL, the method requires no phase estimation, no ancilla, and no post-selection, and it returns the full classical vector ; the price is a classical solve of dimension . Both methods require the preparation of , which costs gates unless has exploitable structure. Compared with SQD for chemistry, the method shares the sample-then-project structure and uses the SKQD sampling protocol, but the classical step is a Galerkin linear solve, in which diagonalization is one option rather than the goal, and no configuration recovery is needed[3, 5]. Compared with the sample-based quantum linear solvers of Refs. 4 and 6, the method shares the measurement of time-evolved (Krylov) states and, with Ref. 4, the Galerkin reconstruction; it differs in implementing the evolution by Lie–Trotter products of the Pauli decomposition, whose circuit cost and leakage we analyze, whereas Ref. 6 analyzes qDRIFT compilation.
Implementation
The method is implemented in the Python package sqd-linsolve, built on Qiskit[1] and Qiskit Aer (tested with Qiskit 2.3.0 and 2.5.2 and Aer 0.17.2, with identical results), and in a self-contained notebook that produces the example, the hardware run, and the scalability test of Figure 3 and Figure 5. The package, the notebook, and scripts that reproduce the simulator tests of Secs. IV B, IV C, IV D, and IV F are provided as ancillary files with this article; the hardware run requires an IBM Quantum account. The circuits of Algorithm 1 are built with PauliEvolutionGate and submitted as a single batched job through one interface to a noiseless simulator, a noisy simulator, or IBM Quantum hardware. Gate counts refer to transpilation to . To isolate the subspace selection from Trotter errors, the tests of Secs. IV B, IV D, and IV F sample the exact distributions ; Trotter errors are quantified separately with actual circuits.
Figure 3. Simulation versus hardware for the example (, , per time point): noiseless AerSimulator (circles), AerSimulator with depolarizing errors of (two-qubit) and (one-qubit) and 2% readout errors (squares), and ibm_fez with dynamical decoupling and Pauli twirling (diamonds). (a) Exact time-dependent probabilities (lines) and measured frequencies at the sampling times (symbols). (b) Aggregated distribution , exact and measured, with shot-noise error bars. (c) Total variation distance between the measured and the exact at each sampling time; the dashed line is the value expected from shot noise alone. (d) Solution components recovered by the Galerkin projection on each platform, compared with the classical solution .

Figure 5. Scalability test for the banded (screened Poisson) and dense (random SPD) families with a point source (unlike the dense of Table VI), , (Gershgorin), and per time point. Solid lines: noiseless AerSimulator; dashed: AerSimulator with a noise model; dotted: sampling of the exact distributions (no circuits). (a) Pauli terms and CNOT gates per circuit, with the number of Trotter steps chosen for an infidelity below at . (b) Relative size of the untruncated configuration set. (c) Relative error of the untruncated solution (exact results plotted at ). (d) Fidelity after truncation to configurations; dotted black lines: oracle selection of the largest .
Results
We first validate the pipeline on a SPD example, using a noiseless simulator, a noisy simulator, and IBM Quantum hardware (Sec. IV A). We then test the method on a localized problem with (Sec. IV B), study the effect of readout noise, shots, and Trotter errors (Sec. IV C), quantify the circuit cost and the behavior for dense matrices (Sec. IV D), examine the scaling with (Sec. IV E), and compare with classical selection strategies (Sec. IV F).
Validation on simulator and hardware
We first consider the SPD matrix with rows , , , , eigenvalues , and , i.e. . Its Pauli decomposition is , and since the three non-identity strings commute, Eq. (5) is exact for any (the infidelity is at the round-off level, below for all in Figure 2). This gives four Pauli terms, compared with the maximum of for a real symmetric matrix. We used times , which satisfies Eq. (8) with , and . For , the circuits contain 24 CNOT gates and have depth 76; for , they contain 6 CNOT gates and have depth 22 (transpiler optimization level 1). Figure 2 shows the CNOT gate count, the circuit depth, and the infidelity as a function of .

Figure 2. 4 × 4 example: number of CNOT gates and circuit depth (left axis) and Trotter infidelity at (right axis) as a function of the number of Trotter steps . The CNOT count is . The infidelity stays at the round-off level because the three non-identity Pauli strings commute, so that the Lie–Trotter product is exact for every .
| 0.25 | 0.137 | 0.125 | 0.343 | 0.394 |
| 0.50 | 0.069 | 0.543 | 0.225 | 0.163 |
| 0.75 | 0.212 | 0.323 | 0.184 | 0.281 |
| 1.00 | 0.239 | 0.125 | 0.575 | 0.061 |
| 1.25 | 0.213 | 0.401 | 0.238 | 0.148 |
| 1.50 | 0.932 | 0.043 | 0.006 | 0.019 |
| 1.75 | 0.627 | 0.226 | 0.052 | 0.095 |
| 2.00 | 0.119 | 0.333 | 0.442 | 0.105 |
Table 1. Time-dependent distributions for the 4 × 4 example.
Since the product formula is exact, both settings produce the same output state. The distribution varies strongly with time: it concentrates 93.2% on at and 57.5% on at . The exact distributions at the eight sampling times are listed in Table I.
The results of the noiseless simulator, where all circuits run in one batch, are shown in Table II: the counts for each time point, the pooled counts, and the comparison of the empirical with the exact . The standard error of the pooled estimate is , because the circuits are independent binomial experiments.
The next step constructs , which selects the rows and columns of , solves , and lifts the result back with . All four configurations are observed, so , , and . The solution coincides with the reference to machine precision (, ).
When , as is necessary for large , the ranking of the configurations determines the accuracy. In the following sections we keep plus the most frequently sampled configurations and compare with the oracle, i.e. the configurations with the largest , which requires knowing the solution.
Figure 3 compares, for the 4 × 4 example, the distributions sampled on the noiseless AerSimulator, on AerSimulator with a noise model, and on the IBM Quantum processor ibm_fez with the exact distributions. Panels (a) and (c) resolve the comparison in time: the noiseless simulator follows the exact curves to within shot noise, whereas the noisy simulator and ibm_fez deviate by up to 0.18 and 0.28 in total variation distance, respectively, with the largest deviations at , where the exact distribution is most concentrated. Panel (b) shows the corresponding bias of the aggregated distribution of Eq. (11) towards the uniform distribution. Since all four configurations are nevertheless sampled on every platform (), the Galerkin solution coincides with irrespective of the noise [panel (d), Remark 1]. This outcome is guaranteed: by Eq. (13), missing the least probable configuration has probability below (with the exact and ), so the configuration set exhausts the space on each platform, and by Remark 1 added configurations cannot reduce the accuracy. The run therefore validates the pipeline and probes the sampled distributions, but not the effect of noise on the solution, which requires the truncated regime .
| 0.25 | 266 | 259 | 699 | 776 |
| 0.50 | 127 | 1118 | 422 | 333 |
| 0.75 | 393 | 663 | 367 | 577 |
| 1.00 | 484 | 235 | 1159 | 122 |
| 1.25 | 420 | 781 | 501 | 298 |
| 1.50 | 1860 | 85 | 11 | 44 |
| 1.75 | 1266 | 440 | 113 | 181 |
| 2.00 | 235 | 689 | 850 | 226 |
| Pooled counts | 5051 | 4270 | 4122 | 2557 |
| 0.3157 | 0.2669 | 0.2576 | 0.1598 | |
| 0.3186 | 0.2650 | 0.2581 | 0.1583 | |
| 0.0029 | 0.0033 | 0.0032 | 0.0027 |
Table 2. Noiseless AerSimulator counts per time point (), pooled counts, empirical , exact , and pooled standard error for the 4 × 4 example.
| Platform | ||||||
| Noiseless simulator | 0.0033 | 0.012 | 1.6 | 1.0 | 4 | 1 |
| Noisy simulator | 0.0251 | 0.077 | 135.6 | 9.2 | 4 | 1 |
| 0.0542 | 0.119 | 405.8 | 13.5 | 4 | 1 | |
| Shot noise | 0.0048 | 0.013 | – | – |
Table 3. Deviation of the sampled distributions from the exact ones for the example of Figure 3: TVD of the aggregated distribution, mean TVD of the per-time distributions, and largest -score of with the pooled variance , size of the configuration set, and fidelity of the solution. Last row: values expected from shot noise alone.
The deviations are quantified by the total variation distance between two distributions over the same configurations,
which is the largest difference between the probabilities that and assign to any set of configurations; it vanishes for identical distributions and equals one for distributions with disjoint supports. Even an ideal sampler gives because of the finite number of shots. For independent samples of , the expected value is approximately
which is 0.013 for the individual distributions (, averaged over ). For the pooled estimate , whose standard error is given in Table II, the corresponding value is 0.0048, and the statistic has the expected value . A TVD at this level means that the platform cannot be distinguished from an ideal sampler with the given number of shots; a TVD clearly above it signals hardware noise or Trotter error.
Table III summarizes the comparison. The noiseless simulator is at the shot-noise level (TVD = 0.0033, ). The noisy simulator and exceed it by factors of 5 and 11 in the aggregated TVD, with and 406 and largest deviations of 9.2 and 13.5 standard deviations, both in ; their per-time TVDs, 0.077 and 0.119 on average, are six and nine times the shot-noise level. These deviations are irrelevant for the solution when , but they matter in the truncated regime , in which the ranking of configurations by their sampled frequency determines the subspace.
Localized problems
To test the regime in which compression is possible, we consider the screened Poisson operator , i.e. the tridiagonal matrix with on the diagonal and on the off-diagonals, with and a point source at the center, . The solution decays exponentially away from the source (participation ratio at ). Equation (9) gives the bound (the true width is 3.9998 at ), and we use , i.e. , , and . The results below are those of the accompanying notebook (random seed 0); the dependence on the seed is stated where it matters.
For , sampling the exact distributions gives a configuration set of of the 1024 configurations, the contiguous window , and the solution reaches and (Table IV). Over 30 seeds, ranges from 31 to 35 (median 33) and from to . The window is set by and not by : for every , so that falls from 0.52 to 0.03 between and while stays at . Quadrupling the time window () enlarges the light cone to for this seed (median 111.5, range 109–114 over 30 seeds) and reduces the error to machine precision ().
| Platform | CNOTs per circuit | |||||||
| Circuits | 64 | 64 | 21248 | 32 | 0.500 | 8 | 0.995 | |
| Circuits | 128 | 64 | 45312 | 32 | 0.250 | 16 | 1.000 | |
| Exact | 64 | – | – | 33 | 0.516 | 8 | 0.995 | |
| Exact | 128 | – | – | 33 | 0.258 | 16 | 1.000 | |
| Exact | 256 | – | – | 33 | 0.129 | 32 | 1.000 | |
| Exact | 512 | – | – | 33 | 0.064 | 64 | 1.000 | |
| Exact | 1024 | – | – | 33 | 0.032 | 128 | 1.000 |
Table IV. Banded (screened Poisson) family, , point source at , , , , seed 0 (accompanying notebook). “Circuits”: noiseless AerSimulator, with the smallest power of two giving a Trotter infidelity below at (cap ); “exact”: sampling of the exact distributions. and : untruncated configuration set; : relative error of the untruncated solution; : fidelity after truncation to configurations (SQD; the oracle gives the same value to three digits in every row).
To test whether the compression survives actual circuits, the same problem was run with Lie–Trotter circuits on the noiseless simulator for and 128, with the smallest power of two for which the Trotter infidelity at is below (, infidelity for both sizes). The circuits select configurations, the window of the exact sampling without its outermost configuration and with no configuration outside it, and give , at the price of and CNOT gates per circuit (Table IV). Larger sizes were not run with circuits because of their cost (Sec. IV D).
Table V and Figure 4(a) compare truncated subspaces for : the most frequently sampled configurations, together with , reproduce the oracle choice of the configurations with the largest at every , as does classical greedy selection. Without , the two most frequently sampled configurations do not contain the source and give ; the source alone accounts for , which is the plateau of random selection with the source included, while random selection without it fails almost completely. Truncating to instead, as in Table IV, selection by sampling coincides with the oracle in every row.
| SQD | SQD without | Oracle | Greedy (classical) | Random, with source | |
| 2 | 0.745 | 0.000 | 0.745 | 0.745 | 0.600 |
| 4 | 0.931 | 0.931 | 0.931 | 0.931 | 0.601 |
| 8 | 0.995 | 0.995 | 0.995 | 0.995 | 0.602 |
| 16 | 0.99998 | 0.99998 | 0.99998 | 0.99998 | 0.603 |
| 32 | 0.611 |
Table V. Fidelity of truncated subspaces of size for the screened Poisson problem (, , , , , exact distributions, seed 0). SQD: the most frequently sampled configurations with included. Oracle: the configurations with the largest . Greedy: classical residual-based selection from . Random: mean over 1000 random sets, with the source included (last column); without the source the mean is at all .
Figure 4. (a) Fidelity versus subspace size for the screened Poisson problem of Table V (SQD shown without the inclusion of ), compared with the oracle, classical greedy residual selection, the classical Krylov support , and random selection. (b) Pauli terms and transpiled CNOT gates per Trotter step for the screened Poisson operator. (c) Mean configuration-set size and largest energy-norm error over five repetitions versus the readout bit-flip probability (untruncated). (d) Mean relative error and mean over five repetitions versus shots per time point (untruncated).
Noise, shots, and Trotter errors
Adding independent readout bit flips with probability , , and enlarges the untruncated configuration set from to 103, 214, and 519, while the energy-norm error decreases from to [Figure 4(c)], as Remark 1 predicts; with truncation to , the fidelity remains 0.99998 at all noise levels. The accuracy depends only weakly on the shot budget [Fig. 4(d)]: 20 shots per time point give and , and give and .
To test Proposition 1 with actual circuits, we interleaved two SPD blocks by a random permutation (, ) and placed in one block. Exact dynamics select precisely the 8-configuration Krylov support and give the exact solution with . Trotterized circuits on the noiseless simulator ( and 8) produce eight spurious configurations outside the support, so : the solution remains exact, but the compression is lost. Trotter errors thus degrade the efficiency of the method before its accuracy. This depends on the accuracy of the circuits: for the banded problem of Sec. IV B, with chosen for an infidelity below , no configuration outside the light cone appears (Table IV), but at – CNOT gates per circuit.
Circuit cost and dense matrices
For the tridiagonal operator of Sec. IV B, the Pauli decomposition contains exactly strings with weights up to , because each hopping term acts on the higher bits through projectors that expand into exponentially many strings. The number of CNOT gates per Trotter step, 20, 60, 148, 332, and 708 for to 7, roughly doubles per qubit (Figure 4(b)), and for an evolution to with infidelity requires , i.e. about CNOT gates per circuit. The bound on is loose by a factor for this operator, whereas Eq. (9) is tight (4 against a true width of 3.99998 at ).
For dense random SPD matrices with and uniform in , and the solutions are delocalized (participation ratio ). Because is dense, is the whole space and the rule of Eq. (12) cannot be applied; configurations are selected by the criterion of each column only. Table VI reports truncation to , averaged over 30 instances per . The spectral widths reach at , so that the grid of the example (, ) lies far outside Eq. (8): –. Lie–Trotter circuits with do not resolve the dynamics on this grid (infidelity 0.995 for and 0.98 for at ), so the table uses the exact distributions . On the grid of the example, selection by sampling frequency is statistically indistinguishable from random selection, as expected in the dephased regime of Remark 2; on the Nyquist grid (, , i.e. ) it reaches 74–80% of the oracle fidelity but remains below the oracle and the classical greedy selection, which agree to within 0.01 at every . Single instances vary widely (at the fidelity on the grid ranges from 0.00 to 0.45), so that results for one random matrix are not representative.
Scaling with the matrix dimension
Figure 5 shows how the method scales with the matrix dimension for the banded (screened Poisson) family of Sec. IV B and for dense random SPD matrices, both with a point source (unlike the dense of Table VI). The upper panels show the cost of the quantum step, i.e. the number of Pauli terms and CNOT gates per circuit (a), and the fraction of configurations selected by sampling (b). The lower panels show the accuracy: the relative error when all sampled configurations are used (c), and the fidelity after truncation to the most frequently sampled configurations, compared with the oracle selection (d).
For the banded family, saturates at for , so that decreases as while the error remains constant (), whereas the circuit cost grows with . For the truncated selection by sampling reproduces the oracle to the resolution of the plot, for both the noiseless circuits and the exact distributions; for the smallest subspaces (, and 16), the noisy simulator at and the noiseless simulator at fall below the oracle ( and 0.60 against 0.76 and 0.745). The dense family could be run with circuits only up to , where a circuit contains CNOT gates, and all configurations are sampled up to . With exact distributions, drops to 0.875 and 0.47 at and 256, and the error of the untruncated solution rises to a few : for delocalized solutions, a smaller subspace comes at the price of accuracy.
| Exact, grid | Exact, Nyquist grid | Random | Oracle | Greedy | ||||
| 16 | 136 | 66 | 5 | |||||
| 32 | 528 | 262 | 21 | |||||
| 64 | 2080 | 1035 | 82 | |||||
| 128 | 8256 | 4108 | 327 |
Table 6. Fidelity under truncation to for dense random SPD matrices (, and uniform in ); mean standard deviation over 30 instances per . “Exact, grid”: the 8 configurations with the largest exact on , ; “Exact, Nyquist grid”: the same on . “Random”: mean over 200 random sets per instance. “Oracle”: the 8 configurations with the largest . “Greedy”: classical residual-based selection started from . is the spectral width; is the grid step of the grid in units of the Nyquist step [Eq. (8) requires ].
Is the quantum step necessary?
For the screened Poisson problem, the untruncated configuration set coincides with the classical Krylov support obtained with 16 sparse matrix–vector products: both contain 33 configurations and give the same fidelity to ten digits [Figure 4(a)]. Classical residual-based selection, which starts from (from for the dense of Table VI) and repeatedly adds the configuration with the largest , reproduces the oracle in Table V and VI, and the conjugate-gradient method converges to a residual of in 34 iterations. The same conclusion was reached for elliptic problems with up to 4096 unknowns, where classical residual-greedy selection outperformed quantum sampling in every case studied[4]. These observations are general: when and the solution is concentrated on few configurations, the residual of a Galerkin solution is supported on and its neighbors, at most configurations, so classical residual-based selection is efficient in the same regime. Moreover, compression requires a small light cone, within which the evolution of a basis state can be simulated classically. A quantum advantage therefore requires problems in which the relevant configurations are not reachable by short classical expansions from , or in which sampling from is classically hard at the required times.
Discussion and outlook
The results point to the following directions. First, problem classes with genuinely polynomial circuits are required. Shifted local Hamiltonians, with a -local , have and turn the linear system
into a resolvent problem related to Green’s functions, for which SKQD has recently been developed; alternatively, banded matrices can be evolved with shift circuits rather than Pauli strings[18]. Second, the circuit depth for dense matrices can be reduced by truncating Eq. (1) to the largest coefficients, which is Frobenius-optimal at fixed because the Pauli basis is orthogonal. Third, Trotter-induced spurious configurations must be controlled, for instance by count thresholds, at the risk of the truncation errors discussed above, or by randomized compilation such as qDRIFT, for which error bounds are available[6]. Fourth, problems must be identified in which the relevant configurations are not accessible to the classical strategies of Sec. IV F, and hardware runs in the truncated regime and comparisons with HHL and classical iterative solvers at matched size are needed. Finally, the heuristic time grid of Eq. (8) could be replaced by the sampling schedules with provable shot complexity of Ref. 6.
Conclusions
We have extended sample-based quantum diagonalization to systems of linear equations, complementary to recently proposed sample-based quantum linear solvers[4, 6] by combining the SKQD sampling protocol with a Galerkin projection onto the sampled configurations, which always include the support of . The subspace solution is exact when the sampled configurations contain the Krylov support of , optimal in the energy norm for symmetric positive-definite matrices, and insensitive to noise-induced configurations as long as they do not displace the ideal ones. On a localized problem with (with exact sampling distributions), the method selects 33 configurations, reaches a relative error of , and its truncated subspaces are optimal; on IBM Quantum hardware, the sampled distribution of a example deviates visibly from the exact one, but the solution is recovered exactly because all configurations are sampled. The same tests show that the selected subspace coincides with that of inexpensive classical selection, in agreement with Ref. 4, that banded matrices require exponentially many Pauli terms in the binary encoding, and that Trotter errors inflate the subspace. With Pauli-string encoding and Lie–Trotter evolution, the circuits are therefore not shallow for banded matrices, the noise robustness has been demonstrated only for readout errors and, with gate errors and on hardware, only for configuration sets that exhaust the space, and the hardware test () does not yet probe the truncated regime. Identifying problems in which the relevant configurations are inaccessible to classical selection, and demonstrating the method on hardware in that regime, is the central open question.
Code availability
This article is accompanied by the open-source Python package sqd_linsolve and two Jupyter notebooks, provided as ancillary files (directory anc/) and released under the MIT License. The notebook reproduce_paper.ipynb uses the package to reproduce the numerical results of this article and compares each value with the one reported here. The notebook sqd_linear_systems_selfcontained.ipynb contains a self-contained implementation of the method with a step-by-step worked example, explanations of each step, and practical information on running the method on simulators and IBM Quantum hardware. The per-time counts of the IBM Quantum job of Figure 3 are provided in anc/data/; running new hardware jobs requires an IBM Quantum account.
Acknowledgments
Preliminary results of this work were presented at the Quantum AI 2026 Conference at Indiana University Indianapolis, Indianapolis, IN, USA, 14–16 August 2026.
We acknowledge the use of IBM Quantum services for this work. The views expressed are those of the author, and do not reflect the official policy or position of IBM or the IBM Quantum team.
References
- [1]A. W. Harrow, A. Hassidim, and S. Lloyd, Physical Review Letters 103, 150502 (2009).
- [2]J. Preskill, Quantum 2, 79 (2018).
- [3]J. Robledo-Moreno et al., Science Advances 11, eadu9991 (2025).
- [4]D. Ahn and B. Park, arXiv:2610.15586 (2026).arxiv.org/abs/2610.15586
- [5]J. Yu et al., arXiv:2501.09702 (2025).arxiv.org/abs/2501.09702
- [6]B. Park, K. Jeong, and D. Ahn, arXiv:2610.23138 (2026).arxiv.org/abs/2610.23138
- [7]D. Dervovic, M. Herbster, P. Mountney, S. Severini, N. Usher, and L. Wossnig, arXiv:1802.08227 (2018).arxiv.org/abs/1802.08227
- [8]K. Kanno, M. Kohda, R. Imai, S. Koh, K. Mitarai, W. Mizukami, and Y. O. Nakagawa, arXiv:2302.11320 (2023).DOI
- [9]A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, Nature Communications 5, 4213 (2014).
- [10]S. Piccinelli et al., arXiv:2508.02578 (2025).arxiv.org/abs/2508.02578
- [11]T. Selim, Sample-based quantum diagonalization for solving systems of linear equations, Talk at the Quantum AI 2026 Conference, Indiana University Indianapolis, Indianapolis, IN, USA, 14–16 August, 2026.arxiv.org/abs/2610.41708
- [12]L. Hantzko, L. Binkowski, and S. Gupta, Physica Scripta 99, 085128 (2024).
- [13]H. F. Trotter, Proceedings of the American Mathematical Society 10, 545 (1959).
- [14]S. Lloyd, Science 273, 1073 (1996).
- [15]A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Physical Review X 11, 011020 (2021).
- [18]J. Patel, C. Rangi, and K.-M. Tam, arXiv:2609.09147 (2026).arxiv.org/abs/2609.09147

