  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\epsilon\|A^{+}b\|$, where $\|\cdot\|$ is the spectral norm
and $A^+$ is the Moore-Penrose inverse of $A$. Our algorithm has time
complexity $\widetilde{O}(\kappa_F^4/\kappa\epsilon^2)$ in the general case,
where $\kappa_{F} =\|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 $\widetilde{O}(s
\kappa\log(1/\epsilon))$, matching the quantum lower bound for solving linear
systems in $\kappa$ and $1/\epsilon$ 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{\kappa}\log(1/\epsilon))$.
  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.
