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

Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations

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

quant-phSubmitted Jan 4, 2026• Announced Jan 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

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

Quantum Linear System Algorithm for Dense Matrices

Leonard Wossnig, Zhikuan Zhao, Anupam Prakash

Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix $A$ and a vector $\mathbf{b}$ the task is to find the vector $\mathbf{x}$ such that $A\mathbf{x}=\mathbf{b}$. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional $A$ with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of $A$, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of $A$ is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of $A$ and the vector of Euclidean norms of the rows of $A$.

arXiv:1704.06174•Physical Review Letters•Jan 31, 2018•222 citations

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

Changpeng Shao, Hua Xiang

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.

arXiv:1905.11686•Physical Review A•Feb 19, 2020•17 citations

An Efficient Quantum Algorithm for Linear System Problem in Tensor Format

Zeguan Wu, Sidhant Misra, Tamás Terlaky B +2 more

Solving linear systems is at the foundation of many algorithms. Recently, quantum linear system algorithms (QLSAs) have attracted great attention since they converge to a solution exponentially faster than classical algorithms in terms of the problem dimension. However, low-complexity circuit implementations of the oracles assumed in these QLSAs constitute the major bottleneck for practical quantum speed-up in solving linear systems. In this work, we focus on the application of QLSAs for linear systems that are expressed as a low rank tensor sums, which arise in solving discretized PDEs. Previous works uses modified Krylov subspace methods to solve such linear systems with a per-iteration complexity being polylogarithmic of the dimension but with no guarantees on the total convergence cost. We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA and perform a detailed analysis of the circuit depth of its implementation. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension, which is comparable to the per-iteration complexity of the classical heuristic methods.

arXiv:2403.19829•Mar 28, 2024•0 citations

A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems

Jianqiang Li

Given a matrix $A$ of dimension $M \times N$ and a vector $\vec{b}$, the quantum linear system (QLS) problem asks for the preparation of a quantum state $|\vec{y}\rangle$ proportional to the solution of $A\vec{y} = \vec{b}$. Existing QLS algorithms have runtimes that scale linearly with the condition number $κ(A)$, the sparsity of $A$, and logarithmically with inverse precision, but often overlook structural properties of $\vec{b}$, whose alignment with $A$'s eigenspaces can greatly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector $\vec{b}$. The runtime of our algorithm depends polynomially on the sparsity of the augmented matrix $H = [A, -\vec{b}]$, the inverse precision, the $\ell_2$ norm of the solution $\vec{y} = A^+ \vec{b}$, and a new instance-dependent parameter \[ ET= \sum_{i=1}^M p_i^2 \cdot d_i, \] where $\vec{p} = (AA^{\top})^+ \vec{b}$, and $d_i$ denotes the squared $\ell_2$ norm of the $i$-th row of $H$. We also introduce a structure-aware rescaling technique tailored to the solution $\vec{y} = A^+ \vec{b}$. Unlike left preconditioning methods, which transform the linear system to $DA\vec{y} = D\vec{b}$, our approach applies a right rescaling matrix, reformulating the linear system as $AD\vec{z} = \vec{b}$. As an application of our instance-aware QLS algorithm and new rescaling scheme, we develop a quantum algorithm for solving multivariate polynomial systems in regimes where prior QLS-based methods fail. This yields an end-to-end framework applicable to a broad class of problems. In particular, we apply it to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system, and show through detailed analysis that, under certain conditions, our quantum algorithm for MIS runs in polynomial time.

arXiv:2510.05588•Oct 7, 2025•0 citations

Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems

Qian Zuo, Tongyang Li

