arXiv:2307.06627

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

Qian Zuo, Tongyang Li

Published Jul 13, 2023• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2307.06627

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.10309ACM Transactions on Quantum ComputingMar 25, 202219 citations

A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems

Tyler Chen, Junhyung Lyle Kim, Archan Ray +3 more

arXiv:2508.13108Aug 18, 20250 citations

Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations

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

quant-pharXiv:2601.01342Jan 6, 20260 citations

An Optimal Quantum Linear Systems Algorithm

Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

quant-pharXiv:2609.35660Sep 29, 20260 citations

Quantum-inspired algorithms in practice

Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan +1 more

arXiv:1905.10415QuantumAug 13, 2020134 citations

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight

Shouvanik Chakrabarti, Dylan Herman, Junhyung Lyle Kim +1 more

quant-pharXiv:2610.42069Nov 2, 2026

arXiv:2307.06627

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

Qian Zuo, Tongyang Li

Published Jul 13, 2023• 0 citations

arXiv HTML PDF

Abstract

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

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

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.

DOI: 10.48550/arxiv.2307.06627

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.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.10309ACM Transactions on Quantum ComputingMar 25, 202219 citations

A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems

Tyler Chen, Junhyung Lyle Kim, Archan Ray +3 more

We describe and analyze a simple algorithm for sampling from the solution $\mathbf{x}^* := \mathbf{A}^+\mathbf{b}$ to a linear system $\mathbf{A}\mathbf{x} = \mathbf{b}$ . We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of $\mathbf{A}$ . Our algorithm produces a compressed representation of some vector $\mathbf{x}$ for which $\|\mathbf{x}^* - \mathbf{x}\| < \varepsilon \|\mathbf{x}^* \|$ in $\widetilde{O}(κ_{\mathsf{F}}^4 κ^2 / \varepsilon^2)$ time, where $κ_{\mathsf{F}} := \|\mathbf{A}\|_{\mathsf{F}}\|\mathbf{A}^{+}\|$ and $κ:= \|\mathbf{A}\|\|\mathbf{A}^{+}\|$ . The representation of $\mathbf{x}$ allows us to query entries of $\mathbf{x}$ in $\widetilde{O}(κ_{\mathsf{F}}^2)$ time and sample proportional to the square entries of $\mathbf{x}$ in $\widetilde{O}(κ_{\mathsf{F}}^4 κ^6)$ time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of $\mathbf{A}$ . Our analysis, which is elementary, non-asymptotic, and fully self-contained, simplifies and clarifies several past analyses from literature including [Gilyén, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].We describe and analyze a simple algorithm for sampling from the solution $\mathbf{x}^* := \mathbf{A}^+\mathbf{b}$ to a linear system $\mathbf{A}\mathbf{x} = \mathbf{b}$. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of $\mathbf{A}$. Our algorithm produces a compressed representation of some vector $\mathbf{x}$ for which $\|\mathbf{x}^* - \mathbf{x}\| < \varepsilon \|\mathbf{x}^* \|$ in $\widetilde{O}(κ_{\mathsf{F}}^4 κ^2 / \varepsilon^2)$ time, where $κ_{\mathsf{F}} := \|\mathbf{A}\|_{\mathsf{F}}\|\mathbf{A}^{+}\|$ and $κ:= \|\mathbf{A}\|\|\mathbf{A}^{+}\|$. The representation of $\mathbf{x}$ allows us to query entries of $\mathbf{x}$ in $\widetilde{O}(κ_{\mathsf{F}}^2)$ time and sample proportional to the square entries of $\mathbf{x}$ in $\widetilde{O}(κ_{\mathsf{F}}^4 κ^6)$ time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of $\mathbf{A}$. Our analysis, which is elementary, non-asymptotic, and fully self-contained, simplifies and clarifies several past analyses from literature including [Gilyén, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].

arXiv:2508.13108Aug 18, 20250 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.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.01342Jan 6, 20260 citations

An Optimal Quantum Linear Systems Algorithm

Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

