Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1603.08675 · Leibniz international proceedings in informatics

Quantum Recommendation Systems

Iordanis Kerenidis, Anupam Prakash

Published Mar 29, 2016• 270 citations
arXivHTMLPDF

Abstract

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 \times 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(\text{poly}(k)\text{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.

DOI
10.4230/lipics.itcs.2017.49

Related papers

A quantum-inspired classical algorithm for recommendation systems

Ewin Tang

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.

arXiv:1807.04271•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•367 citations

Quantum tensor singular value decomposition with applications to recommendation systems

Xiaoqiang Wang, Lejia Gu, Joseph H. W. Lee +1 more

In this paper, we present a quantum singular value decomposition algorithm for third-order tensors inspired by the classical algorithm of tensor singular value decomposition (t-svd) and then extend it to order-$p$ tensors. It can be proved that the quantum version of the t-svd for a third-order tensor $\mathcal{A} \in \mathbb{R}^{N\times N \times N}$ achieves the complexity of $\mathcal{O}(N{\rm polylog}(N))$, an exponential speedup compared with its classical counterpart. As an application, we propose a quantum algorithm for recommendation systems which incorporates the contextual situation of users to the personalized recommendation. We provide recommendations varying with contexts by measuring the output quantum state corresponding to an approximation of this user's preferences. This algorithm runs in expected time $\mathcal{O}(N{\rm polylog}(N){\rm poly}(k)),$ if every frontal slice of the preference tensor has a good rank-$k$ approximation. At last, we provide a quantum algorithm for tensor completion based on a different truncation method which is tested to have a good performance in dynamic video completion.

arXiv:1910.01262•Oct 3, 2019•2 citations

Quantum-Inspired Classical Algorithms for Singular Value Transformation

Dhawal Jethwani, François Le Gall, Sanjay Kumar Singh

A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).

arXiv:1910.05699•Leibniz international proceedings in informatics•Oct 13, 2019•14 citations

Quantum Nearest Neighbor Collaborative Filtering Algorithm for Recommendation System

Jiaye Li, Jinjing Shi, Jian Zhang +4 more

Recommendation has become especially crucial during the COVID-19 pandemic as a significant number of people rely on online shopping from home. Existing recommendation algorithms, designed to address issues like cold start and data sparsity, often overlook the time constraints of users. Specifically, users expect to receive recommendations for products of interest in the shortest possible time. To address this challenge, we propose a novel collaborative filtering recommendation algorithm that leverages the advantages of quantum computing circuits based on data reconstruction. This approach allows for the rapid identification of users similar to the target user, thereby improving recommendation speed. In our method, we utilize the information of known users to linearly reconstruct that of the target users, forming a relational matrix. Subsequently, we employ \(l_{2,1}-\) norm and \(l_{1}-\) norm to sparsely constrain the relationship matrix, deducing the weight of each known user. The final step involves providing similar recommendations to target users based on these weights. Furthermore, we implement the proposed algorithm using a quantum circuit, enabling exponential acceleration. The final weight matrix is derived from the quantum state outputted by the circuit. The speed of this process is theoretically demonstrated in detail. Experimental results indicate that our algorithm outperforms state-of-the-art methods in terms of root mean squared error (RMSE), mean absolute error (MAE) and normalized discounted cumulative gain (NDCG). Compared to state-of-the-art comparison algorithms, the proposed algorithm achieves the fastest recommendation speed across eight public datasets.

ACM Transactions on Knowledge Discovery from Data•Jun 29, 2024•6 citations

Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms

Chenjian Li, Mingsheng Ying, Guan, Ji

We study the differential privacy (DP) of the quantum recommendation algorithm of Kerenidis--Prakash and its quantum-inspired classical counterpart. Under standard low-rank and incoherence assumptions on the preference matrix, we show that the randomness already present in the algorithms' measurement/$\ell_2$-sampling steps can act as a privacy-curating mechanism, yielding $(\varepsilon,δ)$-DP without injecting additional DP noise through the interface. Concretely, for a system with $m$ users and $n$ items and rank parameter $k$, we prove $\varepsilon=\mathcal O(\sqrt{k/n})$ and $δ= \mathcal O\big(k^2/\min^2\{m,n\}\big)$; in the typical regime $k=\mathrm{polylog}(m,n)$ this simplifies to $\varepsilon=\tilde{\mathcal O}(1/\sqrt n)$ and $δ=\tilde{\mathcal O}\big(1/\min^2\{m,n\}\big)$. Our analysis introduces a perturbation technique for truncated SVD under a single-entry update, which tracks the induced change in the low-rank reconstruction while avoiding unstable singular-vector comparisons. Finally, we validate the scaling on real-world rating datasets and compare against classical DP recommender baselines.

arXiv:2502.04758•Feb 7, 2025•0 citations

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The $q$-means algorithm has convergence and precision guarantees similar to $k$-means, and it outputs with high probability a good approximation of the $k$ cluster centroids like the classical algorithm. Given a dataset of $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)$ per iteration, where $κ(V)$ is the condition number, $μ(V)$ is a parameter that appears in quantum linear algebra procedures and $η= \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)$ per iteration, which is linear in the number of features $d$, and polynomial in the rank $k$, the maximum square norm $η$ and the error parameter $δ$. Both running times are only polylogarithmic in the number of datapoints $N$. Our algorithm provides substantial savings compared to the classical $k$-means algorithm that runs in time $O(kdN)$ per iteration, particularly for the case of large datasets.

