# Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension

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

## Key facts

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

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

- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Revisiting dequantization and quantum advantage in learning tasks](https://mlsanity.com/paper/2112.00811/) (2021)
- [Quantum-Inspired Machine Learning: a Survey](https://mlsanity.com/paper/2308.11269/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Quantum Transformer: Accelerating model inference via quantum linear algebra](https://mlsanity.com/paper/2402.16714/) (2024)
- [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)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms](https://mlsanity.com/paper/2304.04932/) (2023)
- [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)
- [Quantum Speedup of Natural Gradient for Variational Bayes](https://mlsanity.com/paper/2106.05807/) (2021)
- [An Introduction to Quantum Computing for Statisticians and Data Scientists](https://mlsanity.com/paper/2112.06587/) (2021)
- [Quantum Semi-Supervised Kernel Learning](https://mlsanity.com/paper/2204.10700/) (2022)

## Abstract (arXiv)

We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for low-rank matrices. Inspired by recent work of Tang, assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix and sample from the solution to the problem Ax=b using fast sampling techniques. We implement the pseudo-inverse by finding an approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, the approach can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem, our result suggests that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms.