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:1905.11686 · Physical Review A

Row and column iteration methods to solve linear systems on a quantum computer

Changpeng Shao, Hua Xiang

Published Feb 19, 2020• 17 citations
arXivHTMLPDF

Abstract

We consider the quantum implementations of two classical iterative solvers for a system of linear equations, including the row (Kaczmarz) method which utilizes a row of the coefficient matrix in each iteration step, and the column (coordinate descent) method which uses a column instead. These two methods are widely applied in big data science due to their simple iteration schemes. We propose fast quantum algorithms for these two approaches by constructing efficient unitary operators in each iteration step based on the block-encoding technique. The construction is based on the unitaries to prepare the quantum states of rows or columns of the coefficient matrix. If the quantum states are efficiently prepared, for example, by qRAM, then the quantum iterative methods achieve an exponential speedup in the problem size $n$ over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is $O({\ensuremath{\kappa}}_{s}^{2}(logn)\left(log\frac{1}{\ensuremath{\epsilon}}\right))$, where ${\ensuremath{\kappa}}_{s}$ is the scaled condition number, and $\ensuremath{\epsilon}$ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.

DOI
10.1103/physreva.101.022322

Related papers

Quantum multirow iteration algorithm for linear systems with nonsquare coefficient matrices

W. A. Lin, Guojing Tian, Xiaoming Sun

In the field of quantum linear system algorithms, quantum computing has realized exponential computational advantages over classical computing. However, the focus has been on square coefficient matrices, with few quantum algorithms addressing nonsquare matrices. Towards this kind of problems defined by $Ax=b$ where $A\ensuremath{\in}{\mathbb{R}}^{m\ifmmode\times\else\texttimes\fi{}n}$, we propose a quantum algorithm inspired by the classical multirow iteration method and provide an explicit quantum circuit based on the quantum comparator and quantum random access memory. The time complexity of our quantum multirow iteration algorithm is $O(K{log}_{2}m)$, with $K$ representing the number of iteration steps, which demonstrates an exponential speedup compared to the classical version.. Based on the convergence of the classical multirow iteration algorithm, we prove that our quantum algorithm converges faster than the quantum one-row iteration algorithm presented by Shao and Xiang [C. Shao and H. Xiang, Phys. Rev. A 101, 022322 (2020)]. Moreover, our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems and quadratic optimization problems.

arXiv:2409.04010•Physical Review A•Aug 27, 2024•0 citations

Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations

Nhat A. Nghiem, Tuan K. Do, Trung V. Phan

We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity $\mathcal{O}\left(\frac{1}{\varepsilon}\log m\right)$, where $m$ is the number of variables and $\varepsilon$ is the target precision, without dependence on the sparsity $s$, and could possibly be without explicit dependence on condition number $κ$. This shows a significant improvement over previous quantum linear solvers where the dependence on $κ,s$ is at least linear. At the same time, when the rows have an arbitrary structure and have at most $s$ nonzero entries, we obtain the circuit depth $\mathcal{O}\left(\frac{1}{\varepsilon}\log s\right)$ using extra $\mathcal{O}(s)$ ancilla qubits, so the depth grows only logarithmically with sparsity $s$. When the sparsity $s$ grows as $\mathcal{O}(\log m)$, then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.

quant-pharXiv:2601.01342•Jan 6, 2026•0 citations

Faster Quantum-inspired Algorithms for Solving Linear Systems

Changpeng Shao, Ashley Montanaro

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system \( A{\bf x}= {\bf b} \) , we show that there is a classical algorithm that outputs a data structure for \( {\bf x} \) allowing sampling and querying to the entries, where \( {\bf x} \) is such that \( \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert \) . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is \( \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) \) , where \( \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert \) and \( \kappa = \Vert A\Vert \Vert A^{+}\Vert \) . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity \( \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) \) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution \( {\bf x} \) in time \( \widetilde{O}(\kappa _F^2) \) , while the best quantum algorithm known returns \( | {\bf x} \rangle \) in time \( \widetilde{O}(\kappa _F) \) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.

arXiv:2103.10309•ACM Transactions on Quantum Computing•Mar 25, 2022•19 citations

Refined Quantum Algorithms for Principal Component Analysis and Solving Linear System

Nhat A. Nghiem

We outline refined versions of two major quantum algorithms for performing principal component analysis and solving linear equations. Our methods are exponentially faster than their classical counterparts and even previous quantum algorithms/dequantization algorithms. Oracle/black-box access to classical data is not required, thus implying great capacity for near-term realization. Several applications and implications of these results are discussed. First, we show that a Hamiltonian $H$ with classically known rows/columns can be efficiently simulated, adding another model in addition to the well-known sparse access and linear combination of unitaries models. Second, we provide a simpler proof of the known result that quantum matrix inversion cannot achieve sublinear complexity $κ^{1-γ}$ where $κ$ is the conditional number of the inverted matrix.

arXiv:2504.00833•Apr 1, 2025•0 citations

On Quantum Solvers for Linear Algebraic Systems

Papagiannis Nikos, Vavalis Manolis

Abstract Solving large-scale linear systems is an integral part of many scientific disciplines. Classical linear solvers have a polynomial time complexity and it seems impossible to further improve their performance. This fact has directed scientific research to the study of corresponding quantum algorithms, which promise even exponential acceleration compared to existing methods. In this paper, we present and analyze some of the most important related results. In particular, we present the HHL and WZP algorithms based on the eigen-decomposition of a matrix, the row and column iteration methods, as well as two hybrid algorithms that require the cooperation of a classical and a quantum computer, namely an algorithm that uses random walks and the VQLS algorithm. The latter is also examined from an experimental standpoint using the Qiskit open-source framework and a suitable quantum circuit is proposed which can enhance its performance.

Quantum Information and Computation•Dec 1, 2025•0 citations

Block-encoding-based quantum algorithm for linear systems with displacement structures

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

Matrices with the displacement structures of circulant, Toeplitz, and Hankel types as well as matrices with structures generalizing these types are omnipresent in computations of sciences and engineering. In this paper we present efficient and memory-reduced quantum algorithms for solving linear systems with such structures by devising an approach to implement the block-encodings of these structured matrices. More specifically, by decomposing $n\ifmmode\times\else\texttimes\fi{}n$ dense matrices into linear combinations of displacement matrices, we first deduce the parametrized representations of the matrices with displacement structures so that they can be treated similarly. With such representations, we then construct $\ensuremath{\epsilon}$-approximate block-encodings of these structured matrices in two different data access models, i.e., the black-box model and the quantum random access memory (QRAM) data structure model. It is shown the quantum linear system solvers based on the proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model. In particular, these linear system solvers subsume known results with significant improvements and also can motivate new instances where there was no specialized quantum algorithm before. As an application, one of the quantum linear system solvers is applied to the linear prediction of time series, which justifies the claimed quantum speedup is achievable for problems of practical interest.