We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in\mathbb{R}^m$, we propose classical algorithms that produce a data structure for the solution $x\in\mathbb{R}^{n}$ of the linear system $Ax=b$ with the ability to sample and query its entries. The resulting $x$ satisfies $\|x-A^{+}b\|\leqε\|A^{+}b\|$, where $\|\cdot\|$ is the spectral norm and $A^+$ is the Moore-Penrose inverse of $A$. Our algorithm has time complexity $\widetilde{O}(κ_F^4/κε^2)$ in the general case, where $κ_{F} =\|A\|_F\|A^+\|$ and $κ=\|A\|\|A^+\|$ are condition numbers. Compared to the prior state-of-the-art result [Shao and Montanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When $A$ is $s$-sparse, our algorithm has complexity $\widetilde{O}(s κ\log(1/ε))$, matching the quantum lower bound for solving linear systems in $κ$ and $1/ε$ up to poly-logarithmic factors [Harrow and Kothari]. When $A$ is $s$-sparse and symmetric positive-definite, our algorithm has complexity $\widetilde{O}(s\sqrtκ\log(1/ε))$. Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices. Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims.

arXiv:2307.06627•Jul 13, 2023•0 citations
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.
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix AAA and a vector b\mathbf{b}b the task is to find the vector x\mathbf{x}x such that Ax=bA\mathbf{x}=\mathbf{b}Ax=b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional AAA with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of AAA, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of AAA is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of AAA and the vector of Euclidean norms of the rows of AAA.
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{\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.
Solving linear systems is at the foundation of many algorithms. Recently, quantum linear system algorithms (QLSAs) have attracted great attention since they converge to a solution exponentially faster than classical algorithms in terms of the problem dimension. However, low-complexity circuit implementations of the oracles assumed in these QLSAs constitute the major bottleneck for practical quantum speed-up in solving linear systems. In this work, we focus on the application of QLSAs for linear systems that are expressed as a low rank tensor sums, which arise in solving discretized PDEs. Previous works uses modified Krylov subspace methods to solve such linear systems with a per-iteration complexity being polylogarithmic of the dimension but with no guarantees on the total convergence cost. We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA and perform a detailed analysis of the circuit depth of its implementation. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension, which is comparable to the per-iteration complexity of the classical heuristic methods.
Given a matrix AAA of dimension M×NM \times NM×N and a vector b⃗\vec{b}b, the quantum linear system (QLS) problem asks for the preparation of a quantum state ∣y⃗⟩|\vec{y}\rangle∣y​⟩ proportional to the solution of Ay⃗=b⃗A\vec{y} = \vec{b}Ay​=b. Existing QLS algorithms have runtimes that scale linearly with the condition number κ(A)κ(A)κ(A), the sparsity of AAA, and logarithmically with inverse precision, but often overlook structural properties of b⃗\vec{b}b, whose alignment with AAA's eigenspaces can greatly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector b⃗\vec{b}b. The runtime of our algorithm depends polynomially on the sparsity of the augmented matrix H=[A,−b⃗]H = [A, -\vec{b}]H=[A,−b], the inverse precision, the ℓ2\ell_2ℓ2​ norm of the solution y⃗=A+b⃗\vec{y} = A^+ \vec{b}y​=A+b, and a new instance-dependent parameter ET=∑i=1Mpi2⋅di, ET= \sum_{i=1}^M p_i^2 \cdot d_i, ET=∑i=1M​pi2​⋅di​, where p⃗=(AA⊤)+b⃗\vec{p} = (AA^{\top})^+ \vec{b}p​=(AA⊤)+b, and did_idi​ denotes the squared ℓ2\ell_2ℓ2​ norm of the iii-th row of HHH. We also introduce a structure-aware rescaling technique tailored to the solution y⃗=A+b⃗\vec{y} = A^+ \vec{b}y​=A+b. Unlike left preconditioning methods, which transform the linear system to DAy⃗=Db⃗DA\vec{y} = D\vec{b}DAy​=Db, our approach applies a right rescaling matrix, reformulating the linear system as ADz⃗=b⃗AD\vec{z} = \vec{b}ADz=b. As an application of our instance-aware QLS algorithm and new rescaling scheme, we develop a quantum algorithm for solving multivariate polynomial systems in regimes where prior QLS-based methods fail. This yields an end-to-end framework applicable to a broad class of problems. In particular, we apply it to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system, and show through detailed analysis that, under certain conditions, our quantum algorithm for MIS runs in polynomial time.
We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix A∈Rm×nA\in\mathbb{R}^{m\times n}A∈Rm×n and a vector b∈Rmb\in\mathbb{R}^mb∈Rm, we propose classical algorithms that produce a data structure for the solution x∈Rnx\in\mathbb{R}^{n}x∈Rn of the linear system Ax=bAx=bAx=b with the ability to sample and query its entries. The resulting xxx satisfies ∥x−A+b∥≤ε∥A+b∥\|x-A^{+}b\|\leqε\|A^{+}b\|∥x−A+b∥≤ε∥A+b∥, where ∥⋅∥\|\cdot\|∥⋅∥ is the spectral norm and A+A^+A+ is the Moore-Penrose inverse of AAA. Our algorithm has time complexity O~(κF4/κε2)\widetilde{O}(κ_F^4/κε^2)O(κF4​/κε2) in the general case, where κF=∥A∥F∥A+∥κ_{F} =\|A\|_F\|A^+\|κF​=∥A∥F​∥A+∥ and κ=∥A∥∥A+∥κ=\|A\|\|A^+\|κ=∥A∥∥A+∥ are condition numbers. Compared to the prior state-of-the-art result [Shao and Montanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When AAA is sss-sparse, our algorithm has complexity O~(sκlog⁡(1/ε))\widetilde{O}(s κ\log(1/ε))O(sκlog(1/ε)), matching the quantum lower bound for solving linear systems in κκκ and 1/ε1/ε1/ε up to poly-logarithmic factors [Harrow and Kothari]. When AAA is sss-sparse and symmetric positive-definite, our algorithm has complexity O~(sκlog⁡(1/ε))\widetilde{O}(s\sqrtκ\log(1/ε))O(sκ​log(1/ε)). Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices. Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims.