betaFeedback

WorksPhysics and Astronomy

Extending Sample-based Quantum Diagonalization to Systems of Linear Equations

Abstract

Solving systems of linear equations, Ax=bAx=b, 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 AA is decomposed in the Pauli basis, the Trotterized time evolution of ∣b⟩|b\rangle 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 bb 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 4×44\times4 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 N=1024N=1024, SQD selects 33 configurations, reaches a relative error of 10−510^{-5}, 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 NN. The Harrow–Hassidim–Lloyd (HHL) algorithm, a well-known quantum algorithm for solving linear systems, prepares a state proportional to A−1∣b⟩A^{-1}\lvert b\rangle with a cost logarithmic in the dimension NN, 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 AA 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 e−iHtj∣ψ0⟩e^{-iHt_j}\lvert\psi_0\rangle, 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 e−iAtj∣b⟩e^{-iAt_j}|b\rangle 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, AA is Hermitian (symmetric positive-definite for the optimality statements) and bb has small support, e.g. a single basis state; a non-Hermitian AA 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 e−iAtbe^{-iAt}b equals the Krylov support of bb 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 NN 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 NN, 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.

Workflow of sample-based quantum diagonalization for linear systems

Figure 1. Workflow of sample-based quantum diagonalization for linear systems. Steps 1–2 (classical) decompose AA into Pauli strings and choose the time grid; Steps 3–4 (quantum) prepare ∣b⟩|b\rangle, apply the Trotterized evolution e−iAtje^{-iAt_j} for j=1,…,Mj = 1,\ldots,M, 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 N=2nN=2^n, the tensor products P∈{I,X,Y,Z}⊗nP\in\{I,X,Y,Z\}^{\otimes n} form an orthogonal basis for Hermitian matrices A∈CN×NA\in\mathbb{C}^{N\times N}, with Tr⁡(PI†PJ)=NδPIPJ\operatorname{Tr}(P_I^\dagger P_J)=N\delta_{P_I P_J}:

A=∑l=1LclPl,cl=1NTr⁡(Pl†A)∈R.(1)A=\sum_{l=1}^{L}c_lP_l,\qquad c_l=\frac{1}{N}\operatorname{Tr}(P_l^\dagger A)\in\mathbb{R}. \tag*{(1)}

The number LL of non-zero terms controls the circuit cost. For a real symmetric AA, strings with an odd number of YY factors are purely imaginary and do not contribute, so a generic real symmetric matrix has L=(4n+2n)/2=N(N+1)/2L=(4^n+2^n)/2=N(N+1)/2 terms and a generic complex Hermitian matrix has L=N2L=N^2, whereas a diagonal matrix has only L=NL=N 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 O(N2log⁡N)O(N^2\log N) operations with the tensorized Pauli decomposition[12]. We typically use symmetric positive-definite (SPD) matrices in our numerical experiments. If AA 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 ∣b⟩|b\rangle into a quantum state and the subsequent Trotterized evolution under the Hamiltonian AA. The normalized state ∣ψ0⟩=∣b⟩/∥b∥|\psi_0\rangle=|b\rangle/\lVert b\rVert is expanded in the eigenbasis A∣ϕk⟩=λk∣ϕk⟩A|\phi_k\rangle=\lambda_k|\phi_k\rangle,

∣ψ0⟩=∑kβk∣ϕk⟩,(2)|\psi_0\rangle=\sum_k\beta_k|\phi_k\rangle, \tag*{(2)}

with overlap amplitudes

βk=⟨ϕk∣ψ0⟩,∑k∣βk∣2=1,(3)\beta_k=\langle\phi_k|\psi_0\rangle,\qquad\sum_k|\beta_k|^2=1, \tag*{(3)}

and evolves as

∣ψ(t)⟩=e−iAt∣ψ0⟩=∑kβke−iλkt∣ϕk⟩.(4)|\psi(t)\rangle=e^{-iAt}|\psi_0\rangle=\sum_k\beta_ke^{-i\lambda_kt}|\phi_k\rangle. \tag*{(4)}

The propagator is approximated by the first-order Lie-Trotter product formula[13, 14],

e−iAt≈(∏l=1Le−iclPlt/S)S,(5)e^{-iAt}\approx\left(\prod_{l=1}^{L}e^{-ic_lP_lt/S}\right)^S, \tag*{(5)}

whose error is bounded by the commutators of the terms[15],

ϵTrot≤t22S∑j<l∣cjcl∣∥[Pj,Pl]∥.(6)\epsilon_{\mathrm{Trot}}\leq\frac{t^2}{2S}\sum_{j<l}|c_jc_l|\lVert[P_j,P_l]\rVert. \tag*{(6)}

hence the formula is exact when all terms commute. Since P2=IP^2=I, each factor is exactly a Pauli rotation,

e−iθP=cos⁡θI−isin⁡θP,(7)e^{-i\theta P}=\cos\theta I-i\sin\theta P, \tag*{(7)}

which for a string of weight ww costs 2(w−1)2(w-1) CNOT gates; the identity string contributes a global phase only. A circuit therefore contains at most LSLS rotations and 2(n−1)LS2(n-1)LS CNOT gates.

Sampling and the configuration set

Measuring ∣ψ(tj)⟩|\psi(t_j)\rangle in the computational basis yields configuration z∈{0,1}nz\in\{0,1\}^n with probability p(z∣tj)=∣⟨z∣ψ(tj)⟩∣2p(z\mid t_j)=|\langle z|\psi(t_j)\rangle|^2. Since p(z∣t)p(z\mid t) depends only on the eigenvalues through their differences, it is a trigonometric polynomial in tt whose angular frequencies lie in [−Δλ,Δλ][-\Delta\lambda,\Delta\lambda], with Δλ=λmax⁡−λmin⁡\Delta\lambda=\lambda_{\max}-\lambda_{\min}. Sampling it on a uniform grid of step Δt=tmax⁡/M\Delta t=t_{\max}/M without aliasing requires

