# Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2019.

## Built on by (most cited first, 30 of 37)

- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance](https://mlsanity.com/paper/2401.11351/) (2024)
- [The complexity of quantum support vector machines](https://mlsanity.com/paper/2203.00031/) (2022)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Quantum policy gradient algorithms](https://mlsanity.com/paper/2212.09328/) (2022)
- [Revisiting dequantization and quantum advantage in learning tasks](https://mlsanity.com/paper/2112.00811/) (2021)
- [Quantum Gaussian Process Regression for Bayesian Optimization](https://mlsanity.com/paper/2304.12923/) (2023)
- [Quantum Transformer: Accelerating model inference via quantum linear algebra](https://mlsanity.com/paper/2402.16714/) (2024)
- [A unifying framework for differentially private quantum algorithms](https://mlsanity.com/paper/2307.04733/) (2023)
- [Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters](https://mlsanity.com/paper/2311.14823/) (2023)
- [Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms](https://mlsanity.com/paper/2203.03604/) (2022)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [When can classical neural networks represent quantum states?](https://mlsanity.com/paper/2410.23152/) (2024)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [Quantum Topological Data Analysis with Linear Depth and Exponential Speedup](https://mlsanity.com/paper/2108.02811/) (2021)
- [Topological data analysis on noisy quantum computers](https://mlsanity.com/paper/2209.09371/) (2022)
- [Quantum algorithms for SVD-based data representation and analysis](https://mlsanity.com/paper/2104.08987/) (2021)
- [Multivariate trace estimation using quantum state space linear algebra](https://mlsanity.com/paper/2405.01098/) (2024)
- [Provable quantum speedups for computing persistence in topological data analysis](https://mlsanity.com/paper/2410.21258/) (2024)
- [An Introduction to Quantum Computing for Statisticians and Data Scientists](https://mlsanity.com/paper/2112.06587/) (2021)
- [Advances in Machine Learning: Where Can Quantum Techniques Help?](https://mlsanity.com/paper/2507.08379/) (2025)
- [Accelerating Inference for Multilayer Neural Networks with Quantum Computers](https://mlsanity.com/paper/2510.07195/) (2025)
- [Quantum Inspired Adaptive Boosting](https://mlsanity.com/paper/2102.00949/) (2021)
- [Quantum Semi-Supervised Kernel Learning](https://mlsanity.com/paper/2204.10700/) (2022)
- [A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm](https://mlsanity.com/paper/2406.13879/) (2024)
- [An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems](https://mlsanity.com/paper/2411.02087/) (2024)
- [Quantitative Evaluation of Quantum/Classical Neural Network Using a Game Solver Metric](https://mlsanity.com/paper/2503.21514/) (2025)

## Abstract (arXiv)

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quantum-inspired algorithm for recommendation systems [STOC'19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gily'en, Su, Low, and Wiebe [STOC'19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.