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:1704.06174 · Physical Review Letters

Quantum Linear System Algorithm for Dense Matrices

Leonard Wossnig, Zhikuan Zhao, Anupam Prakash

Published Jan 31, 2018• 222 citations
arXivHTMLPDF

Abstract

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$.

DOI
10.1103/physrevlett.120.050502

Related papers

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•3 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

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

Quantum Data Fitting Algorithm for Non-sparse Matrices

Guangxi Li, Youle Wang, Yu Luo +1 more

We propose a quantum data fitting algorithm for non-sparse matrices, which is based on the Quantum Singular Value Estimation (QSVE) subroutine and a novel efficient method for recovering the signs of eigenvalues. Our algorithm generalizes the quantum data fitting algorithm of Wiebe, Braun, and Lloyd for sparse and well-conditioned matrices by adding a regularization term to avoid the over-fitting problem, which is a very important problem in machine learning. As a result, the algorithm achieves a sparsity-independent runtime of $O(κ^2\sqrt{N}\mathrm{polylog}(N)/(ε\logκ))$ for an $N\times N$ dimensional Hermitian matrix $\bm{F}$, where $κ$ denotes the condition number of $\bm{F}$ and $ε$ is the precision parameter. This amounts to a polynomial speedup on the dimension of matrices when compared with the classical data fitting algorithms, and a strictly less than quadratic dependence on $κ$.

arXiv:1907.06949•Jul 16, 2019•2 citations

Efficient quantum algorithms for solving quantum linear system problems

Hefeng Wang, Hua Xiang

We transform the problem of solving linear system of equations $A\mathbf{x}=\mathbf{b}$ to a problem of finding the right singular vector with singular value zero of an augmented matrix $C$, and present two quantum algorithms for solving this problem. The first algorithm solves the problem directly by applying the quantum eigenstate filtering algorithm with query complexity of $O\left( sκ\log \left( 1/ε\right) \right) $ for a $s$-sparse matrix $C$, where $κ$ is the condition number of the matrix $A$, and $ε$ is the desired precision. The second algorithm uses the quantum resonant transition approach, the query complexity scales as $O\left[sκ+ \log\left( 1/ε\right)/\log \log \left( 1/ε\right) \right] $. Both algorithms meet the optimal query complexity in $κ$, and are simpler than previous algorithms.

arXiv:2208.06763•Aug 14, 2022•0 citations

Faster quantum linear system solver beyond the condition number

Alexander M. Dalzell, Jianqiang Li, Yuan Su

The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution $|x\rangle$ of linear system $Ax=| b \rangle$ to accuracy $ε$ with complexity independent of the condition number $κ=\lVert A^{-1}\rVert$. We focus on the standard input model where $A$ is accessed through a block encoding and $| b \rangle$ is prepared by a unitary. But we also introduce an affine dilation model that encodes $A$ and $| b \rangle$ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to $| b \rangle$ and $\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)$ queries to $A$. We prove a family of upper bounds on the effective condition number, including $κ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive even integer $t$ and $κ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive odd $t$, overcoming the $κ$-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity $3\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε$ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.

quant-pharXiv:2607.07691•Jul 9, 2026•0 citations
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 O(\ensuremathκ2npolylog(n)/\ensuremathϵ)\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}O(\ensuremathκ2n​polylog(n)/\ensuremathϵ) for an n\ifmmode×\else\texttimes\finn\ifmmode\times\else\texttimes\fi{}nn\ifmmode×\else\texttimes\fin dimensional AAA with bounded spectral norm, where \ensuremathκ\ensuremath{\kappa}\ensuremathκ denotes the condition number of AAA, and \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ 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.
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.
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.
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 a quantum data fitting algorithm for non-sparse matrices, which is based on the Quantum Singular Value Estimation (QSVE) subroutine and a novel efficient method for recovering the signs of eigenvalues. Our algorithm generalizes the quantum data fitting algorithm of Wiebe, Braun, and Lloyd for sparse and well-conditioned matrices by adding a regularization term to avoid the over-fitting problem, which is a very important problem in machine learning. As a result, the algorithm achieves a sparsity-independent runtime of O(κ2Npolylog(N)/(εlog⁡κ))O(κ^2\sqrt{N}\mathrm{polylog}(N)/(ε\logκ))O(κ2N​polylog(N)/(εlogκ)) for an N×NN\times NN×N dimensional Hermitian matrix F\bm{F}F, where κκκ denotes the condition number of F\bm{F}F and εεε is the precision parameter. This amounts to a polynomial speedup on the dimension of matrices when compared with the classical data fitting algorithms, and a strictly less than quadratic dependence on κκκ.
We transform the problem of solving linear system of equations Ax=bA\mathbf{x}=\mathbf{b}Ax=b to a problem of finding the right singular vector with singular value zero of an augmented matrix CCC, and present two quantum algorithms for solving this problem. The first algorithm solves the problem directly by applying the quantum eigenstate filtering algorithm with query complexity of $O\left( sκ\log \left( 1/ε\right) \right) $ for a sss-sparse matrix CCC, where κκκ is the condition number of the matrix AAA, and εεε is the desired precision. The second algorithm uses the quantum resonant transition approach, the query complexity scales as $O\left[sκ+ \log\left( 1/ε\right)/\log \log \left( 1/ε\right) \right] $. Both algorithms meet the optimal query complexity in κκκ, and are simpler than previous algorithms.
The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution ∣x⟩|x\rangle∣x⟩ of linear system Ax=∣b⟩Ax=| b \rangleAx=∣b⟩ to accuracy εεε with complexity independent of the condition number κ=∥A−1∥κ=\lVert A^{-1}\rVertκ=∥A−1∥. We focus on the standard input model where AAA is accessed through a block encoding and ∣b⟩| b \rangle∣b⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes AAA and ∣b⟩| b \rangle∣b⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to ∣b⟩| b \rangle∣b⟩ and O⁡(κeffpolylog⁡(κeffε))\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)O(κeff​polylog(εκeff​​)) queries to AAA. We prove a family of upper bounds on the effective condition number, including κeff≤∥(A†A)−t/2∣x⟩∥1/tε1/tκ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}κeff​≤ε1/t∥(A†A)−t/2∣x⟩∥1/t​ for positive even integer ttt and κeff≤∥A−1†(A†A)−(t−1)/2∣x⟩∥1/tε1/tκ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}κeff​≤ε1/t∥A−1†(A†A)−(t−1)/2∣x⟩∥1/t​ for positive odd ttt, overcoming the κκκ-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity 3∥A−1†∣x⟩∥ε3\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε3ε∥A−1†∣x⟩∥​ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.