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:1802.07194

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

Yongzhen Xu, Yifan Huang, Zekun Ye, Lvzhou Li

Published Feb 20, 2018• 0 citations
arXivHTMLPDF

Abstract

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$.

DOI
10.48550/arxiv.1802.07194

Related papers

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.

arXiv:2411.02522•Reviews of Modern Physics•Jan 8, 2026•83 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

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

Classical and quantum resource analysis for the quantum linear systems

Jon Inouye

Recently (2009) a quantum algorithm for solving a system of linear equations\nhas been proposed. The algorithm by Harrow, Hassidim, and Lloyd has attracted\nconsiderable attention in the quantum algorithms community, due to the broad\npotential applications of a rapid linear equations solver. The contribution of this\nthesis is to analyze the classical and quantum resources required for implementation.\nThe thesis has two major tasks. We first survey the field of quantum\nalgorithms. The papers which established this field (e.g., Feynman and Deutsch) to\nrecent works are reviewed. Different classes of quantum algorithms are examined,\nincluding those based on the Fourier transform, quantum searching, and quantum\nwalk.\nFor the second task, we focus on the algorithm by Harrow, Hassidim, and\nLloyd. The advantages of the algorithm are an exponential performance gain over\nclassical algorithms (under conditions of sparse operator matrices and few selected\nmeasurements from the solution set), and fewer data registers.\nIn the second part of the thesis, we study the classical resources required for\nimplementation of the algorithm. Since classical resources can determine the ultimate\nefficiency of the quantum algorithm, the optimal use of classical resources is\nmandatory.\nWe demonstrate how a classical computer may handle certain computations\n(e.g., time evolution) and feed these into the quantum circuit implementing the\nalgorithm. Thus, the classical and quantum resources for implementing the algorithm\nare described. Through a detailed analysis of the classical resources, we hope to\nunderstand how these resources may be optimized. This work can therefore\ncontribute to the design of efficient quantum algorithms.

•Jul 22, 2010•0 citations

Quantum Algorithm for Linear Systems of Equations

Aram W. Harrow, Avinatan Hassidim, Seth Lloyd

Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix $A$ and a vector $\stackrel{\ensuremath{\rightarrow}}{b}$, find a vector $\stackrel{\ensuremath{\rightarrow}}{x}$ such that $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$. We consider the case where one does not need to know the solution $\stackrel{\ensuremath{\rightarrow}}{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\stackrel{\ensuremath{\rightarrow}}{x}$, e.g., ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ for some matrix $M$. In this case, when $A$ is sparse, $N\ifmmode\times\else\texttimes\fi{}N$ and has condition number $\ensuremath{\kappa}$, the fastest known classical algorithms can find $\stackrel{\ensuremath{\rightarrow}}{x}$ and estimate ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ in time scaling roughly as $N\sqrt{\ensuremath{\kappa}}$. Here, we exhibit a quantum algorithm for estimating ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ whose runtime is a polynomial of $\mathrm{log}(N)$ and $\ensuremath{\kappa}$. Indeed, for small values of $\ensuremath{\kappa}$ [i.e., $\mathrm{poly}\mathrm{log}(N)$], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.

arXiv:0811.3171•Physical Review Letters•Oct 7, 2009•3,798 citations

Study of Error Propagation and Generation in Harrow-Hassidim-Lloyd (HHL) Quantum Algorithm

Anika Zaman, Hiu Yung Wong

In this paper, we study the error propagation and generation in the Harrow-Hassidim-Lloyd (HHL) quantum algorithm runs on IBM-Q hardware with the help of a MATLAB simulator. HHL is a quantum algorithm that can provide exponential speedup over the fastest classical algorithm (conjugate gradient method) in solving systems of linear equations (SLE). However, without error correction, it cannot give correct results even in a 2-variable system due to its complexity. In this study, an HHL quantum circuit for a 2-variable SLE is implemented in IBM-Q and the error is extracted after each stage of the circuit and compared to a MATLAB simulator. We identified three major sources of errors, namely single-qubit flipping, gate infidelity, and error propagation. We also found that at the ancillary bit rotation stage, the error becomes large but the encoded solution still has high fidelity. However, the solution is mostly lost after the inverse quantum phase estimation which is necessary to extract the solution efficiently. Therefore, it is suggested that error correction resources, if limited, should be added to the second half of the circuit.

IEEE Latin American Electron Devices Conference (LAEDC)•Jul 4, 2022•16 citations
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.
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.
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.
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.
Recently (2009) a quantum algorithm for solving a system of linear equations\nhas been proposed. The algorithm by Harrow, Hassidim, and Lloyd has attracted\nconsiderable attention in the quantum algorithms community, due to the broad\npotential applications of a rapid linear equations solver. The contribution of this\nthesis is to analyze the classical and quantum resources required for implementation.\nThe thesis has two major tasks. We first survey the field of quantum\nalgorithms. The papers which established this field (e.g., Feynman and Deutsch) to\nrecent works are reviewed. Different classes of quantum algorithms are examined,\nincluding those based on the Fourier transform, quantum searching, and quantum\nwalk.\nFor the second task, we focus on the algorithm by Harrow, Hassidim, and\nLloyd. The advantages of the algorithm are an exponential performance gain over\nclassical algorithms (under conditions of sparse operator matrices and few selected\nmeasurements from the solution set), and fewer data registers.\nIn the second part of the thesis, we study the classical resources required for\nimplementation of the algorithm. Since classical resources can determine the ultimate\nefficiency of the quantum algorithm, the optimal use of classical resources is\nmandatory.\nWe demonstrate how a classical computer may handle certain computations\n(e.g., time evolution) and feed these into the quantum circuit implementing the\nalgorithm. Thus, the classical and quantum resources for implementing the algorithm\nare described. Through a detailed analysis of the classical resources, we hope to\nunderstand how these resources may be optimized. This work can therefore\ncontribute to the design of efficient quantum algorithms.
Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix AAA and a vector $\stackrel{\ensuremath{\rightarrow}}{b}$, find a vector $\stackrel{\ensuremath{\rightarrow}}{x}$ such that $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$. We consider the case where one does not need to know the solution $\stackrel{\ensuremath{\rightarrow}}{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\stackrel{\ensuremath{\rightarrow}}{x}$, e.g., ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ for some matrix MMM. In this case, when AAA is sparse, $N\ifmmode\times\else\texttimes\fi{}N$ and has condition number $\ensuremath{\kappa}$, the fastest known classical algorithms can find $\stackrel{\ensuremath{\rightarrow}}{x}$ and estimate ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ in time scaling roughly as $N\sqrt{\ensuremath{\kappa}}$. Here, we exhibit a quantum algorithm for estimating ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ whose runtime is a polynomial of log(N)\mathrm{log}(N)log(N) and $\ensuremath{\kappa}$. Indeed, for small values of $\ensuremath{\kappa}$ [i.e., polylog(N)\mathrm{poly}\mathrm{log}(N)polylog(N)], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.
In this paper, we study the error propagation and generation in the Harrow-Hassidim-Lloyd (HHL) quantum algorithm runs on IBM-Q hardware with the help of a MATLAB simulator. HHL is a quantum algorithm that can provide exponential speedup over the fastest classical algorithm (conjugate gradient method) in solving systems of linear equations (SLE). However, without error correction, it cannot give correct results even in a 2-variable system due to its complexity. In this study, an HHL quantum circuit for a 2-variable SLE is implemented in IBM-Q and the error is extracted after each stage of the circuit and compared to a MATLAB simulator. We identified three major sources of errors, namely single-qubit flipping, gate infidelity, and error propagation. We also found that at the ancillary bit rotation stage, the error becomes large but the encoded solution still has high fidelity. However, the solution is mostly lost after the inverse quantum phase estimation which is necessary to extract the solution efficiently. Therefore, it is suggested that error correction resources, if limited, should be added to the second half of the circuit.