Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations

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

Read Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations by Nhat A. Nghiem, Tuan K. Do, Trung V. Phan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-01342.txt.

Introduction

Nhat Nghiem, Tuan Do, and Trung Phan design a quantum algorithm for solving large systems of linear equations, a core task in data fitting, imaging, and optimization. Their method adapts the classical Kaczmarz approach, which fixes the current answer one equation at a time. Unlike many quantum solvers, it needs no oracle that serves matrix entries on demand, removing a major practical barrier.

When the system has low rank and suitable row structure, the circuit cost grows only with the logarithm of the variable count and inverse precision. It avoids the usual dependence on sparsity. For general sparse rows, the depth grows just logarithmically with sparsity, at the price of extra helper qubits. When sparsity is itself logarithmic, the authors claim an exponential depth advantage over known quantum methods. The work narrows the gap between quantum linear algebra and real problems.

Catalog record

CREATORNhat A. Nghiem, Tuan K. Do, Trung V. Phan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-01342

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations Nhat A. Nghiem, Tuan K. Do, Trung V. Phan 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 𝒪 ⁡ ( 1 ε ​ log ⁡ m ) \mathcal{O}\left(\frac{1}{\varepsilon}\log m\right) , where m m is the number of variables and ε \varepsilon is the target precision, without dependence on the sparsity s s , and could possibly be without explicit dependence on condition number κ \kappa . This shows a significant improvement over previous quantum linear solvers where the dependence on κ , s \kappa,s is at least linear. At the same time, when the rows have an arbitrary structure and have at most s s nonzero entries, we obtain the circuit depth 𝒪 ⁡ ( 1 ε ​ log ⁡ s ) \mathcal{O}\left(\frac{1}{\varepsilon}\log s\right) using extra 𝒪 ⁡ ( s ) \mathcal{O}(s) ancilla qubits, so the depth grows only logarithmically with sparsity s s . When the sparsity s s grows as 𝒪 ⁡ ( log ⁡ m ) \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. I Introduction Linear systems reside at the core of scientific computing, such as data regression/fitting 25 , inverse problems such as tomographic reconstruction 10 ; 12 , and large-scale modern optimization 29 . These tasks repeatedly boil down to solving systems of many linear algebraic equations — often overdetermined and corrupted by noise — that must be handled efficiently at scale. A powerful classical approach in this regime is the Kaczmarz method 14 , a lightweight “row-action” iteration that refines the estimate by enforcing one equation at a time, offering strong practical performance with minimal memory overhead in big data settings. As data sizes and model complexities continue to grow 22 ; 15 , these linear-algebra subroutines increasingly dominate end-to-end pipelines, making it timely to explore quantum methods that can accelerate these fundamental linear-solve workloads across many applications. Quantum algorithm for solving linear algebraic equations has stood out as one of the most promising quantum computer’s application. The first quantum algorithm for solving sparse linear system was introduced in 11 , showing an exponential improvement compared to the best-known classical algorithm in relative to the dimension. In particular, it was shown in 11 that inverting a matrix is \rm BQP -complete, highlighting that it is unlikely for classical computers to match the quantum complexity. Subsequently, quantum linear solving algorithms have been refined and improved in a series of works. Ref. 3 introduced a quantum linear solvers with exponentially improved dependence on error tolerance. Ref. 4 introduced a namely preconditioned quantum linear solvers, which can handle ill-conditioned linear systems more efficiently than 11 ; 3 . Ref. 13 outlined a variational quantum linear solvers, which was shown heuristically to perform well in practice. Ref. 28 constructed a quantum linear solvers suitable for dense system. Ref. 24 shares a certain similarity to ours, as both methods rely on row iterations. As we will show more explicitly later, our method gains certain advantage compared to 24 . In this work, we develop a quantum version of the classical Kaczmarz algorithm. While quantum adaptations of Kaczmarz and related quantum linear solvers have been studied 11 ; 3 ; 28 ; 4 ; 13 ; 24 , we advance beyond previous approaches on two fronts: we obtain faster scaling in relevant regimes and, crucially, we adopt a substantially lighter input-access model by avoiding QRAM/oracle queries of individual matrix entries — thus the performance of our algorithm does not hinge on a data-access assumption that is likely to be the hardest part to realize in practice. Our paper is organized as follows. In Section II , we review the classical Kaczmarz method, including its randomized iteration and convergence behavior. Section III presents the quantum Kaczmarz algorithm: we state the input-access assumptions and state-preparation routines (Section III.1 ), construct the quantum row-action update via block-encodings then prove the main complexity bounds (Section III.2 ), and followed by a discussion and comparison with prior quantum linear solvers (Section III.3 ). The Appendices collect the required background on block-encoding/QSVT tools (Appendix A ) and provide the detailed complexity analysis underlying the main theorem (Appendix C ). II Classical Kaczmarz Method Consider a linear system Ax=b\ , (II.1) where A is a n\times m real-valued matrix, b is a known n real-valued vector, and x is the unknown m real-valued vector the unknown vector to be estimated. For notational convenience, we write b=\begin{pmatrix}b_{1}\\ b_{2}\\ ...\\ b_{n}\end{pmatrix}\in\mathbb{R}^{n}\ ,\ x=\begin{pmatrix}x_{1}\\ x_{2}\\ ...\\ x_{m}\end{pmatrix}\in\mathbb{R}^{m}\ ,\ and represent the matrix A row-wise as A=\begin{pmatrix}a_{1}^{\top}\\ a_{2}^{\top}\\ ...\\ a_{n}^{\top}\end{pmatrix}\in\mathbb{R}^{n\times m}\ ,\ a_{j}=\begin{pmatrix}a_{j1}\\ a_{j2}\\ ...\\ a_{jm}\end{pmatrix}\in\mathbb{R}^{m}\ , where ⊤ is the transpose operation, so that the system Eq. ( II.1 ) is equivalent to the collection of n scalar linear equations a_{j}^{\top}x=a_{j1}x_{1}+a_{j2}x_{2}+...+a_{jm}x_{m}=b_{j}\ . In many applications, the matrix A is not required to be a square. Of particular interest are rectangular systems, in which the number of equations is at least the number of unknowns, i.e. n\geq m . In this case, Eq. ( II.1 ) may have no exact solution due to measurement noise or modeling error, and one often seeks an approximate solution . A classical approach for solving this problem at large scale is the algebraic reconstruction technique known as the Kaczmarz method 14 , an iterative row-action scheme that updates the current estimate by enforcing one equation at a time 2 . The procedure is as follows: Algorithm 1 (Classical Kaczmarz method for solving linear system) . Let Ax=b be the linear system of interest where A\in\mathbb{R}^{n\times m},b\in\mathbb{R}^{n} . • Step 0: We start with an initial guess x^{(0)} , often chosen as the zero-vector (0,0,...,0)^{\top} . • Step k\geq 1 : Pick an index j_{k}\in\{1,2,\ldots,n\} , often cyclically or at random 26 , and update the guess iteratively via: x^{(k+1)}=x^{(k)}+\lambda\left(\frac{b_{j_{k}}-a_{j_{k}}^{\top}x^{(k)}}{||a_{j_{k}}||_{2}}\right)a_{j_{k}}\ , (II.2) where ||a_{j_{k}}||_{2}=a_{j_{k}}^{\top}a_{j_{k}} is the row l_{2} -norm and \lambda is the relaxation parameter, which is often chosen between 0 and 2 . For \lambda=1 , this update can be interpreted as an exact projection 1 1 1 When \lambda=1 , the update is the orthogonal projection of x^{(k-1)} onto the hyperplane a_{j_{k}}^{\top}x=b_{j_{k}} , as it produces an iterate x^{(k)} satisfies a_{j_{k}}^{\top}x^{(k)}=b_{j_{k}} exactly. . In other words, the Kaczmarz method views each row-equation a_{j}^{\top}x=b_{j} as a hyperplane in \mathbb{R}^{m} , then generates a sequence \{x^{(k)}\} by repeatedly projecting onto these hyperplanes by applying Eq. ( II.2 ). The iteration is terminated after a prescribed number of steps, or once a chosen convergence criterion is met. It

Read the complete text