© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Classical and quantum resource analysis for the quantum linear systems

Jon Inouye

Published Jul 22, 2010• 0 citations

Abstract

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.

Related papers

Analysis of Classical and Quantum Resources for the Quantum Linear Systems Algorithm

Jon Inouye

The quantum algorithm by Harrow, Hassidim, and Lloyd solves a system of N linear equations and achieves exponential speedup over classical algorithms under certain conditions. The advantage to the algorithm is that log(N) rather than N registers are required. Given an N x N matrix A and vectors x and b, the quantum algorithm seeks to find x such that Ax = b. By representing vector b as a superposition of quantum states |b>, quantum phase estimation is used to find the corresponding eigenvalues of A. Applying the inverse Fourier transform, we solve for |x> such that |x> = A-1|b>. We model the algorithm using a quantum circuit diagram, with data qubits encoded using the Steane code for fault tolerant quantum phase estimation. Fresh ancilla for error correction are provided using an oracular pipelined ancilla architecture. We then analyze the classical and quantum resources needed for implementation. The significance of this case study is to examine how classical and quantum resources interact in implementing this algorithm. The issues raised in this analysis, such as fault tolerant phase estimation using pipelined ancilla, garbage collection, and the preparation of I/O registers to this architecture, will be explored in more detail in future research.

International Conference on Information Technology: New Generations•Apr 1, 2013•1 citation

Solving Linear Systems of Equations with the Quantum HHL Algorithm: A Tutorial on the Physical and Mathematical Foundations for Undergraduate Students

Lucas Queiroz Galvão, de Souza, Anna Beatriz M., A. Santos +2 more

Quantum computing enables the efficient resolution of complex problems, often outperforming classical methods across various applications. In 2009, Harrow, Hassidim and Lloyd proposed an algorithm for solving linear systems of equations, demonstrating exponential speedup (under ideal conditions) with a complexity of $poly(\log N)$, in contrast to classical approaches, which in the general case exhibit a complexity of $O(N^3)$, although they can achieve $O(N)$ in specific cases involving sparse matrices. This algorithm holds promise for advancements in machine learning, the solution of differential equations, linear regression, and cryptographic analysis. However, its structure is intricate, and there is a notable lack of detailed instructional materials in the literature. In this context, this paper presents a tutorial addressing the physical and mathematical foundations of the HHL algorithm, aimed at undergraduate students, explaining its theoretical construction and its implementation for solving linear equation systems. After discussing the underlying mathematical and physical concepts, we present numerical examples that illustrate the evolution of the quantum circuit. Finally, the algorithm's complexity, limitations, and future prospects are analyzed. The examples are compared with their classical simulations, allowing for an operational assessment of the algorithm's performance.

arXiv:2509.16640•Sep 20, 2025•0 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.

arXiv:2411.02522•Reviews of Modern Physics•Jan 8, 2026•4 citations

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

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•62 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

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.

The quantum algorithm by Harrow, Hassidim, and Lloyd solves a system of N linear equations and achieves exponential speedup over classical algorithms under certain conditions. The advantage to the algorithm is that log(N) rather than N registers are required. Given an N x N matrix A and vectors x and b, the quantum algorithm seeks to find x such that Ax = b. By representing vector b as a superposition of quantum states |b>, quantum phase estimation is used to find the corresponding eigenvalues of A. Applying the inverse Fourier transform, we solve for |x> such that |x> = A-1|b>. We model the algorithm using a quantum circuit diagram, with data qubits encoded using the Steane code for fault tolerant quantum phase estimation. Fresh ancilla for error correction are provided using an oracular pipelined ancilla architecture. We then analyze the classical and quantum resources needed for implementation. The significance of this case study is to examine how classical and quantum resources interact in implementing this algorithm. The issues raised in this analysis, such as fault tolerant phase estimation using pipelined ancilla, garbage collection, and the preparation of I/O registers to this architecture, will be explored in more detail in future research.

Quantum computing enables the efficient resolution of complex problems, often outperforming classical methods across various applications. In 2009, Harrow, Hassidim and Lloyd proposed an algorithm for solving linear systems of equations, demonstrating exponential speedup (under ideal conditions) with a complexity of

poly(\log N)

, in contrast to classical approaches, which in the general case exhibit a complexity of

O(N^3)

, although they can achieve

O(N)

in specific cases involving sparse matrices. This algorithm holds promise for advancements in machine learning, the solution of differential equations, linear regression, and cryptographic analysis. However, its structure is intricate, and there is a notable lack of detailed instructional materials in the literature. In this context, this paper presents a tutorial addressing the physical and mathematical foundations of the HHL algorithm, aimed at undergraduate students, explaining its theoretical construction and its implementation for solving linear equation systems. After discussing the underlying mathematical and physical concepts, we present numerical examples that illustrate the evolution of the quantum circuit. Finally, the algorithm's complexity, limitations, and future prospects are analyzed. The examples are compared with their classical simulations, allowing for an operational assessment of the algorithm's performance.

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.

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

.

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.