Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2411.02522 · Reviews of Modern Physics

Quantum linear system solvers: A survey of algorithms and applications

Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru‐Guzik, Lin Lin, Patrick Rebentrost, Dominic William Berry

Published Jan 8, 2026• 83 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/x6gh-d8gh

Related papers

The HHL algorithm: Implementation and research directions

Varsha Sambhaje, Anju Chaurasia

Linear systems of equations lie at the heart of numerous scientific and engineering challenges. In cutting-edge arena like artificial intelligence, machine learning and neuro-computation, these systems serve as a fundamental tool for mathematical modeling. Classical algorithms for solving linear systems have been extensively developed and forms the backbone of diverse applications across various scientific disciplines. While classical algorithms exist for solving linear systems, they often encounter limitations termed “NP-completeness” as data complexity increases. The emerging field of quantum computing offers a revolutionary approach to deal with these kinds of problems. The Harrow–Hassidim–Lloyd (HHL) algorithm tackles these challenges and opens new avenues for research. This study delves into the contemporary effectiveness of the HHL algorithm to address systems of linear equations. By examining recent research in quantum machine learning, we aim to assess the HHL algorithm’s potential to revolutionize the process of optimizing hyperparameters for machine learning models, resulting in increased efficiency and cost savings. This paper meticulously analyzes the HHL algorithm and explores its evolution from conception to the latest advancements. A comprehensive examination of the HHL algorithm, including its evolution over time, is thoroughly explored. The investigation delves into the potential challenges and limitations that might hinder the practical deployment of the HHL algorithm. Identifying these roadblocks will pave the way for future research and development efforts.

International Journal of Quantum Information•May 31, 2024•2 citations

A quantum linear system solver

Steven Herbert

Abstract In a sense, gate-based quantum computers are just machines that apply (extremely) large matrices to input states (vectors), and so it is natural to ask whether linear algebra applications can benefit from quantum computing. In the case of solving linear systems, this question has been answered with an emphatic ‘yes’. In 2009, Aram Harrow, Avinatan Hassidim, and Seth Lloyd proposed a quantum algorithm to solve linear systems exponentially faster than the best classical counterpart. The quantum linear systems solver is ubiquitously known by the initials of its inventors, ‘HHL’. As well as detailing HHL, this chapter also explores some of the quantum machine learning applications that have been proposed based on HHL along with results showing that these algorithms are often ‘dequantised’ in the problem space of interest – i.e., there exists an efficient classical ‘quantum-inspired’ algorithm.

Oxford University Press eBooks•Dec 8, 2025•0 citations

Quantum linear systems algorithms: a primer

Danial Dervovic, Mark Herbster, Peter Mountney +3 more

The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.

arXiv:1802.08227•Feb 22, 2018•140 citations

COMPARATIVE ANALYSIS OF CLASSICAL AND QUANTUM ALGORITHMS FOR SOLVING LINEAR SYSTEMS OF EQUATIONS: THEORETICAL INSIGHTS AND BENCHMARKING CHALLENGES

Journal of Theoretical and Applied Information Technology

Modern computers utilize a model based on a simple Turing machine concept. This study contains an extensive comparative review of classical and quantum algorithm approaches to solving a system of linear equations. The study details standard classical approaches like Gaussian Elimination or Conjugate Gradient Method and compares these with the algorithm of quantum theory algorithm HHL (Harrow-Hassidim-Lloyd). It considers the logic behind each of them, their benchmarks, scalability, implementation difficulties and practical use. Benchmarking results illustrate the fact that a classical approach continues to do especially good for small to moderate sized problems. However, quantum computation has the potential for an exponential speedup using algorithms like HHL in well-conditioned sparse matrices. The current limits of the hardware are discussed and future research directions needed to be able to utilize quantum computing for larger scale linear algebra problems are presented.

Journal of Theoretical and Applied Information Technology•Jun 30, 2025•0 citations

Benchmarking Highly Precise Quantum Linear Systems Algorithms

