aiqbench analysis
This paper adapts sample-based quantum diagonalization, a method from quantum chemistry, to solve linear systems $Ax=b$ as an alternative to HHL, which needs phase estimation and post-selection that are impractical on today's noisy hardware. The authors prove conditions under which noisy samples don't degrade the classical Galerkin solution, and demonstrate it on IBM hardware. The paper is candid about limits: the selected subspace matches cheap classical selection heuristics, banded matrices blow up in Pauli-term count, and Trotter errors add spurious configurations, so readers should treat the speedup case as unproven.
Extending Sample-based Quantum Diagonalization to Systems of Linear Equations
arXiv:2610.41708v1 Announce Type: new Abstract: Solving systems of linear equations, $Ax=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 $A$ is decomposed in the Pauli basis, the Trotterized time evolution of $|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 $b$ 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\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=1024$, SQD selects 33 configurations, reaches a relative error of $10^{-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.
Abstract:Solving systems of linear equations, $Ax=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 $A$ is decomposed in the Pauli basis, the Trotterized time evolution of $|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 $b$ 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\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=1024$, SQD selects 33 configurations, reaches a relative error of $10^{-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.
13 pages, 5 figures, 6 tables. Code: Python package sqd_linsolve (MIT License) with two notebooks in the ancillary files: this http URL reproduces the numerical results of the paper; this http URL gives a self-contained, step-by-step implementation with explanations and a worked example
Quantum Physics (quant-ph); Numerical Analysis (math.NA)
arXiv:2610.41708 [quant-ph]
(or arXiv:2610.41708v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2610.41708 arXiv-issued DOI via DataCite (pending registration)
Full text under the publisher's open licence · 309 words