Δt≤πΔλ⟺M≳tmax⁡Δλπ.(8)\Delta t\le\frac{\pi}{\Delta\lambda}\quad\Longleftrightarrow\quad M\gtrsim\frac{t_{\max}\Delta\lambda}{\pi}. \tag*{(8)}

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 AA, an inexpensive upper bound on Δλ\Delta\lambda follows from the Gershgorin theorem,

Δλ≤max⁡z(Azz+rz)−min⁡z(Azz−rz),(9)\Delta\lambda\le\max_z(A_{zz}+r_z)-\min_z(A_{zz}-r_z), \tag*{(9)}

with rz=∑z′≠z∣Az′z∣r_z=\sum_{z'\ne z}|A_{z'z}|. AzzA_{zz} is the expectation value of AA in the computational basis state ∣z⟩|z\rangle:

Azz=⟨z∣A∣z⟩.(10)A_{zz}=\langle z|A|z\rangle. \tag*{(10)}

In this work, we label the computational basis states by the bit strings z∈{0,1}nz\in\{0,1\}^n. The usual integer index is zz read as a binary number, and Az′z=⟨z′∣A∣z⟩A_{z'z}=\langle z'|A|z\rangle is the entry in row z′z' and column zz, which is off-diagonal when z′≠zz'\ne z. Evaluating Eq. (9) requires the rows of AA; when AA is given as a Pauli sum, the bound Δλ≤2∑Pl≠I∣cl∣\Delta\lambda\le2\sum_{P_l\ne I}|c_l| can be evaluated in O(L)O(L) operations.

The SKQD choice Δt∼π/∥A∥\Delta t\sim\pi/\|A\|, where ∥A∥=max⁡(∣λmax⁡∣,∣λmin⁡∣)\|A\|=\max(|\lambda_{\max}|,|\lambda_{\min}|), the operator (spectral) norm, i.e. the largest absolute eigenvalue, is related but not equivalent to Eq. (8)^{5}: for positive semidefinite AA one has Δλ≤∥A∥\Delta\lambda\le\|A\|, so that it satisfies Eq. (8) automatically (and is much finer than necessary when Δλ≪∥A∥\Delta\lambda\ll\|A\|), whereas in general Δλ≤2∥A∥\Delta\lambda\le2\|A\|, so that it can exceed the bound of Eq. (8) by at most a factor of two. Amplitude propagates through the sparsity graph of AA, so the configurations sampled up to tmax⁡t_{\max} form a light cone around supp⁡(b)\operatorname{supp}(b) whose radius, and hence the subspace size, is controlled by tmax⁡t_{\max} as we expect to see in the computational examples.

Components of p(z∣t)p(z \mid t) whose frequencies differ by less than ∼2π/tmax⁡\sim2\pi/t_{\max} are, moreover, not resolved within the time window, and each p(z∣tj)p(z \mid t_j) is only estimated up to shot noise ∼p(1−p)/Nshots\sim\sqrt{p(1-p)/N_{\mathrm{shots}}}. 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 ∥b−Axapprox∥\lVert b-Ax_{\mathrm{approx}}\rVert and improved by increasing tmax⁡t_{\max}, MM, or NshotsN_{\mathrm{shots}}. This is tested numerically in Sec. IV.

The exact aggregated distribution can be defined as the average over the MM sampling times,

pagg(z)=1M∑j=1Mp(z∣tj),(11)p_{\mathrm{agg}}(z)=\frac{1}{M}\sum_{j=1}^{M}p(z\mid t_j), \tag*{(11)}

which differs from the long-time average pˉ\bar{p} of Remark 2. Pooling the NshotsN_{\mathrm{shots}} samples of each of the MM circuits gives its empirical estimate p^agg(z)\hat{p}_{\mathrm{agg}}(z) and the configuration set

C={z∣p^agg(z)>0}∪supp⁡(b),R=∣C∣.(12)\mathcal{C}=\{z\mid\hat{p}_{\mathrm{agg}}(z)>0\}\cup\operatorname{supp}(b),\qquad R=\lvert\mathcal{C}\rvert. \tag*{(12)}

The support of bb, which is known classically, is always included: a set that misses it gives bsub=0b_{\mathrm{sub}}=0 below and hence a vanishing solution. More explicitly, under amplitude encoding, supp⁡(b)\operatorname{supp}(b) is the set of configurations occupied by ∣ψ0⟩\lvert\psi_0\rangle at t=0t=0, the initial state. That is, the time evolution spreads amplitude from these configurations through the couplings of AA.

A configuration z∉supp⁡(b)z\notin\operatorname{supp}(b) is missed only if it is absent from all MNshotsMN_{\mathrm{shots}} independent samples, so that, using 1−p≤e−p1-p\le e^{-p},

Pr⁡[z∉C]=∏j=1M(1−p(z∣tj))Nshots≤exp⁡(−MNshotspagg(z)).(13)\Pr[z\notin\mathcal{C}]=\prod_{j=1}^{M}\left(1-p(z\mid t_j)\right)^{N_{\mathrm{shots}}} \le\exp\left(-MN_{\mathrm{shots}}p_{\mathrm{agg}}(z)\right). \tag*{(13)}

Hence R<NR<N arises only from configurations of weight below ∼1/(MNshots)\sim1/(MN_{\mathrm{shots}}) or from explicit truncation. The Trotterized propagator does not preserve the sparsity pattern of AA, since individual Pauli strings can couple configurations that AA does not couple; by Eq. (13), with p(z∣tj)p(z\mid t_j) now the distributions of the Trotterized circuits, Trotter errors therefore populate spurious configurations unless their weight is below ∼1/(MNshots)\sim1/(MN_{\mathrm{shots}}). The sampling step is summarized in Algorithm 1.

Algorithm 1. Trotterized time-evolution sampling

Require: Hermitian A∈CN×NA\in\mathbb{C}^{N\times N} with Pauli decomposition A=∑l=1LclPlA=\sum_{l=1}^{L}c_lP_l; initial state ∣ψ0⟩\lvert\psi_0\rangle corresponding to bb; number of time samples MM; Trotter steps SS; maximum time tmax⁡t_{\max}; shots per circuit NshotsN_{\mathrm{shots}}

Ensure: Empirical aggregated distribution p^agg(z)\hat{p}_{\mathrm{agg}}(z) over z∈{0,1}nz\in\{0,1\}^{n}, n=log⁡2Nn=\log_2N

  1. p^agg(z)←0\hat{p}_{\mathrm{agg}}(z)\leftarrow0 for all zz

  2. for j=1j=1 to MM do

  3. tj←j⋅tmax⁡/Mt_j\leftarrow j\cdot t_{\max}/M ▷ time grid

  4. normalize the state ∣ψ0⟩\lvert\psi_0\rangle

  5. initialize circuit QjQ_j on nn qubits in state ∣ψ0⟩\lvert\psi_0\rangle

  6. for s=1s=1 to SS do ▷ Trotter steps

  7. for l=1l=1 to LL do

  8. θ←cltj/S\theta\leftarrow c_l t_j/S

  9. append e−iθPl=cos⁡θ I−isin⁡θ Ple^{-i\theta P_l}=\cos\theta\,I-i\sin\theta\,P_l to QjQ_j

  10. end for

  11. end for

  12. measure all qubits of QjQ_j in the computational basis, NshotsN_{\mathrm{shots}} times

  13. record counts {nz(j)}z\{n_z^{(j)}\}_z; set p^(z∣tj)←nz(j)/Nshots\hat{p}(z\mid t_j)\leftarrow n_z^{(j)}/N_{\mathrm{shots}}

  14. p^agg(z)←p^agg(z)+p^(z∣tj)/M\hat{p}_{\mathrm{agg}}(z)\leftarrow\hat{p}_{\mathrm{agg}}(z)+\hat{p}(z\mid t_j)/M for all zz

  15. end for

  16. return p^agg(z)\hat{p}_{\mathrm{agg}}(z)

Total gate count follows directly from the nested loops: LL rotations per Trotter step, SS steps per circuit, MM independent circuits, for M×L×SM\times L\times S rotation gates overall—all MM circuits are independent and are submitted as a single batched job in the implementation below, so MM affects total shot count and job size but not per-circuit depth. The implementation is described in Sec. III.

Galerkin solution

Let C={z1,…,zR}\mathcal{C}=\{z_1,\ldots,z_R\} and let

V=[∣z1⟩⋯∣zR⟩]∈CN×R(14)V=[\lvert z_1\rangle\cdots\lvert z_R\rangle]\in\mathbb{C}^{N\times R} \tag*{(14)}

be the corresponding isometry (V†V=IRV^\dagger V=I_R; the orthogonal projector onto the subspace is VV†VV^\dagger). The system is restricted to the subspace,

Asub=V†AV,bsub=V†b,(15)A_{\mathrm{sub}}=V^\dagger AV,\qquad b_{\mathrm{sub}}=V^\dagger b, \tag*{(15)}

which in practice amounts to selecting rows and columns of AA. For SPD AA, AsubA_{\mathrm{sub}} is SPD and the reduced system is solved directly. The spectral decomposition Asub=WΛW†A_{\mathrm{sub}}=W\Lambda W^\dagger gives

xsub=Wf(Λ)W†bsub,(16)x_{\mathrm{sub}}=Wf(\Lambda)W^\dagger b_{\mathrm{sub}}, \tag*{(16)}

with f(λ)=1/λf(\lambda)=1/\lambda, replaced for indefinite AA by a pseudo-inverse or the Tikhonov filter f(λ)=λ/(λ2+τ2)f(\lambda)=\lambda/(\lambda^2+\tau^2). This is the diagonalization step of the method; it carries out classically the 1/λ1/\lambda inversion that HHL performs coherently. The approximate solution is xapprox=Vxsubx_{\mathrm{approx}}=Vx_{\mathrm{sub}}, and its accuracy is quantified by the fidelity and the relative error,

F=∣⟨x^approx∣x^⟩∣2,η=∥xapprox−x∥∥x∥,(17)F=\lvert\langle\hat{x}_{\mathrm{approx}}\mid\hat{x}\rangle\rvert^2,\qquad\eta=\frac{\lVert x_{\mathrm{approx}}-x\rVert}{\lVert x\rVert}, \tag*{(17)}

and by the energy-norm error ∥xapprox−x∥A\lVert x_{\mathrm{approx}}-x\rVert_A, where x=xclassical=A−1bx=x_{\mathrm{classical}}=A^{-1}b, hats denote normalization, and ∥x∥A2=x†Ax\lVert x\rVert_A^2=x^\dagger Ax. Unlike a comparison of ∣xz∣2\lvert x_z\rvert^2 alone, these metrics are sensitive to the signs of the components.

Exactness, optimality, and targeting

We denote by supp⁡(v)\operatorname{supp}(v) the set of configurations on which vv is non-zero and assume AA invertible.

Proposition 1 (Krylov support). Let SKr=⋃m=0N−1supp⁡(Amb)S_{\mathrm{Kr}} = \bigcup_{m=0}^{N-1} \operatorname{supp}(A^m b) be the Krylov support of bb. Then (i) supp⁡(xclassical)⊆SKr\operatorname{supp}(x_{\mathrm{classical}}) \subseteq S_{\mathrm{Kr}}; (ii) supp⁡(e−iAtb)=SKr\operatorname{supp}(e^{-iAt}b) = S_{\mathrm{Kr}} for all tt outside a countable set; (iii) if C⊇SKrC \supseteq S_{\mathrm{Kr}} and AsubA_{\mathrm{sub}} is invertible, then xapprox=xclassicalx_{\mathrm{approx}} = x_{\mathrm{classical}} exactly.

Proof. (i) By the Cayley–Hamilton theorem, A−1A^{-1} is a polynomial of degree at most N−1N-1 in AA, so xclassical=A−1b∈span⁡{Amb}m=0N−1x_{\mathrm{classical}} = A^{-1}b \in\operatorname{span}\{A^m b\}_{m=0}^{N-1}. (ii) Each amplitude fz(t)=⟨z∣e−iAtb⟩=∑m≥0(−it)mm!⟨z∣Amb⟩f_z(t) = \langle z \mid e^{-iAt}b\rangle= \sum_{m\geq0} \frac{(-it)^m}{m!}\langle z \mid A^m b\rangle is an entire function of tt; it vanishes identically for z∉SKrz \notin S_{\mathrm{Kr}} (coefficients with m≥Nm \geq N are combinations of those with m<Nm < N), and otherwise has isolated zeros only. (iii) By (i), x=VV†xx = VV^\dagger x and b=VV†bb = VV^\dagger b, so AsubV†x=bsubA_{\mathrm{sub}}V^\dagger x = b_{\mathrm{sub}} and xapprox=VV†x=xx_{\mathrm{approx}} = VV^\dagger x = x. □

By (ii), the states e−iAtj∣b⟩e^{-iAt_j}\lvert b\rangle explore exactly the configurations that can carry weight in the solution. If the graph of AA is connected, SKrS_{\mathrm{Kr}} generically contains all NN configurations, so R<NR < N 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 AA, xapprox=VAsub−1V†bx_{\mathrm{approx}} = VA_{\mathrm{sub}}^{-1}V^\dagger b minimizes ∥xclassical−y∥A\lVert x_{\mathrm{classical}} - y\rVert_A over all yy supported in CC, so the error cannot increase when CC 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 Cnoisy⊇CidealC_{\mathrm{noisy}} \supseteq C_{\mathrm{ideal}}; noise degrades the accuracy only when this nesting fails or when CC is truncated.

Remark 2 (Sampling distribution). For a non-degenerate spectrum, the long-time average of p(z∣t)p(z \mid t) is pˉ(z)=∑k∣βk∣2∣⟨z∣ϕk⟩∣2\bar{p}(z) = \sum_k \lvert\beta_k\rvert^2\lvert\langle z \mid\phi_k\rangle\rvert^2, whereas xclassical,z=∥b∥∑kβkλk−1⟨z∣ϕk⟩x_{\mathrm{classical},z} = \lVert b\rVert\sum_k \beta_k\lambda_k^{-1}\langle z \mid\phi_k\rangle. Sampling weights each eigencomponent by ∣βk∣2\lvert\beta_k\rvert^2, the solution by βk/λk\beta_k/\lambda_k, 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 ∣λk−λk′∣≲π/tmax⁡\lvert\lambda_k-\lambda_{k'}\rvert\lesssim\pi/t_{\max} 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 xapproxx_{\mathrm{approx}}; the price is a classical solve of dimension RR. Both methods require the preparation of ∣b⟩\lvert b\rangle, which costs O(N)O(N) gates unless bb 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 4×44 \times4 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 MM 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 {CX,RZ,X,X}\{\mathrm{CX},R_Z,\sqrt{X},X\}. To isolate the subspace selection from Trotter errors, the tests of Secs. IV B, IV D, and IV F sample the exact distributions p(z∣tj)p(z \mid t_j); Trotter errors are quantified separately with actual circuits.

Figure 3. Simulation versus hardware for the 4×44 \times4 example (M=8M = 8, S=4S = 4, Nshots=2000N_{\mathrm{shots}} = 2000 per time point): noiseless AerSimulator (circles), AerSimulator with depolarizing errors of 10−210^{-2} (two-qubit) and 10−310^{-3} (one-qubit) and 2% readout errors (squares), and ibm_fez with dynamical decoupling and Pauli twirling (diamonds). (a) Exact time-dependent probabilities p(z∣t)p(z \mid t) (lines) and measured frequencies at the sampling times tjt_j (symbols). (b) Aggregated distribution pagg(z)p_{\mathrm{agg}}(z), exact and measured, with ±1σ\pm1\sigma shot-noise error bars. (c) Total variation distance between the measured and the exact p(z∣tj)p(z \mid t_j) 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 A−1bA^{-1}b.

Scalability test plots for banded and dense matrix families

Figure 5. Scalability test for the banded (screened Poisson) and dense (random SPD) families with a point source (unlike the dense bb of Table VI), M=8M = 8, Δt=π/Δλ\Delta t = \pi/\Delta\lambda (Gershgorin), and Nshots=2000N_{\mathrm{shots}} = 2000 per time point. Solid lines: noiseless AerSimulator; dashed: AerSimulator with a noise model; dotted: sampling of the exact distributions (no circuits). (a) Pauli terms LL and CNOT gates per circuit, with the number of Trotter steps chosen for an infidelity below 10−210^{-2} at tmax⁡t_{\max}. (b) Relative size R/NR/N of the untruncated configuration set. (c) Relative error of the untruncated solution (exact results plotted at 10−1610^{-16}). (d) Fidelity after truncation to R=max⁡(2,N/8)R = \max(2,N/8) configurations; dotted black lines: oracle selection of the RR largest ∣xz∣|x_z|.

Results

We first validate the pipeline on a 4×44 \times4 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 N=1024N = 1024 (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 NN (Sec. IV E), and compare with classical selection strategies (Sec. IV F).

Validation on simulator and hardware

We first consider the 4×44 \times4 SPD matrix with rows (5,3,1,−2)(5,3,1,-2), (3,5,2,−1)(3,5,2,-1), (1,2,5,−3)(1,2,5,-3), (−2,−1,−3,5)(-2,-1,-3,5), eigenvalues {1,3,5,11}\{1,3,5,11\}, and b=(0,0,0,1)Tb=(0,0,0,1)^{\mathsf{T}}, i.e. ∣ψ0⟩=∣11⟩\lvert\psi_0\rangle=\lvert11\rangle. Its Pauli decomposition is A=5I+XZ+2YY+3ZXA=5I+X Z+2Y Y+3Z X, and since the three non-identity strings commute, Eq. (5) is exact for any SS (the infidelity is at the round-off level, below 3×10−143 \times10^{-14} for all SS in Figure 2). This gives four Pauli terms, compared with the maximum of N(N+1)/2=10N(N+1)/2 = 10 for a real symmetric matrix. We used M=8M=8 times tj=0.25jt_j=0.25j, which satisfies Eq. (8) with Δλ=λmax⁡−λmin⁡=10\Delta\lambda=\lambda_{\max}-\lambda_{\min}=10, and Nshots=2000N_{\mathrm{shots}}=2000. For S=4S=4, the circuits contain 24 CNOT gates and have depth 76; for S=1S=1, 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 SS.

CNOT gate count, circuit depth, and Trotter infidelity as a function of Trotter steps

Figure 2. 4 × 4 example: number of CNOT gates and circuit depth (left axis) and Trotter infidelity at tmax⁡t_{\max} (right axis) as a function of the number of Trotter steps SS. The CNOT count is 6S6S. 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 SS.

tjt_jp(∣00⟩)p(\lvert00\rangle)p(∣01⟩)p(\lvert01\rangle)p(∣10⟩)p(\lvert10\rangle)p(∣11⟩)p(\lvert11\rangle)
0.250.1370.1250.3430.394
0.500.0690.5430.2250.163
0.750.2120.3230.1840.281
1.000.2390.1250.5750.061
1.250.2130.4010.2380.148
1.500.9320.0430.0060.019
1.750.6270.2260.0520.095
2.000.1190.3330.4420.105

Table 1. Time-dependent distributions p(z∣tj)p(z \mid t_j) for the 4 × 4 example.

Since the product formula is exact, both settings produce the same output state. The distribution p(z∣tj)p(z\mid t_j) varies strongly with time: it concentrates 93.2% on ∣00⟩\lvert00\rangle at tj=1.5t_j=1.5 and 57.5% on ∣10⟩\lvert10\rangle at tj=1.0t_j=1.0. The exact distributions at the eight sampling times are listed in Table I.

The results of the noiseless simulator, where all MM 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 p^agg\hat{p}_{\mathrm{agg}} with the exact paggp_{\mathrm{agg}}. The standard error of the pooled estimate is σz={∑jp(z∣tj)[1−p(z∣tj)]}1/2/(MNshots)\sigma_z=\left\{\sum_j p(z\mid t_j)[1-p(z\mid t_j)]\right\}^{1/2}/(M\sqrt{N_{\mathrm{shots}}}), because the MM circuits are independent binomial experiments.

The next step constructs V=[∣z1⟩⋯∣zR⟩]V=[\lvert z_1\rangle\cdots\lvert z_R\rangle], which selects the rows and columns of AA, solves Asubxsub=bsubA_{\mathrm{sub}}x_{\mathrm{sub}}=b_{\mathrm{sub}}, and lifts the result back with x=Vxsubx=Vx_{\mathrm{sub}}. All four configurations are observed, so R=NR=N, Asub=AA_{\mathrm{sub}}=A, and bsub=bb_{\mathrm{sub}}=b. The solution xSQD=(0.1939,−0.1394,0.2606,0.4061)x_{\mathrm{SQD}}=(0.1939,-0.1394,0.2606,0.4061) coincides with the reference xref=A−1bx_{\mathrm{ref}}=A^{-1}b to machine precision (F=1F=1, η≈0\eta\approx0).

When R<NR<N, as is necessary for large NN, the ranking of the configurations determines the accuracy. In the following sections we keep supp⁡(b)\operatorname{supp}(b) plus the most frequently sampled configurations and compare with the oracle, i.e. the RR configurations with the largest ∣xz∣\lvert x_z\rvert, 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 tj=1.5t_j=1.5, where the exact distribution is most concentrated. Panel (b) shows the corresponding bias of the aggregated distribution pagg(z)p_{\mathrm{agg}}(z) of Eq. (11) towards the uniform distribution. Since all four configurations are nevertheless sampled on every platform (R=NR=N), the Galerkin solution coincides with A−1bA^{-1}b irrespective of the noise [panel (d), Remark 1]. This outcome is guaranteed: by Eq. (13), missing the least probable configuration has probability below e−2500e^{-2500} (with the exact pagg=0.158p_{\mathrm{agg}}=0.158 and MNshots=1.6×104MN_{\mathrm{shots}}=1.6\times10^4), 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 R<NR<N.

tjt_j∣00⟩\lvert00\rangle∣01⟩\lvert01\rangle∣10⟩\lvert10\rangle∣11⟩\lvert11\rangle
0.25266259699776
0.501271118422333
0.75393663367577
1.004842351159122
1.25420781501298
1.501860851144
1.751266440113181
2.00235689850226
Pooled counts5051427041222557
p^agg\hat{p}_{\mathrm{agg}}0.31570.26690.25760.1598
paggp_{\mathrm{agg}}0.31860.26500.25810.1583
σz\sigma_z0.00290.00330.00320.0027

Table 2. Noiseless AerSimulator counts per time point (Nshots=2000N_{\mathrm{shots}}=2000), pooled counts, empirical p^agg\hat{p}_{\mathrm{agg}}, exact paggp_{\mathrm{agg}}, and pooled standard error σz\sigma_z for the 4 × 4 example.

PlatformTVDagg\mathrm{TVD}_{\mathrm{agg}}TVDtj\mathrm{TVD}_{t_j}χ2\chi^2max⁡∣z∣\max|z|RRFF
Noiseless simulator0.00330.0121.61.041
Noisy simulator0.02510.077135.69.241
ibm_fez\texttt{ibm\_fez}0.05420.119405.813.541
Shot noise0.00480.0133±2.43 \pm2.4≲2\lesssim2––

Table 3. Deviation of the sampled distributions from the exact ones for the 4×44 \times4 example of Figure 3: TVD of the aggregated distribution, mean TVD of the per-time distributions, χ2\chi^2 and largest ∣z∣|z|-score of p^agg\hat{p}_{\mathrm{agg}} with the pooled variance σz2\sigma_z^2, size RR of the configuration set, and fidelity FF 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,

TVD⁡(p,q)=12∑z∣p(z)−q(z)∣,(18)\operatorname{TVD}(p,q)=\frac{1}{2}\sum_z |p(z)-q(z)|, \tag*{(18)}

which is the largest difference between the probabilities that pp and qq assign to any set of configurations; it vanishes for identical distributions and equals one for distributions with disjoint supports. Even an ideal sampler gives TVD⁡>0\operatorname{TVD}>0 because of the finite number of shots. For NsN_s independent samples of pp, the expected value is approximately

TVD⁡shot≈122π∑zp(z)[1−p(z)]Ns,(19)\operatorname{TVD}_{\mathrm{shot}}\approx\frac{1}{2}\sqrt{\frac{2}{\pi}}\sum_z\sqrt{\frac{p(z)[1-p(z)]}{N_s}}, \tag*{(19)}

which is 0.013 for the individual distributions p(z∣tj)p(z\mid t_j) (Ns=2000N_s=2000, averaged over jj). For the pooled estimate p^agg\hat{p}_{\mathrm{agg}}, whose standard error σz\sigma_z is given in Table II, the corresponding value is 0.0048, and the statistic χ2=∑z[p^agg(z)−pagg(z)]2/σz2\chi^2=\sum_z[\hat{p}_{\mathrm{agg}}(z)-p_{\mathrm{agg}}(z)]^2/\sigma_z^2 has the expected value N−1=3±2.4N-1=3\pm2.4. 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, χ2=1.6\chi^2=1.6). The noisy simulator and ibm_fez\texttt{ibm\_fez} exceed it by factors of 5 and 11 in the aggregated TVD, with χ2=136\chi^2=136 and 406 and largest deviations of 9.2 and 13.5 standard deviations, both in ∣11⟩|11\rangle; 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 R=NR=N, but they matter in the truncated regime R<NR<N, 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 A=−Δh+μIA=-\Delta_h+\mu I, i.e. the tridiagonal matrix with 2+μ2+\mu on the diagonal and −1-1 on the off-diagonals, with μ=0.5\mu=0.5 and a point source b=∣z0⟩b=|z_0\rangle at the center, z0=N/2z_0=N/2. The solution decays exponentially away from the source (participation ratio 1/∑z∣x^z∣4=2.451/\sum_z|\hat{x}_z|^4=2.45 at N=1024N=1024). Equation (9) gives the bound Δλ≲4\Delta\lambda\lesssim4 (the true width is 3.9998 at n=10n=10), and we use Δt=π/4\Delta t=\pi/4, i.e. tmax⁡=2πt_{\max}=2\pi, M=8M=8, and Nshots=2000N_{\mathrm{shots}}=2000. The results below are those of the accompanying notebook (random seed 0); the dependence on the seed is stated where it matters.

For N=1024N=1024, sampling the exact distributions p(z∣tj)p(z\mid t_j) gives a configuration set of R=33R=33 of the 1024 configurations, the contiguous window z0±16z_0\pm16, and the solution reaches F=1−1.2×10−10F=1-1.2\times10^{-10} and η=1.1×10−5\eta=1.1\times10^{-5} (Table IV). Over 30 seeds, RR ranges from 31 to 35 (median 33) and η\eta from 0.8×10−50.8\times10^{-5} to 2.2×10−52.2\times10^{-5}. The window is set by tmax⁡t_{\max} and not by NN: R=33R=33 for every N≥64N\ge64, so that R/NR/N falls from 0.52 to 0.03 between N=64N=64 and N=1024N=1024 while η\eta stays at 1.1×10−51.1\times10^{-5}. Quadrupling the time window (M=32M=32) enlarges the light cone to R=109R=109 for this seed (median 111.5, range 109–114 over 30 seeds) and reduces the error to machine precision (6×10−176\times10^{-17}).

PlatformNNSSCNOTs per circuitRRR/NR/Nη\etaRtruncR_{\mathrm{trunc}}FtruncF_{\mathrm{trunc}}
Circuits646421248320.5001.7×10−51.7 \times10^{-5}80.995
Circuits1286445312320.2501.7×10−51.7 \times10^{-5}161.000
Exact64––330.5161.1×10−51.1 \times10^{-5}80.995
Exact128––330.2581.1×10−51.1 \times10^{-5}161.000
Exact256––330.1291.1×10−51.1 \times10^{-5}321.000
Exact512––330.0641.1×10−51.1 \times10^{-5}641.000
Exact1024––330.0321.1×10−51.1 \times10^{-5}1281.000

Table IV. Banded (screened Poisson) family, μ=0.5\mu= 0.5, point source at z0=N/2z_0 = N/2, Δt=π/ΔλGersh=π/4\Delta t = \pi/\Delta\lambda_{\mathrm{Gersh}} = \pi/4, M=8M = 8, Nshots=2000N_{\mathrm{shots}} = 2000, seed 0 (accompanying notebook). “Circuits”: noiseless AerSimulator, with SS the smallest power of two giving a Trotter infidelity below 10−210^{-2} at tmax⁡t_{\max} (cap S≤64S \le64); “exact”: sampling of the exact distributions. RR and R/NR/N: untruncated configuration set; η\eta: relative error of the untruncated solution; FtruncF_{\mathrm{trunc}}: fidelity after truncation to Rtrunc=N/8R_{\mathrm{trunc}} = N/8 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 N=64N=64 and 128, with SS the smallest power of two for which the Trotter infidelity at tmax⁡t_{\max} is below 10−210^{-2} (S=64S=64, infidelity 2.5×10−32.5\times10^{-3} for both sizes). The circuits select R=32R=32 configurations, the window of the exact sampling without its outermost configuration and with no configuration outside it, and give η=1.7×10−5\eta=1.7\times10^{-5}, at the price of 2.1×1042.1\times10^4 and 4.5×1044.5\times10^4 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 N=1024N=1024: the most frequently sampled configurations, together with supp⁡(b)\operatorname{supp}(b), reproduce the oracle choice of the RR configurations with the largest ∣xz∣|x_z| at every RR, as does classical greedy selection. Without supp⁡(b)\operatorname{supp}(b), the two most frequently sampled configurations do not contain the source and give F=0F=0; the source alone accounts for F=0.60F=0.60, which is the plateau of random selection with the source included, while random selection without it fails almost completely. Truncating to Rtrunc=N/8R_{\mathrm{trunc}}=N/8 instead, as in Table IV, selection by sampling coincides with the oracle in every row.

RRSQDSQD without supp⁡(b)\operatorname{supp}(b)OracleGreedy (classical)Random, with source
20.7450.0000.7450.7450.600
40.9310.9310.9310.9310.601
80.9950.9950.9950.9950.602
160.999980.999980.999980.999980.603
32>1−10−9> 1 - 10^{-9}>1−10−9> 1 - 10^{-9}>1−10−9> 1 - 10^{-9}>1−10−9> 1 - 10^{-9}0.611

Table V. Fidelity of truncated subspaces of size RR for the screened Poisson problem (N=1024N = 1024, μ=0.5\mu= 0.5, Δt=π/4\Delta t = \pi/4, M=8M = 8, Nshots=2000N_{\mathrm{shots}} = 2000, exact distributions, seed 0). SQD: the most frequently sampled configurations with supp⁡(b)\operatorname{supp}(b) included. Oracle: the RR configurations with the largest ∣xz∣|x_z|. Greedy: classical residual-based selection from supp⁡(b)\operatorname{supp}(b). Random: mean over 1000 random sets, with the source included (last column); without the source the mean is ≤0.02\le0.02 at all RR.

Figure 4. (a) Fidelity versus subspace size for the screened Poisson problem of Table V (SQD shown without the inclusion of supp⁡(b)\operatorname{supp}(b)), compared with the oracle, classical greedy residual selection, the classical Krylov support ⋃m′≤msupp⁡(Am′b)\bigcup_{m'\leq m}\operatorname{supp}(A^{m'}b), and random selection. (b) Pauli terms LL 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 RR over five repetitions versus shots per time point (untruncated).

Noise, shots, and Trotter errors

Adding independent readout bit flips with probability p=10−3p=10^{-3}, 10−210^{-2}, and 5×10−25\times10^{-2} enlarges the untruncated configuration set from R=33R=33 to 103, 214, and 519, while the energy-norm error decreases from 2×10−102\times10^{-10} to 2×10−102\times10^{-10} [Figure 4(c)], as Remark 1 predicts; with truncation to R=16R=16, 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 R=24R = 24 and η=4×10−4\eta= 4 \times10^{-4}, and 2×1042 \times10^{4} give R=35R = 35 and 5×10−65 \times10^{-6}.

To test Proposition 1 with actual circuits, we interleaved two 8×88 \times8 SPD blocks by a random permutation (N=16N = 16, L=136L = 136) and placed bb in one block. Exact dynamics select precisely the 8-configuration Krylov support and give the exact solution with R=N/2R = N/2. Trotterized circuits on the noiseless simulator (S=2S = 2 and 8) produce eight spurious configurations outside the support, so R=NR = N: 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 SS chosen for an infidelity below 10−210^{-2}, no configuration outside the light cone appears (Table IV), but at 2×1042 \times10^{4}–5×1045 \times10^{4} CNOT gates per circuit.

Circuit cost and dense matrices

For the tridiagonal operator of Sec. IV B, the Pauli decomposition contains exactly L=NL = N strings with weights up to nn, because each hopping term ∣z⟩⟨z+1∣\lvert z \rangle\langle z + 1 \rvert 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 n=3n = 3 to 7, roughly doubles per qubit (Figure 4(b)), and for n=6n = 6 an evolution to t=2πt = 2\pi with infidelity 2.5×10−32.5 \times10^{-3} requires S=64S = 64, i.e. about 2×1042 \times10^{4} CNOT gates per circuit. The bound 2∑P≠I∣cP∣=2n2\sum_{P \ne I}|c_P| = 2n on Δλ\Delta\lambda is loose by a factor n/2n/2 for this operator, whereas Eq. (9) is tight (4 against a true width of 3.99998 at n=10n = 10).

For dense random SPD matrices A=QQT+NIA = QQ^{\mathsf{T}} + N I with QijQ_{ij} and bib_i uniform in [0,1)[0,1), L=N(N+1)/2L = N(N+1)/2 and the solutions are delocalized (participation ratio ≈N/2\approx N/2). Because bb is dense, supp⁡(b)\operatorname{supp}(b) 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 R=8R = 8, averaged over 30 instances per NN. The spectral widths reach ≈4100\approx4100 at N=128N = 128, so that the grid of the 4×44 \times4 example (tj=0.25jt_j = 0.25j, M=8M = 8) lies far outside Eq. (8): 0.25 Δλ/π=50.25\ \Delta\lambda/\pi= 5–327327. Lie–Trotter circuits with S=4S = 4 do not resolve the dynamics on this grid (infidelity 0.995 for N=16N = 16 and 0.98 for N=32N = 32 at t=2t = 2), so the table uses the exact distributions p(z∣tj)p(z \mid t_j). On the grid of the 4×44 \times4 example, selection by sampling frequency is statistically indistinguishable from random selection, as expected in the dephased regime of Remark 2; on the Nyquist grid (tj=jπ/Δλt_j = j\pi/\Delta\lambda, M=8M = 8, i.e. tmax⁡=8π/Δλ≤0.4t_{\max} = 8\pi/\Delta\lambda\le0.4) 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 NN. Single instances vary widely (at N=32N = 32 the fidelity on the 4×44 \times4 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 NN for the banded (screened Poisson) family of Sec. IV B and for dense random SPD matrices, both with a point source (unlike the dense bb 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 R/NR/N 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 R=max⁡(2,N/8)R = \max(2,N/8) most frequently sampled configurations, compared with the oracle selection (d).

For the banded family, RR saturates at ≈33\approx33 for N≥64N \ge64, so that R/NR/N decreases as 1/N1/N while the error remains constant (≈10−5\approx10^{-5}), whereas the circuit cost grows with NN. For N≥32N \ge32 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 (R=2R = 2, N=8N = 8 and 16), the noisy simulator at N=8N = 8 and the noiseless simulator at N=16N = 16 fall below the oracle (F=0.61F = 0.61 and 0.60 against 0.76 and 0.745). The dense family could be run with circuits only up to N=32N = 32, where a circuit contains ∼104\sim10^4 CNOT gates, and all configurations are sampled up to N=64N = 64. With exact distributions, R/NR/N drops to 0.875 and 0.47 at N=128N = 128 and 256, and the error of the untruncated solution rises to a few 10−210^{-2}: for delocalized solutions, a smaller subspace comes at the price of accuracy.

NNLLΔλ\Delta\lambda0.25 Δλ/π0.25\,\Delta\lambda/\piExact, 4×44\times4 gridExact, Nyquist gridRandomOracleGreedy
161366650.46±0.130.46 \pm0.130.68±0.140.68 \pm0.140.47±0.010.47 \pm0.010.88±0.050.88 \pm0.050.88±0.050.88 \pm0.05
32528262210.23±0.130.23 \pm0.130.48±0.140.48 \pm0.140.22±0.010.22 \pm0.010.61±0.070.61 \pm0.070.60±0.070.60 \pm0.07
6420801035820.10±0.060.10 \pm0.060.25±0.080.25 \pm0.080.10±0.010.10 \pm0.010.33±0.040.33 \pm0.040.34±0.030.34 \pm0.03
128825641083270.04±0.020.04 \pm0.020.13±0.050.13 \pm0.050.05±0.000.05 \pm0.000.17±0.040.17 \pm0.040.18±0.010.18 \pm0.01

Table 6. Fidelity under truncation to R=8R=8 for dense random SPD matrices (A=QQT+NIA=QQ^{\mathsf{T}}+NI, QijQ_{ij} and bib_i uniform in [0,1)[0,1)); mean ±\pm standard deviation over 30 instances per NN. “Exact, 4×44\times4 grid”: the 8 configurations with the largest exact paggp_{\mathrm{agg}} on tj=0.25jt_j=0.25j, j=1,…,8j=1,\ldots,8; “Exact, Nyquist grid”: the same on tj=jπ/Δλt_j=j\pi/\Delta\lambda. “Random”: mean over 200 random sets per instance. “Oracle”: the 8 configurations with the largest ∣xz∣|x_z|. “Greedy”: classical residual-based selection started from arg⁡max⁡∣bz∣\arg\max|b_z|. Δλ\Delta\lambda is the spectral width; 0.25 Δλ/π0.25\,\Delta\lambda/\pi is the grid step of the 4×44\times4 grid in units of the Nyquist step [Eq. (8) requires ≲1\lesssim1].

Is the quantum step necessary?

For the screened Poisson problem, the untruncated configuration set coincides with the classical Krylov support ⋃m≤16supp⁡(Amb)\bigcup_{m\leq16}\operatorname{supp}(A^m b) 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 supp⁡(b)\operatorname{supp}(b) (from arg⁡max⁡∣bz∣\arg\max|b_z| for the dense bb of Table VI) and repeatedly adds the configuration with the largest ∣(b−Axapprox)z∣|(b-Ax_{\mathrm{approx}})_z|, reproduces the oracle in Table V and VI, and the conjugate-gradient method converges to a residual of 10−1010^{-10} 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 L=poly⁡(n)L = \operatorname{poly}(n) and the solution is concentrated on few configurations, the residual of a Galerkin solution is supported on CC and its neighbors, at most RLRL 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 supp⁡(b)\operatorname{supp}(b), or in which sampling from e−iAt∣b⟩e^{-iAt}|b\rangle 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, A=H+σIA = H + \sigma I with a kk-local HH, have L=O(n)L = O(n) 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 L′L' largest coefficients, which is Frobenius-optimal at fixed L′L' 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 b\mathbf{b}. The subspace solution is exact when the sampled configurations contain the Krylov support of b\mathbf{b}, 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 N=1024N = 1024 (with exact sampling distributions), the method selects 33 configurations, reaches a relative error of 10−510^{-5}, and its truncated subspaces are optimal; on IBM Quantum hardware, the sampled distribution of a 4×44 \times4 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 (N=4N = 4) 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. [1]A. W. Harrow, A. Hassidim, and S. Lloyd, Physical Review Letters 103, 150502 (2009).
  2. [2]J. Preskill, Quantum 2, 79 (2018).
  3. [3]J. Robledo-Moreno et al., Science Advances 11, eadu9991 (2025).
  4. [4]D. Ahn and B. Park, arXiv:2610.15586 (2026).arxiv.org/abs/2610.15586
  5. [5]J. Yu et al., arXiv:2501.09702 (2025).arxiv.org/abs/2501.09702
  6. [6]B. Park, K. Jeong, and D. Ahn, arXiv:2610.23138 (2026).arxiv.org/abs/2610.23138
  7. [7]D. Dervovic, M. Herbster, P. Mountney, S. Severini, N. Usher, and L. Wossnig, arXiv:1802.08227 (2018).arxiv.org/abs/1802.08227
  8. [8]K. Kanno, M. Kohda, R. Imai, S. Koh, K. Mitarai, W. Mizukami, and Y. O. Nakagawa, arXiv:2302.11320 (2023).DOI
  9. [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. [10]S. Piccinelli et al., arXiv:2508.02578 (2025).arxiv.org/abs/2508.02578
  11. [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. [12]L. Hantzko, L. Binkowski, and S. Gupta, Physica Scripta 99, 085128 (2024).
  13. [13]H. F. Trotter, Proceedings of the American Mathematical Society 10, 545 (1959).
  14. [14]S. Lloyd, Science 273, 1073 (1996).
  15. [15]A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Physical Review X 11, 011020 (2021).
  16. [18]J. Patel, C. Rangi, and K.-M. Tam, arXiv:2609.09147 (2026).arxiv.org/abs/2609.09147

Paper details

vlnc:W_vgz359qg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents