# A quantum-inspired classical algorithm for recommendation systems

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

## Key facts

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

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

- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [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)
- [A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance](https://mlsanity.com/paper/2401.11351/) (2024)
- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (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)
- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [Feature Selection for Recommender Systems with Quantum Computing](https://mlsanity.com/paper/2110.05089/) (2021)
- [Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation](https://mlsanity.com/paper/2211.08737/) (2022)
- [Revisiting dequantization and quantum advantage in learning tasks](https://mlsanity.com/paper/2112.00811/) (2021)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Detecting quantum entanglement with unsupervised learning](https://mlsanity.com/paper/2103.04804/) (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)
- [When can classical neural networks represent quantum states?](https://mlsanity.com/paper/2410.23152/) (2024)
- [Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation](https://mlsanity.com/paper/2301.11936/) (2023)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Quantum Next Generation Reservoir Computing: An Efficient Quantum Algorithm for Forecasting Quantum Dynamics](https://mlsanity.com/paper/2308.14239/) (2023)
- [Quantum Topological Data Analysis with Linear Depth and Exponential Speedup](https://mlsanity.com/paper/2108.02811/) (2021)
- [Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems](https://mlsanity.com/paper/2204.01815/) (2022)
- [Implementation of Trained Factorization Machine Recommendation System on Quantum Annealer](https://mlsanity.com/paper/2210.12953/) (2022)
- [Quantum contextual bandits and recommender systems for quantum data](https://mlsanity.com/paper/2301.13524/) (2023)
- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [Advantage of Quantum Machine Learning from General Computational Advantages](https://mlsanity.com/paper/2312.03057/) (2023)
- [Entanglement-induced provable and robust quantum learning advantages](https://mlsanity.com/paper/2410.03094/) (2024)
- [A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values](https://mlsanity.com/paper/2506.05216/) (2025)

## Abstract (arXiv)

We give a classical analogue to Kerenidis and Prakash's quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Our main result is an algorithm that, given an m × n matrix in a data structure supporting certain ℓ2-norm sampling operations, outputs an ℓ2-norm sample from a rank-k approximation of that matrix in time O(poly(k)log(mn)), only polynomially slower than the quantum algorithm. As a consequence, Kerenidis and Prakash's algorithm does not in fact give an exponential speedup over classical algorithms. Further, under strong input assumptions, the classical recommendation system resulting from our algorithm produces recommendations exponentially faster than previous classical systems, which run in time linear in m and n. The main insight of this work is the use of simple routines to manipulate ℓ2-norm sampling distributions, which play the role of quantum superpositions in the classical setting. This correspondence indicates a potentially fruitful framework for formally comparing quantum machine learning algorithms to classical machine learning algorithms.