⚛️ quantum physics

Extending Sample-based Quantum Diagonalization to Systems of Linear Equations

This paper extends sample-based quantum diagonalization to solve systems of linear equations by classically projecting onto a subspace of sampled computational-basis configurations, demonstrating that the method is robust against noise and achieves high accuracy on quantum hardware while identifying specific limitations regarding classical competitiveness and circuit depth.

Original authors: Taha Selim

Published 2026-11-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Taha Selim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern computing, solving systems of linear equations is a fundamental task, appearing everywhere from engineering simulations to financial modeling. These equations describe how different variables interact, and finding the solution means determining the specific values that satisfy all the relationships at once. For decades, classical computers have handled this work efficiently, but as problems grow larger and more complex, researchers have looked to quantum computers for a speed advantage. The most famous quantum approach to this problem, known as the HHL algorithm, promised to solve these equations exponentially faster than classical machines. However, that promise comes with a heavy price: it requires a level of precision and hardware stability that current quantum devices simply do not possess. These machines are noisy and prone to errors, making the deep, complex circuits required by the HHL algorithm impossible to run reliably today. This has created a pressing need for new methods that can work within the limitations of today's imperfect hardware, finding solutions without demanding the impossible.

A researcher has now extended a technique originally designed for chemistry to tackle these linear equations, offering a path forward for noisy quantum devices. Their approach, called sample-based quantum diagonalization, avoids the deep, error-prone circuits of previous methods. Instead of trying to calculate the entire solution at once, the method uses the quantum computer to take a series of snapshots. It prepares a quantum state representing the starting point of the problem and then lets it evolve over time, much like watching a ripple spread across a pond. At several specific moments, the researcher measures the state of the system, recording which configurations appear. These measurements are not the final answer, but rather a guide. They identify a small, manageable set of possibilities that are most likely to contain the solution. The heavy lifting of finding the actual numbers is then handed back to a classical computer, which solves the equation using only this small, curated set of options.

The researcher tested this pipeline on a small four-by-four example using both simulated environments and actual hardware from IBM. In these tests, the quantum device successfully sampled the necessary configurations, and the classical computer reconstructed the solution with perfect accuracy. The study then moved to a much larger problem with a dimension of 1,024, simulating a localized physical system where the solution is concentrated in a small area. Here, the method proved highly efficient, selecting just 33 configurations out of the 1,024 available to reach a relative error of 10 to the power of negative 5. This level of precision demonstrates that the method can compress a massive problem down to a tiny, solvable core. Crucially, the researcher found that the quantum step was robust against the readout errors common in current hardware; even when noise introduced extra, irrelevant configurations, the accuracy of the final solution did not degrade, provided the correct configurations were still present.

However, the study also drew a clear line around where this quantum advantage truly lies. While the method works beautifully for problems where the solution is concentrated in a small region, the researcher discovered that for these specific types of problems, a classical computer can often find the same small set of configurations just as easily and cheaply. By using standard mathematical tricks to track how the solution spreads, a classical algorithm could identify the same 33 configurations without needing a quantum computer at all. The paper explicitly rules out the idea that this method offers a universal shortcut for all linear systems. For problems where the solution is spread out across the entire system, or for matrices that are dense and complex, the quantum approach requires an exponential number of operations to describe the system, negating any potential speedup. Furthermore, the researcher noted that the quantum circuits used to evolve the system introduce their own errors, which can create "spurious" configurations that clutter the selection process, though these did not ruin the final accuracy in their tests.

The findings suggest that the future of this technology depends on finding the right kind of problem. The method is not a magic bullet that solves every linear equation faster; rather, it is a specialized tool that excels when the solution is localized and the quantum hardware can sample the relevant states without being overwhelmed by noise or circuit depth. The researcher concludes that for the method to provide a genuine advantage over classical computers, it must be applied to problems where the relevant configurations are inaccessible to classical strategies or where the quantum sampling itself is inherently difficult for classical machines to simulate. Until such problems are identified and tested on real hardware in a truncated regime, the most efficient path for solving these equations remains with classical algorithms. This work does not claim to have solved the linear equation problem for the quantum age, but it has successfully mapped the terrain, showing exactly where the quantum path is viable and where it leads to a dead end.

Technical Summary: Extending Sample-based Quantum Diagonalization to Systems of Linear Equations

Problem Statement
Solving systems of linear equations, $Ax = b$ , is a fundamental task in computational science. While the Harrow–Hassidim–Lloyd (HHL) algorithm offers a quantum speedup with logarithmic scaling in dimension $N$ , it relies on deep circuits involving quantum phase estimation, controlled rotations, and post-selection, rendering it impractical for current noisy intermediate-scale quantum (NISQ) hardware. Existing alternatives often require fault-tolerant resources or suffer from poor scaling with condition numbers and desired accuracy. There is a need for algorithms that operate natively within the limitations of present hardware, utilizing shallower circuits.

Methodology
This work extends Sample-based Quantum Diagonalization (SQD), originally developed for quantum chemistry, to solve linear systems. The approach follows a hybrid quantum-classical workflow:

Pauli Decomposition: The Hermitian matrix $A$ is decomposed into a sum of Pauli strings: $A = \sum_{l=1}^L c_l P_l$ .
State Preparation and Evolution: The right-hand side vector $b$ is encoded as an initial quantum state $|\psi_0\rangle$ . The system undergoes Trotterized time evolution under the Hamiltonian $A$ at discrete time points $t_j$ , approximating the state $|\psi(t_j)\rangle = e^{-iAt_j}|\psi_0\rangle$ using the Lie–Trotter product formula.
Sampling: The evolved states are measured in the computational basis at multiple time steps. The resulting bit-string configurations are aggregated to form an empirical distribution $\hat{p}_{agg}(z)$ .
Configuration Selection: A configuration set $C$ is constructed from the sampled bit strings (those with non-zero empirical probability) and the known support of $b$ .
Galerkin Projection: The linear system is projected onto the subspace spanned by the configurations in $C$ . This involves constructing a reduced matrix $A_{sub} = V^\dagger A V$ and vector $b_{sub} = V^\dagger b$ , where $V$ is the isometry of the selected basis states. The reduced system $A_{sub} x_{sub} = b_{sub}$ is solved classically, and the solution is lifted back to the full space as $x_{approx} = V x_{sub}$ .

Key Contributions
The paper makes four primary contributions relative to existing sample-based quantum linear solvers (specifically Refs. 4 and 6):

Theoretical Characterization of Exactness: The author proves that if the sampled configuration set $C$ contains the Krylov support of $b$ (the support of $\{A^k b\}$ ), the Galerkin solution is exact. Furthermore, for symmetric positive-definite (SPD) matrices, the solution is optimal in the energy norm; noise-induced configurations do not degrade accuracy as long as they do not displace the ideal configurations.
Cost Analysis in Pauli Encoding: The work analyzes the cost of the method in the Pauli-string encoding. It demonstrates that for banded matrices, the binary encoding requires $O(N)$ Pauli terms, and Lie–Trotter errors can populate spurious configurations outside the Krylov support, potentially negating the compression benefits before accuracy is lost.
Open-Source Implementation: An open-source Qiskit package (sqd_linsolve) is provided, offering a unified interface for noiseless simulators, noisy simulators, and IBM Quantum hardware.
Comparative Analysis: The method is benchmarked against classical Krylov methods, residual-based greedy selection, and oracle selection on localized and dense problem instances using exact sampling distributions.

Results
The author validates the pipeline through numerical experiments and hardware runs:

4x4 Example: On a noiseless simulator, a noisy simulator, and IBM Quantum hardware (ibm_fez), the method successfully solved a $4 \times 4$ SPD system. While the hardware distribution deviated from the exact distribution (due to noise), the solution was recovered exactly because all four configurations were sampled ( $R=N$ ), satisfying the condition for exactness.
Localized Problem ( $N=1024$ ): Using exact sampling distributions (bypassing circuit noise for this specific test) on a screened Poisson operator, the method selected a subspace of only $R=33$ configurations out of $N=1024$ . This yielded a relative error of $10^{-5}$ , and the truncated subspace coincided with the optimal oracle choice.
Noise and Errors: The method proved robust to readout noise; adding bit-flip errors enlarged the configuration set but did not degrade the energy-norm error, consistent with the theoretical optimality claims. However, Trotter errors were found to populate spurious configurations, which can inflate the subspace size and reduce efficiency.
Classical Comparison: For the tested localized problems, the quantum sampling step selected subspaces that coincided with those found by inexpensive classical residual-based selection and classical Krylov support analysis. For dense random matrices, the method performed comparably to random selection unless a finer time grid (Nyquist step) was used, yet it still lagged behind classical greedy selection.

Significance and Limitations
The paper concludes that the proposed method delineates the conditions under which a quantum sampling step can be advantageous. The results suggest that for problems where the solution is concentrated on few configurations and the matrix is given as a sum of polynomially many Pauli strings, the method is effective. However, the author notes a significant limitation: in the tested regimes (localized problems with small light cones), the quantum sampling step does not outperform classical residual-based selection.

The author states that identifying problem structures where relevant configurations are inaccessible to classical short expansions, or where sampling from $e^{-iAt}|b\rangle$ is classically hard, remains an open question. The work serves as a preliminary validation of the SQD framework for linear systems, highlighting that while the method is robust to certain noise types and theoretically sound, achieving a quantum advantage requires specific problem structures not yet demonstrated on current hardware. The paper emphasizes that for banded matrices, the Pauli-string encoding leads to deep circuits, and the current hardware tests have not yet probed the truncated regime ( $R < N$ ) where a quantum advantage might manifest.

Technical Summary: Extending Sample-based Quantum Diagonalization to Systems of Linear Equations

More like this