Extending Sample-based Quantum Diagonalization to Systems of Linear Equations
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⟩ 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×4 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.
Related
- Methods for Deriving Nonlinear Kinetic Equations from the Dynamics of Quantum Systems
- Parameter Estimation for Diffusive Stochastic Master Equations in Continuously Observed Quantum Systems
- Extending geometric integrators to control systems - an example study
- Finite Sample Identification of Analytic Nonlinear Systems
- Minimum-Energy Control for Stochastic Linear Systems: A Data-Driven Approach with Finite-Sample Guarantees
BibTeX
@misc{selim2026extending,
title = {{Extending Sample-based Quantum Diagonalization to Systems of Linear Equations}},
author = {Taha Selim},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41708},
eprint = {2610.41708},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41708},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Extending Sample-based Quantum Diagonalization to Systems of Linear Equations
AU - Taha Selim
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41708
UR - https://arxiv.org/abs/2610.41708
AB - 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⟩ 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×4 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.
ER -