# Quantum Recommendation Systems

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

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2016.

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

- [Quantum Federated Learning with Quantum Data](https://mlsanity.com/paper/2106.00005/) (2021)
- [Quantum Vision Transformers](https://mlsanity.com/paper/2209.08167/) (2022)
- [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)
- [Universal Adversarial Examples and Perturbations for Quantum Classifiers](https://mlsanity.com/paper/2102.07788/) (2021)
- [Quantum Reinforcement Learning via Policy Iteration](https://mlsanity.com/paper/2203.01889/) (2022)
- [Feature Selection for Recommender Systems with Quantum Computing](https://mlsanity.com/paper/2110.05089/) (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)
- [Effects of quantum resources on the statistical complexity of quantum circuits](https://mlsanity.com/paper/2102.03282/) (2021)
- [The Hintons in your Neural Network: a Quantum Field Theory View of Deep Learning](https://mlsanity.com/paper/2103.04913/) (2021)
- [Quantum Transformer: Accelerating model inference via quantum linear algebra](https://mlsanity.com/paper/2402.16714/) (2024)
- [Expressive variational quantum circuits provide inherent privacy in federated learning](https://mlsanity.com/paper/2309.13002/) (2023)
- [Representation of binary classification trees with binary features by quantum circuits](https://mlsanity.com/paper/2108.13207/) (2021)
- [Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits](https://mlsanity.com/paper/2111.07952/) (2021)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Verifying Fairness in Quantum Machine Learning](https://mlsanity.com/paper/2207.11173/) (2022)
- [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)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://mlsanity.com/paper/2106.02496/) (2021)
- [Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation](https://mlsanity.com/paper/2301.11936/) (2023)
- [Application of quantum-inspired generative models to small molecular datasets](https://mlsanity.com/paper/2304.10867/) (2023)
- [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)
- [Are Quantum Computers Practical Yet? A Case for Feature Selection in Recommender Systems using Tensor Networks](https://mlsanity.com/paper/2205.04490/) (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)

## Abstract (arXiv)

A recommendation system uses the past purchases or ratings of n products by a group of m users, in order to provide personalized recommendations to individual users. The information is modeled as an m × n preference matrix which is assumed to have a good rank-k approximation, for a small constant k. In this work, we present a quantum algorithm for recommendation systems that has running time O(poly(k)polylog(mn)). All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application.