arXiv:1812.03584•Dec 10, 2018•119 citations
A recommendation system uses the past purchases or ratings of nnn products by a group of mmm users, in order to provide personalized recommendations to individual users. The information is modeled as an m×nm \times nm×n preference matrix which is assumed to have a good rank-kkk approximation, for a small constant kkk. In this work, we present a quantum algorithm for recommendation systems that has running time O(poly(k)polylog(mn))O(\text{poly}(k)\text{polylog}(mn))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.
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.
In this paper, we present a quantum singular value decomposition algorithm for third-order tensors inspired by the classical algorithm of tensor singular value decomposition (t-svd) and then extend it to order-ppp tensors. It can be proved that the quantum version of the t-svd for a third-order tensor A∈RN×N×N\mathcal{A} \in \mathbb{R}^{N\times N \times N}A∈RN×N×N achieves the complexity of O(Npolylog(N))\mathcal{O}(N{\rm polylog}(N))O(Npolylog(N)), an exponential speedup compared with its classical counterpart. As an application, we propose a quantum algorithm for recommendation systems which incorporates the contextual situation of users to the personalized recommendation. We provide recommendations varying with contexts by measuring the output quantum state corresponding to an approximation of this user's preferences. This algorithm runs in expected time O(Npolylog(N)poly(k)),\mathcal{O}(N{\rm polylog}(N){\rm poly}(k)),O(Npolylog(N)poly(k)), if every frontal slice of the preference tensor has a good rank-kkk approximation. At last, we provide a quantum algorithm for tensor completion based on a different truncation method which is tested to have a good performance in dynamic video completion.
A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).
Recommendation has become especially crucial during the COVID-19 pandemic as a significant number of people rely on online shopping from home. Existing recommendation algorithms, designed to address issues like cold start and data sparsity, often overlook the time constraints of users. Specifically, users expect to receive recommendations for products of interest in the shortest possible time. To address this challenge, we propose a novel collaborative filtering recommendation algorithm that leverages the advantages of quantum computing circuits based on data reconstruction. This approach allows for the rapid identification of users similar to the target user, thereby improving recommendation speed. In our method, we utilize the information of known users to linearly reconstruct that of the target users, forming a relational matrix. Subsequently, we employ l2,1−l_{2,1}-l2,1​− norm and l1−l_{1}-l1​− norm to sparsely constrain the relationship matrix, deducing the weight of each known user. The final step involves providing similar recommendations to target users based on these weights. Furthermore, we implement the proposed algorithm using a quantum circuit, enabling exponential acceleration. The final weight matrix is derived from the quantum state outputted by the circuit. The speed of this process is theoretically demonstrated in detail. Experimental results indicate that our algorithm outperforms state-of-the-art methods in terms of root mean squared error (RMSE), mean absolute error (MAE) and normalized discounted cumulative gain (NDCG). Compared to state-of-the-art comparison algorithms, the proposed algorithm achieves the fastest recommendation speed across eight public datasets.
We study the differential privacy (DP) of the quantum recommendation algorithm of Kerenidis--Prakash and its quantum-inspired classical counterpart. Under standard low-rank and incoherence assumptions on the preference matrix, we show that the randomness already present in the algorithms' measurement/ℓ2\ell_2ℓ2​-sampling steps can act as a privacy-curating mechanism, yielding (ε,δ)(\varepsilon,δ)(ε,δ)-DP without injecting additional DP noise through the interface. Concretely, for a system with mmm users and nnn items and rank parameter kkk, we prove ε=O(k/n)\varepsilon=\mathcal O(\sqrt{k/n})ε=O(k/n​) and δ=O(k2/min⁡2{m,n})δ= \mathcal O\big(k^2/\min^2\{m,n\}\big)δ=O(k2/min2{m,n}); in the typical regime k=polylog(m,n)k=\mathrm{polylog}(m,n)k=polylog(m,n) this simplifies to ε=O~(1/n)\varepsilon=\tilde{\mathcal O}(1/\sqrt n)ε=O~(1/n​) and δ=O~(1/min⁡2{m,n})δ=\tilde{\mathcal O}\big(1/\min^2\{m,n\}\big)δ=O~(1/min2{m,n}). Our analysis introduces a perturbation technique for truncated SVD under a single-entry update, which tracks the induced change in the low-rank reconstruction while avoiding unstable singular-vector comparisons. Finally, we validate the scaling on real-world rating datasets and compare against classical DP recommender baselines.
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)κ(V)κ(V) is the condition number, μ(V)μ(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2η= \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm ηηη and the error parameter δδδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)O(kdN) per iteration, particularly for the case of large datasets.