In the quantum linear systems problem (QLSP), we are given query access to a $d$ -sparse $N\times N$ matrix $A$ with condition number $κ$ , and the ability to prepare a quantum state proportional to a vector $\vec b$ . The goal is to output an $ε$ -approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$ . Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$ , while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$ . We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$ . We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.

quant-pharXiv:2609.35660Sep 29, 20260 citations

Quantum-inspired algorithms in practice

Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan +1 more

We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.

arXiv:1905.10415QuantumAug 13, 2020134 citations

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight

Shouvanik Chakrabarti, Dylan Herman, Junhyung Lyle Kim +1 more

Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$ , return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\|A\|_F/\|A\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use $\widetilde O(ρ)$ queries, whereas the best dequantized algorithms use $\widetilde O(ρ^4)$ . We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $κ_0>1$ , we construct dense linear systems with condition number at most $κ_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $Ω(ρ^4/\logρ)$ classical queries but only $Θ(ρ)$ quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\|A\|_F/\|A\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use $\widetilde O(ρ)$ queries, whereas the best dequantized algorithms use $\widetilde O(ρ^4)$. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $κ_0>1$, we construct dense linear systems with condition number at most $κ_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $Ω(ρ^4/\logρ)$ classical queries but only $Θ(ρ)$ quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.

quant-pharXiv:2610.42069Nov 2, 2026

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

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

s

-sparse and symmetric positive-definite, our algorithm has complexity

\widetilde{O}(s\sqrtκ\log(1/ε))

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.

We describe and analyze a simple algorithm for sampling from the solution

\mathbf{x}^* := \mathbf{A}^+\mathbf{b}

to a linear system

\mathbf{A}\mathbf{x} = \mathbf{b}

. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of

\mathbf{A}

. Our algorithm produces a compressed representation of some vector

\mathbf{x}

for which

\|\mathbf{x}^* - \mathbf{x}\| < \varepsilon \|\mathbf{x}^* \|

\widetilde{O}(κ_{\mathsf{F}}^4 κ^2 / \varepsilon^2)

time, where

κ_{\mathsf{F}} := \|\mathbf{A}\|_{\mathsf{F}}\|\mathbf{A}^{+}\|

and

κ:= \|\mathbf{A}\|\|\mathbf{A}^{+}\|

. The representation of

\mathbf{x}

allows us to query entries of

\mathbf{x}

\widetilde{O}(κ_{\mathsf{F}}^2)

time and sample proportional to the square entries of

\mathbf{x}

\widetilde{O}(κ_{\mathsf{F}}^4 κ^6)

time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of

\mathbf{A}

. Our analysis, which is elementary, non-asymptotic, and fully self-contained, simplifies and clarifies several past analyses from literature including [Gilyén, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].

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

In the quantum linear systems problem (QLSP), we are given query access to a

d

-sparse

N\times N

matrix

A

with condition number

κ

, and the ability to prepare a quantum state proportional to a vector

\vec b

. The goal is to output an

ε

-approximation to the quantum state proportional to the solution

\vec x

A\vec{x}=\vec{b}

. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities

O(κd\log(1/ε))

and

κ\sqrt d(κd/ε)^{o(1)}

, while the best known lower bounds were

Ω(κ\log(1/ε))

and

Ω(κ\sqrt d)

. We improve these bounds and show that the complexity of the QLSP is

Θ(κ\sqrt d\log(1/ε))

. We also resolve an open problem of Berry and Childs by showing that any

N\times N

unitary can be implemented with bounded error using

O(\sqrt N)

queries to its matrix entries.

Quantum algorithms for linear algebra that access a matrix

A

through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to

A

, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm

ρ=\|A\|_F/\|A\|

and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use

\widetilde O(ρ)

queries, whereas the best dequantized algorithms use

\widetilde O(ρ^4)

. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant

κ_0>1

, we construct dense linear systems with condition number at most

κ_0

for which sampling from the solution within a sufficiently small constant total variation distance requires

Ω(ρ^4/\logρ)

classical queries but only

Θ(ρ)

quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.