Systems of linear equations are ubiquitous across science, engineering, machine learning, and even finance. While classical methods can be prohibitively slow for large-scale problems, quantum linear systems algorithms offer the potential for exponential speedup in certain parameter regimes. However, a significant gap persists between this theoretical promise and practical implementation, as the advantages are often obscured by the substantial quantum resources and high sensitivity to noise inherent in current quantum hardware. One way to bridge this gap is through the use of Iterative Refinement, a classical post-processing scheme that can exponentially improve the accuracy to which a linear system of equations can be solved using low-precision arithmetic. In the context of quantum linear systems algorithms, such as the HHL algorithm proposed by Harrow, Hassidim, and Loyd, Iterative Refinement can greatly reduce the quantum resources required to calculate an accurate solution in terms of tomography cost, circuit volume, and fault-tolerant overhead. Here, we compute and benchmark highly precise solutions to linear systems of equations of up to eight variables by running HHL with Iterative Refinement on NISQ quantum computers. We also present our open-source implementation, emphasizing that our circuit is not tailored to specific problem instances, as most available implementations are.Systems of linear equations are ubiquitous across science, engineering, machine learning, and even finance. While classical methods can be prohibitively slow for large-scale problems, quantum linear systems algorithms offer the potential for exponential speedup in certain parameter regimes. However, a significant gap persists between this theoretical promise and practical implementation, as the advantages are often obscured by the substantial quantum resources and high sensitivity to noise inherent in current quantum hardware. One way to bridge this gap is through the use of Iterative Refinement, a classical post-processing scheme that can exponentially improve the accuracy to which a linear system of equations can be solved using low-precision arithmetic. In the context of quantum linear systems algorithms, such as the HHL algorithm proposed by Harrow, Hassidim, and Loyd, Iterative Refinement can greatly reduce the quantum resources required to calculate an accurate solution in terms of tomography cost, circuit volume, and fault-tolerant overhead. Here, we compute and benchmark highly precise solutions to linear systems of equations of up to eight variables by running HHL with Iterative Refinement on NISQ quantum computers. We also present our open-source implementation, emphasizing that our circuit is not tailored to specific problem instances, as most available implementations are.

IEEE International Conference on Quantum Computing and Engineering (QCE)Aug 30, 20250 citations

Implementing and Evaluating the Efficiency of a Quantum Linear Systems Algorithm

Dhruv Yalamanchi

Bulletin of the American Physical SocietyNov 5, 20200 citations

Solving linear systems on quantum hardware with hybrid HHL++

Romina Yalovetzky, Pierre Minssen, Dylan Herman +1 more

The limited capabilities of current quantum hardware significantly constrain the scale of experimental demonstrations of most quantum algorithmic primitives. This makes it challenging to perform benchmarking of the current hardware using useful quantum algorithms, i.e., application-oriented benchmarking. In particular, the Harrow-Hassidim-Lloyd (HHL) algorithm is a critical quantum linear algebra primitive, but the majority of the components of HHL are far out of the reach of noisy intermediate-scale quantum devices, which has led to the proposal of hybrid classical-quantum variants. The goal of this work is to further bridge the gap between proposed near-term friendly implementations of HHL and the kinds of quantum circuits that can be executed on noisy hardware. Our proposal adds to the existing literature of hybrid quantum algorithms for linear algebra that are more compatible with the current scale of quantum devices. Specifically, we propose two modifications to the Hybrid HHL algorithm proposed by Lee et al., leading to our algorithm Hybrid $\hbox {HHL}^{++}$ : (1) propose a novel algorithm for determining a scaling factor for the linear system matrix that maximizes the utility of the amount of ancillary qubits allocated to the phase estimation component of HHL, and (2) introduce a heuristic for compressing the HHL circuit. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers to solve different problem instances of small-scale portfolio optimization problems, leading to the largest experimental demonstrations of HHL for an application to date.The limited capabilities of current quantum hardware significantly constrain the scale of experimental demonstrations of most quantum algorithmic primitives. This makes it challenging to perform benchmarking of the current hardware using useful quantum algorithms, i.e., application-oriented benchmarking. In particular, the Harrow-Hassidim-Lloyd (HHL) algorithm is a critical quantum linear algebra primitive, but the majority of the components of HHL are far out of the reach of noisy intermediate-scale quantum devices, which has led to the proposal of hybrid classical-quantum variants. The goal of this work is to further bridge the gap between proposed near-term friendly implementations of HHL and the kinds of quantum circuits that can be executed on noisy hardware. Our proposal adds to the existing literature of hybrid quantum algorithms for linear algebra that are more compatible with the current scale of quantum devices. Specifically, we propose two modifications to the Hybrid HHL algorithm proposed by Lee et al., leading to our algorithm Hybrid $$\hbox {HHL}^{++}$$ : (1) propose a novel algorithm for determining a scaling factor for the linear system matrix that maximizes the utility of the amount of ancillary qubits allocated to the phase estimation component of HHL, and (2) introduce a heuristic for compressing the HHL circuit. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers to solve different problem instances of small-scale portfolio optimization problems, leading to the largest experimental demonstrations of HHL for an application to date.

arXiv:2110.15958Scientific ReportsSep 10, 202418 citations

Quantum Linear System Algorithms: Direct Methods

Osama M. Raisuddin, Suvranu De

Springer eBooksNov 14, 20250 citations

An analysis of iterative refinement for quantum linear system solvers

Adrian Harkness, Mohammadhossein Mohammadisiahroudi, Brandon Augustino +2 more

We present and analyze an iterative refinement (IR) framework for improving the precision dependence of algorithms that combine a quantum linear system algorithm (QLSA) with quantum state tomography. Existing QLSAs achieve polylogarithmic dependence on the inverse error tolerance to prepare a quantum state encoding the solution, but extracting a classical description of such a state via tomography typically introduces a polynomial dependence on the target precision. To retain polylogarithmic dependence in the inverse error tolerance throughout the entire process, we develop an IR scheme that solves a sequence of related linear systems to progressively refine the solution while requiring only fixed-precision quantum subroutines, finally obtaining a classical description of a high-precision solution. We analyze the proposed framework under three input models: quantum-read/classical-write RAM (QRAM), linear combinations of unitaries (LCU), and sparse-access oracles. We evaluate the proposed scheme through numerical experiments on both quantum simulators and real quantum hardware. The results demonstrate that iterative refinement efficiently improves the precision of the solution and exhibits robustness to hardware noise.We present and analyze an iterative refinement (IR) framework for improving the precision dependence of algorithms that combine a quantum linear system algorithm (QLSA) with quantum state tomography. Existing QLSAs achieve polylogarithmic dependence on the inverse error tolerance to prepare a quantum state encoding the solution, but extracting a classical description of such a state via tomography typically introduces a polynomial dependence on the target precision. To retain polylogarithmic dependence in the inverse error tolerance throughout the entire process, we develop an IR scheme that solves a sequence of related linear systems to progressively refine the solution while requiring only fixed-precision quantum subroutines, finally obtaining a classical description of a high-precision solution. We analyze the proposed framework under three input models: quantum-read/classical-write RAM (QRAM), linear combinations of unitaries (LCU), and sparse-access oracles. We evaluate the proposed scheme through numerical experiments on both quantum simulators and real quantum hardware. The results demonstrate that iterative refinement efficiently improves the precision of the solution and exhibits robustness to hardware noise.

quant-pharXiv:2609.10250Sep 10, 20260 citations

Quantum linear system solvers: A survey of algorithms and applications

Mauro E. S. Morales, Lirandë Pira, Philipp Schleich +7 more

Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with some applications. We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. The analysis begins by examining the Harrow-Hassidim-Lloyd (HHL) solver. We note its limitations and reliance on computationally expensive quantum methods, then highlight subsequent research efforts which aimed to address these limitations and optimize runtime efficiency and precision via various paradigms. We focus in particular on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. By doing so, we propose a taxonomy that categorizes these studies. Furthermore, by contextualizing these developments within the broader landscape of quantum computing, we explore the foundational work that have inspired and informed their development, as well as subsequent refinements. Finally, we discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics.Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with some applications. We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. The analysis begins by examining the Harrow-Hassidim-Lloyd (HHL) solver. We note its limitations and reliance on computationally expensive quantum methods, then highlight subsequent research efforts which aimed to address these limitations and optimize runtime efficiency and precision via various paradigms. We focus in particular on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. By doing so, we propose a taxonomy that categorizes these studies. Furthermore, by contextualizing these developments within the broader landscape of quantum computing, we explore the foundational work that have inspired and informed their development, as well as subsequent refinements. Finally, we discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics.

arXiv:2411.02522Reviews of Modern PhysicsJan 8, 20264 citations

\hbox {HHL}^{++}

: (1) propose a novel algorithm for determining a scaling factor for the linear system matrix that maximizes the utility of the amount of ancillary qubits allocated to the phase estimation component of HHL, and (2) introduce a heuristic for compressing the HHL circuit. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers to solve different problem instances of small-scale portfolio optimization problems, leading to the largest experimental demonstrations of HHL for an application to date.