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

IEEE journal on multiscale and multiphysics computational techniques

QW-HHL: A Quantum Computer Amenable General Matrix Equation Solver

Christopher D. Phillips, Helia Akbari, Vladimir Okhmatovski

Published Jan 1, 2026• 1 citation
Publisher

Abstract

Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique ways in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there is limited research on efficient, general, and fully implemented quantum procedures. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(sN log(N)) complexity, where N is the number of unknowns, and s is an upper bound on the number of nonzero elements in any row of the system matrix. This efficiency is competitive with the most sophisticated available classical solvers, and is independent of the structure of the input matrix. Hence, this procedure represents an important step towards the achievement of quantum advantage over classical algorithms for practical problems in numerical science.

DOI
10.1109/jmmct.2026.3678506

Related papers

A Quantum Computer Amenable Sparse Matrix Equation Solver

Christopher D. Phillips, Vladimir Okhmatovski

Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique way in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with $\mathcal{O}\left(N_{nz}\log\left(N\right)\right)$ complexity, where $N$ is the number of unknowns, and $N_{nz}$ is the total number of nonzero elements in the system matrix. This efficiency is independent of the matrix structure, and hence the quantum procedure can outperform classical methods for many common system types. We show this using the example of sparse approximate inverse (SPAI) preconditioning, which involves the application of matrix inverses for matrices with $N_{nz}=\mathcal{O}\left(N\right)$.

arXiv:2112.02600•Dec 5, 2021•3 citations

A Quantum-Walk-Unitary HHL Matrix Equation Solver and Its Challenges in the NISQ Era

Xinbo Li, Christopher Phillips, Ian Jeffrey +1 more

The Harrow/Hassidim/Lloyd algorithm is a celebrated quantum matrix equation solver. Its Hamiltonian simulation involves a quantum walk process. A newly developed Quantum Walk Unitary HHL (QWU-HHL) leverages the spectral relationship between the quantum walk operator and the system matrix, and uses the quantum walk operator as its unitary in the phase estimation directly, allowing Hamiltonian simulation in the classical HHL to be removed, hence improving its efficiency. Despite the potential of being exponentially faster than classical matrix equation solvers, HHL is not feasible in the noisy intermediate-scale quantum era because its quantum circuit is too deep to preserve an accurate solution. In this work, we investigate the error behavior of QWU-HHL on a 7-qubit quantum system. Instead of executing the entire circuit, the behaviors of its sub-circuits which each contain only an initialization and a single gate are recorded. The error caused by isolated initialization and operation are analyzed.

IEEE MTT-S International Microwave Symposium digest•Jun 11, 2023•1 citation

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

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

Solving Systems of Linear Equations: HHL from a Tensor Networks Perspective

Alejandro Mata Ali, Iñigo Perez Delgado, Marina Ristol Roura +2 more

This work presents a new approach for simulating the HHL linear systems of equations solver algorithm with tensor networks. First, a novel HHL in the qudits formalism, the generalization of qubits, is developed, and then its operations are transformed into an equivalent classical HHL, taking advantage of the non-unitary operations that they can apply. The main novelty of this proposal is to perform a classical simulation of the HHL as efficiently as possible to benchmark the algorithm steps according to its input parameters and the input matrix. The algorithm is applied to three classical simple simulation problems, comparing it with an exact inversion algorithm, and its performance is compared against an implementation of the original HHL simulated in the Qiskit framework, providing both codes. It is also applied to study the sensitivity of the HHL algorithm with respect to its hyperparameter values, reporting the existence of saturation points and maximal performance values. The results show that this approach can achieve a promising performance in computational efficiency to simulate the HHL process without quantum noise, providing a higher bound for its performance.

arXiv:2309.05290•Sep 11, 2023•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
Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique ways in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there is limited research on efficient, general, and fully implemented quantum procedures. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(sN log(N)) complexity, where N is the number of unknowns, and s is an upper bound on the number of nonzero elements in any row of the system matrix. This efficiency is competitive with the most sophisticated available classical solvers, and is independent of the structure of the input matrix. Hence, this procedure represents an important step towards the achievement of quantum advantage over classical algorithms for practical problems in numerical science.
Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique way in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(Nnzlog⁡(N))\mathcal{O}\left(N_{nz}\log\left(N\right)\right)O(Nnz​log(N)) complexity, where NNN is the number of unknowns, and NnzN_{nz}Nnz​ is the total number of nonzero elements in the system matrix. This efficiency is independent of the matrix structure, and hence the quantum procedure can outperform classical methods for many common system types. We show this using the example of sparse approximate inverse (SPAI) preconditioning, which involves the application of matrix inverses for matrices with Nnz=O(N)N_{nz}=\mathcal{O}\left(N\right)Nnz​=O(N).
The Harrow/Hassidim/Lloyd algorithm is a celebrated quantum matrix equation solver. Its Hamiltonian simulation involves a quantum walk process. A newly developed Quantum Walk Unitary HHL (QWU-HHL) leverages the spectral relationship between the quantum walk operator and the system matrix, and uses the quantum walk operator as its unitary in the phase estimation directly, allowing Hamiltonian simulation in the classical HHL to be removed, hence improving its efficiency. Despite the potential of being exponentially faster than classical matrix equation solvers, HHL is not feasible in the noisy intermediate-scale quantum era because its quantum circuit is too deep to preserve an accurate solution. In this work, we investigate the error behavior of QWU-HHL on a 7-qubit quantum system. Instead of executing the entire circuit, the behaviors of its sub-circuits which each contain only an initialization and a single gate are recorded. The error caused by isolated initialization and operation are analyzed.
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.
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)poly(\log N)poly(logN), in contrast to classical approaches, which in the general case exhibit a complexity of O(N3)O(N^3)O(N3), although they can achieve O(N)O(N)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.
This work presents a new approach for simulating the HHL linear systems of equations solver algorithm with tensor networks. First, a novel HHL in the qudits formalism, the generalization of qubits, is developed, and then its operations are transformed into an equivalent classical HHL, taking advantage of the non-unitary operations that they can apply. The main novelty of this proposal is to perform a classical simulation of the HHL as efficiently as possible to benchmark the algorithm steps according to its input parameters and the input matrix. The algorithm is applied to three classical simple simulation problems, comparing it with an exact inversion algorithm, and its performance is compared against an implementation of the original HHL simulated in the Qiskit framework, providing both codes. It is also applied to study the sensitivity of the HHL algorithm with respect to its hyperparameter values, reporting the existence of saturation points and maximal performance values. The results show that this approach can achieve a promising performance in computational efficiency to simulate the HHL process without quantum noise, providing a higher bound for its performance.
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.