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

arXiv: https://arxiv.org/abs/2307.06627 · HTML: https://mlsanity.com/paper/2307.06627/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2023.

## Built on by (most cited first, 1 of 1)

- [Randomized Kaczmarz with geometrically smoothed momentum](https://mlsanity.com/paper/2401.09415/) (2024)

## Abstract (arXiv)

We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix A∈ℝm× n and a vector b∈ℝm, we propose classical algorithms that produce a data structure for the solution x∈ℝn of the linear system Ax=b with the ability to sample and query its entries. The resulting x satisfies |x-A+b|≤ε|A+b|, where |·| is the spectral norm and A^+ is the Moore-Penrose inverse of A. Our algorithm has time complexity widetildeO(kappaF4/kappaε2) in the general case, where kappaF =|A|F|A^+| and kappa=|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 widetildeO(s kappalog(1/ε)), matching the quantum lower bound for solving linear systems in kappa and 1/ε up to poly-logarithmic factors [Harrow and Kothari]. When A is s-sparse and symmetric positive-definite, our algorithm has complexity widetildeO(s√kappalog(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.