Adrian Harkness, Kate Saltovets, Mohammadhossein Mohammadisiahroudi +1 more

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, 2025•1 citation

A Note on "Quantum Algorithm for Linear Systems of Equations"

Yongzhen Xu, Yifan Huang, Zekun Ye +1 more

Recently, an efficient quantum algorithm for linear systems of equations introduced by Harrow, Hassidim, and Lloyd, has received great concern from the academic community. However, the error and complexity analysis for this algorithm seems so complicated that it may not be applicable to other filter functions for other tasks. In this note, a concise proof is proposed. We hope that it may inspire some novel HHL-based algorithms that can compute $F(A)|b\rangle$ for any computable $F$.

arXiv:1802.07194•Feb 20, 2018•0 citations
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.
Linear systems of equations lie at the heart of numerous scientific and engineering challenges. In cutting-edge arena like artificial intelligence, machine learning and neuro-computation, these systems serve as a fundamental tool for mathematical modeling. Classical algorithms for solving linear systems have been extensively developed and forms the backbone of diverse applications across various scientific disciplines. While classical algorithms exist for solving linear systems, they often encounter limitations termed “NP-completeness” as data complexity increases. The emerging field of quantum computing offers a revolutionary approach to deal with these kinds of problems. The Harrow–Hassidim–Lloyd (HHL) algorithm tackles these challenges and opens new avenues for research. This study delves into the contemporary effectiveness of the HHL algorithm to address systems of linear equations. By examining recent research in quantum machine learning, we aim to assess the HHL algorithm’s potential to revolutionize the process of optimizing hyperparameters for machine learning models, resulting in increased efficiency and cost savings. This paper meticulously analyzes the HHL algorithm and explores its evolution from conception to the latest advancements. A comprehensive examination of the HHL algorithm, including its evolution over time, is thoroughly explored. The investigation delves into the potential challenges and limitations that might hinder the practical deployment of the HHL algorithm. Identifying these roadblocks will pave the way for future research and development efforts.
Abstract In a sense, gate-based quantum computers are just machines that apply (extremely) large matrices to input states (vectors), and so it is natural to ask whether linear algebra applications can benefit from quantum computing. In the case of solving linear systems, this question has been answered with an emphatic ‘yes’. In 2009, Aram Harrow, Avinatan Hassidim, and Seth Lloyd proposed a quantum algorithm to solve linear systems exponentially faster than the best classical counterpart. The quantum linear systems solver is ubiquitously known by the initials of its inventors, ‘HHL’. As well as detailing HHL, this chapter also explores some of the quantum machine learning applications that have been proposed based on HHL along with results showing that these algorithms are often ‘dequantised’ in the problem space of interest – i.e., there exists an efficient classical ‘quantum-inspired’ algorithm.
The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.
Modern computers utilize a model based on a simple Turing machine concept. This study contains an extensive comparative review of classical and quantum algorithm approaches to solving a system of linear equations. The study details standard classical approaches like Gaussian Elimination or Conjugate Gradient Method and compares these with the algorithm of quantum theory algorithm HHL (Harrow-Hassidim-Lloyd). It considers the logic behind each of them, their benchmarks, scalability, implementation difficulties and practical use. Benchmarking results illustrate the fact that a classical approach continues to do especially good for small to moderate sized problems. However, quantum computation has the potential for an exponential speedup using algorithms like HHL in well-conditioned sparse matrices. The current limits of the hardware are discussed and future research directions needed to be able to utilize quantum computing for larger scale linear algebra problems are presented.
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.
Recently, an efficient quantum algorithm for linear systems of equations introduced by Harrow, Hassidim, and Lloyd, has received great concern from the academic community. However, the error and complexity analysis for this algorithm seems so complicated that it may not be applicable to other filter functions for other tasks. In this note, a concise proof is proposed. We hope that it may inspire some novel HHL-based algorithms that can compute F(A)∣b⟩F(A)|b\rangleF(A)∣b⟩ for any computable FFF.