arXiv:1912.12212•Physical Review A•Dec 8, 2021•39 citations
We consider the quantum implementations of two classical iterative solvers for a system of linear equations, including the row (Kaczmarz) method which utilizes a row of the coefficient matrix in each iteration step, and the column (coordinate descent) method which uses a column instead. These two methods are widely applied in big data science due to their simple iteration schemes. We propose fast quantum algorithms for these two approaches by constructing efficient unitary operators in each iteration step based on the block-encoding technique. The construction is based on the unitaries to prepare the quantum states of rows or columns of the coefficient matrix. If the quantum states are efficiently prepared, for example, by qRAM, then the quantum iterative methods achieve an exponential speedup in the problem size nnn over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is O(\ensuremathκs2(logn)(log1\ensuremathϵ))O({\ensuremath{\kappa}}_{s}^{2}(logn)\left(log\frac{1}{\ensuremath{\epsilon}}\right))O(\ensuremathκs2​(logn)(log\ensuremathϵ1​)), where \ensuremathκs{\ensuremath{\kappa}}_{s}\ensuremathκs​ is the scaled condition number, and \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.
In the field of quantum linear system algorithms, quantum computing has realized exponential computational advantages over classical computing. However, the focus has been on square coefficient matrices, with few quantum algorithms addressing nonsquare matrices. Towards this kind of problems defined by Ax=bAx=bAx=b where $A\ensuremath{\in}{\mathbb{R}}^{m\ifmmode\times\else\texttimes\fi{}n}$, we propose a quantum algorithm inspired by the classical multirow iteration method and provide an explicit quantum circuit based on the quantum comparator and quantum random access memory. The time complexity of our quantum multirow iteration algorithm is O(Klog2m)O(K{log}_{2}m)O(Klog2​m), with KKK representing the number of iteration steps, which demonstrates an exponential speedup compared to the classical version.. Based on the convergence of the classical multirow iteration algorithm, we prove that our quantum algorithm converges faster than the quantum one-row iteration algorithm presented by Shao and Xiang [C. Shao and H. Xiang, Phys. Rev. A 101, 022322 (2020)]. Moreover, our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems and quadratic optimization problems.
We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity O(1εlog⁡m)\mathcal{O}\left(\frac{1}{\varepsilon}\log m\right)O(ε1​logm), where mmm is the number of variables and ε\varepsilonε is the target precision, without dependence on the sparsity sss, and could possibly be without explicit dependence on condition number κκκ. This shows a significant improvement over previous quantum linear solvers where the dependence on κ,sκ,sκ,s is at least linear. At the same time, when the rows have an arbitrary structure and have at most sss nonzero entries, we obtain the circuit depth O(1εlog⁡s)\mathcal{O}\left(\frac{1}{\varepsilon}\log s\right)O(ε1​logs) using extra O(s)\mathcal{O}(s)O(s) ancilla qubits, so the depth grows only logarithmically with sparsity sss. When the sparsity sss grows as O(log⁡m)\mathcal{O}(\log m)O(logm), then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system Ax=b A{\bf x}= {\bf b} Ax=b , we show that there is a classical algorithm that outputs a data structure for x {\bf x} x allowing sampling and querying to the entries, where x {\bf x} x is such that ∥x−A+b∥≤ϵ∥A+b∥ \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert ∥x−A+b∥≤ϵ∥A+b∥ . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is O~(κF6κ2/ϵ2) \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) O(κF6​κ2/ϵ2) , where κF=∥A∥F∥A+∥ \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert κF​=∥A∥F​∥A+∥ and κ=∥A∥∥A+∥ \kappa = \Vert A\Vert \Vert A^{+}\Vert κ=∥A∥∥A+∥ . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity O~(κF6κ6/ϵ4) \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) O(κF6​κ6/ϵ4) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution x {\bf x} x in time O~(κF2) \widetilde{O}(\kappa _F^2) O(κF2​) , while the best quantum algorithm known returns ∣x⟩ | {\bf x} \rangle ∣x⟩ in time O~(κF) \widetilde{O}(\kappa _F) O(κF​) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.
We outline refined versions of two major quantum algorithms for performing principal component analysis and solving linear equations. Our methods are exponentially faster than their classical counterparts and even previous quantum algorithms/dequantization algorithms. Oracle/black-box access to classical data is not required, thus implying great capacity for near-term realization. Several applications and implications of these results are discussed. First, we show that a Hamiltonian HHH with classically known rows/columns can be efficiently simulated, adding another model in addition to the well-known sparse access and linear combination of unitaries models. Second, we provide a simpler proof of the known result that quantum matrix inversion cannot achieve sublinear complexity κ1−γκ^{1-γ}κ1−γ where κκκ is the conditional number of the inverted matrix.
Abstract Solving large-scale linear systems is an integral part of many scientific disciplines. Classical linear solvers have a polynomial time complexity and it seems impossible to further improve their performance. This fact has directed scientific research to the study of corresponding quantum algorithms, which promise even exponential acceleration compared to existing methods. In this paper, we present and analyze some of the most important related results. In particular, we present the HHL and WZP algorithms based on the eigen-decomposition of a matrix, the row and column iteration methods, as well as two hybrid algorithms that require the cooperation of a classical and a quantum computer, namely an algorithm that uses random walks and the VQLS algorithm. The latter is also examined from an experimental standpoint using the Qiskit open-source framework and a suitable quantum circuit is proposed which can enhance its performance.
Matrices with the displacement structures of circulant, Toeplitz, and Hankel types as well as matrices with structures generalizing these types are omnipresent in computations of sciences and engineering. In this paper we present efficient and memory-reduced quantum algorithms for solving linear systems with such structures by devising an approach to implement the block-encodings of these structured matrices. More specifically, by decomposing $n\ifmmode\times\else\texttimes\fi{}n$ dense matrices into linear combinations of displacement matrices, we first deduce the parametrized representations of the matrices with displacement structures so that they can be treated similarly. With such representations, we then construct $\ensuremath{\epsilon}$-approximate block-encodings of these structured matrices in two different data access models, i.e., the black-box model and the quantum random access memory (QRAM) data structure model. It is shown the quantum linear system solvers based on the proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model. In particular, these linear system solvers subsume known results with significant improvements and also can motivate new instances where there was no specialized quantum algorithm before. As an application, one of the quantum linear system solvers is applied to the linear prediction of time series, which justifies the claimed quantum speedup is achievable for problems of practical interest.