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

Physica Scripta

A novel quantum recommender system

Shang Bing Gao, Yu‐Guang Yang

Published Nov 21, 2022• 8 citations
Publisher

Abstract

Abstract Recommendation system is a kind of information filtering system, which plays an increasingly important role in the era of big data. In this work, we present a novel quantum recommender system, which can also be regarded as a quantum version of the matrix reconstruction algorithm. In order to obtain two factors in the quantum state form, a quantum version of the alternating least squares algorithm is designed. And based on the factor matrices, the reconstruction matrix of the original rating matrix is calculated. The complexity analysis shows that our quantum algorithm may achieve an exponential speedup relative to the classical counterpart under certain conditions.

DOI
10.1088/1402-4896/aca4a8

Related papers

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

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 Recommendation Systems

Iordanis Kerenidis, Anupam Prakash

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.

arXiv:1603.08675•Leibniz international proceedings in informatics•Mar 29, 2016•270 citations

Quantum-inspired algorithms in practice

Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan +1 more

We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.

arXiv:1905.10415•Quantum•Aug 13, 2020•134 citations

Intelligent recommender system based on quantum clustering and matrix completion

Oumayma Ouedrhiri, Oumayma Banouar, Salah El Hadaj +1 more

Abstract Faster than classical algorithms, quantum algorithms benefit from the superposition property of quantum information to offer significant speedup to complex algorithms. Therefore, quantum computing can be used to help machine learning algorithms by boosting their performance and accelerate the processing of time‐consuming ones. Clustering algorithms are very complex unsupervised learning algorithms. Indeed, the similarity calculation (distance) between input vectors is a resource‐consuming step, especially when working with large datasets. In this article, we propose a new better‐performing recommender system that operates as a combination of an adapted quantum K‐means algorithm and the singular value decomposition (SVT) algorithm. We integrate the developed quantum clustering algorithm to a prediction process of the proposed recommender system using matrix completion. To the best of our knowledge, no system with such details was proposed in the literature. The system was applied on the MovieLens dataset without a dimensionality reduction step and evaluated according to measures of information retrieval systems. The results of the quantum K‐means algorithm show that the quantum version leads to a logarithmic reduction of the time complexity compared to the classical algorithm. The proposed system has proved to be better than the previous tested ones in terms of precision and recall.

Concurrency and Computation Practice and Experience•Mar 15, 2022•17 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
Abstract Recommendation system is a kind of information filtering system, which plays an increasingly important role in the era of big data. In this work, we present a novel quantum recommender system, which can also be regarded as a quantum version of the matrix reconstruction algorithm. In order to obtain two factors in the quantum state form, a quantum version of the alternating least squares algorithm is designed. And based on the factor matrices, the reconstruction matrix of the original rating matrix is calculated. The complexity analysis shows that our quantum algorithm may achieve an exponential speedup relative to the classical counterpart under certain conditions.
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 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.
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 study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.
Abstract Faster than classical algorithms, quantum algorithms benefit from the superposition property of quantum information to offer significant speedup to complex algorithms. Therefore, quantum computing can be used to help machine learning algorithms by boosting their performance and accelerate the processing of time‐consuming ones. Clustering algorithms are very complex unsupervised learning algorithms. Indeed, the similarity calculation (distance) between input vectors is a resource‐consuming step, especially when working with large datasets. In this article, we propose a new better‐performing recommender system that operates as a combination of an adapted quantum K‐means algorithm and the singular value decomposition (SVT) algorithm. We integrate the developed quantum clustering algorithm to a prediction process of the proposed recommender system using matrix completion. To the best of our knowledge, no system with such details was proposed in the literature. The system was applied on the MovieLens dataset without a dimensionality reduction step and evaluated according to measures of information retrieval systems. The results of the quantum K‐means algorithm show that the quantum version leads to a logarithmic reduction of the time complexity compared to the classical algorithm. The proposed system has proved to be better than the previous tested ones in terms of precision and recall.
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.