# Quantum-inspired sublinear classical algorithms for solving low-rank linear systems

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2018.

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

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Quantum-Inspired Machine Learning: a Survey](https://mlsanity.com/paper/2308.11269/) (2023)
- [Quantum Machine Learning for Finance](https://mlsanity.com/paper/2109.04298/) (2021)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [A unifying framework for differentially private quantum algorithms](https://mlsanity.com/paper/2307.04733/) (2023)
- [Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms](https://mlsanity.com/paper/2203.03604/) (2022)
- [Quantum Machine Learning For Classical Data](https://mlsanity.com/paper/2105.03684/) (2021)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Boosting Classification with Quantum-Inspired Augmentations](https://mlsanity.com/paper/2506.22241/) (2025)
- [Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model](https://mlsanity.com/paper/2509.13112/) (2025)
- [When AI meets quantum information: A comprehensive review](https://mlsanity.com/paper/2607.00365/) (2026)
- [A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features](https://mlsanity.com/paper/2609.10729/) (2026)

## Abstract (arXiv)

We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our algorithms are inspired by the HHL quantum algorithm for solving linear systems and the recent breakthrough by Tang of dequantizing the quantum algorithm for recommendation systems. Let A ∈ mathbbCm × n be a rank-k matrix, and b ∈ mathbbCm be a vector. We present two algorithms: a "sampling" algorithm that provides a sample from A-1b and a "query" algorithm that outputs an estimate of an entry of A-1b, where A-1 denotes the Moore-Penrose pseudo-inverse. Both of our algorithms have query and time complexity O(poly(k, kappa, |A|F, 1/ε),polylog(m, n)), where kappa is the condition number of A and ε is the precision parameter. Note that the algorithms we consider are sublinear time, so they cannot write and read the whole matrix or vectors. In this paper, we assume that A and b come with well-known low-overhead data structures such that entries of A and b can be sampled according to some natural probability distributions. Alternatively, when A is positive semidefinite, our algorithms can be adapted so that the sampling assumption on b is not required.