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

Laser Physics Letters

Quantum algorithm for solving matrix equations of the form AX = B

Xu Li, Xiaoqi Liu, Jin‐Min Liang, Jing Wang, Ming Li, Shu‐Qian Shen

Published Mar 21, 2022• 10 citations
Publisher

Abstract

Abstract Solving linear systems of equations is of vital importance in various fields of science. With the scale of calculation soaring, classical computers are intractable, and the advantage of quantum computing is reflected. Quantum algorithm has exponential acceleration in solving the linear systems A x ⃗ = b ⃗ for sparse and well-conditioned coefficient matrix A with dimension N × N . In this paper, we present a quantum algorithm to solve matrix equations of the form AX = B , where X = ( x ⃗ 1 , x ⃗ 2 , … , x ⃗ n ) , B = ( b ⃗ 1 , b ⃗ 2 , … , b ⃗ n ) , x ⃗ k and b ⃗ k are unit vectors. The problem can be intuitively treated as solving n linear systems simultaneously, which will needs O ( n log N ) complexity by the famous HHL algorithm. We demonstrate that in our algorithm the scale of complexity is O ( log n N ) . In the error analysis part, phase estimation is discussed in details.

DOI
10.1088/1612-202x/ac5b5a

Related papers

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

Experimental Quantum Computing to Solve Systems of Linear Equations

Xiang Cai, Christian Weedbrook, Zu-En Su +7 more

Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2×2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.

arXiv:1302.4310•Physical Review Letters•Jun 6, 2013•186 citations

Quantum Algorithm for the Toeplitz Systems

Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan +2 more

Solving the Toeplitz systems, which is to find the vector $x$ such that $T_nx = b$ given a $n\times n$ Toeplitz matrix $T_n$ and a vector $b$, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the Toeplitz systems, in which a quantum state encoding the solution with error $\epsilon$ is generated. It is shown that our algorithm's complexity is nearly linear in the condition number, and polylog in the dimensions $n$ and in the inverse error $\epsilon^{-1}$. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if the condition number of $T_n$ is $O(\textrm{poly}(\textrm{log}\,n))$. Since no assumption on the sparseness of $T_n$ is demanded in our algorithm, the algorithm can serve as an example of quantum algorithms for solving non-sparse linear systems.

•Aug 7, 2016•1 citation

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

Christopher D. Phillips, Helia Akbari, 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 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.

IEEE journal on multiscale and multiphysics computational techniques•Jan 1, 2026•1 citation

Quantum Linear System Algorithm for General Matrices in System Identification

Kai Li, Ming Zhang, Xiaowen Liu +4 more

Solving linear systems of equations is one of the most common and basic problems in classical identification systems. Given a coefficient matrix A and a vector b, the ultimate task is to find the solution x such that Ax=b. Based on the technique of the singular value estimation, the paper proposes a modified quantum scheme to obtain the quantum state |x⟩ corresponding to the solution of the linear system of equations in O(κ2rpolylog(mn)/ϵ) time for a general m×n dimensional A, which is superior to existing quantum algorithms, where κ is the condition number, r is the rank of matrix A and ϵ is the precision parameter. Meanwhile, we also design a quantum circuit for the homogeneous linear equations and achieve an exponential improvement. The coefficient matrix A in our scheme is a sparsity-independent and non-square matrix, which can be applied in more general situations. Our research provides a universal quantum linear system solver and can enrich the research scope of quantum computation.

Entropy•Jun 28, 2022•4 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
Abstract Solving linear systems of equations is of vital importance in various fields of science. With the scale of calculation soaring, classical computers are intractable, and the advantage of quantum computing is reflected. Quantum algorithm has exponential acceleration in solving the linear systems A x ⃗ = b ⃗ for sparse and well-conditioned coefficient matrix A with dimension N × N . In this paper, we present a quantum algorithm to solve matrix equations of the form AX = B , where X = ( x ⃗ 1 , x ⃗ 2 , … , x ⃗ n ) , B = ( b ⃗ 1 , b ⃗ 2 , … , b ⃗ n ) , x ⃗ k and b ⃗ k are unit vectors. The problem can be intuitively treated as solving n linear systems simultaneously, which will needs O ( n log N ) complexity by the famous HHL algorithm. We demonstrate that in our algorithm the scale of complexity is O ( log n N ) . In the error analysis part, phase estimation is discussed in details.
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.
Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2×2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.
Solving the Toeplitz systems, which is to find the vector xxx such that Tnx=bT_nx = bTn​x=b given a n×nn\times nn×n Toeplitz matrix TnT_nTn​ and a vector bbb, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the Toeplitz systems, in which a quantum state encoding the solution with error ϵ\epsilonϵ is generated. It is shown that our algorithm's complexity is nearly linear in the condition number, and polylog in the dimensions nnn and in the inverse error ϵ−1\epsilon^{-1}ϵ−1. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if the condition number of TnT_nTn​ is O(poly(log n))O(\textrm{poly}(\textrm{log}\,n))O(poly(logn)). Since no assumption on the sparseness of TnT_nTn​ is demanded in our algorithm, the algorithm can serve as an example of quantum algorithms for solving non-sparse linear systems.
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.
Solving linear systems of equations is one of the most common and basic problems in classical identification systems. Given a coefficient matrix A and a vector b, the ultimate task is to find the solution x such that Ax=b. Based on the technique of the singular value estimation, the paper proposes a modified quantum scheme to obtain the quantum state |x⟩ corresponding to the solution of the linear system of equations in O(κ2rpolylog(mn)/ϵ) time for a general m×n dimensional A, which is superior to existing quantum algorithms, where κ is the condition number, r is the rank of matrix A and ϵ is the precision parameter. Meanwhile, we also design a quantum circuit for the homogeneous linear equations and achieve an exponential improvement. The coefficient matrix A in our scheme is a sparsity-independent and non-square matrix, which can be applied in more general situations. Our research provides a universal quantum linear system solver and can enrich the research scope of quantum computation.
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.