Quantum Recommendation Systems
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Quantum Machine LearningRecommendation SystemsSimilar Papers 제목 키워드 기반
Quantum tensor singular value decomposition with applications to recommendation systems
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$ tensor…
Recommendation SystemsA quantum-inspired classical algorithm for recommendation systems
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 res…
BIG-bench Machine LearningQuantum Machine LearningRecommendation SystemsPerformance-Driven QUBO for Recommender Systems on Quantum Annealers
We propose Counterfactual Analysis Quadratic Unconstrained Binary Optimization (CAQUBO) to solve QUBO problems for feature selection in recommender systems. CAQUBO leverages counterfactual analysis to measure the impact …
counterfactualfeature selectionRecommendation SystemsCRUISE on Quantum Computing for Feature Selection in Recommender Systems
Using Quantum Computers to solve problems in Recommender Systems that classical computers cannot address is a worthwhile research topic. In this paper, we use Quantum Annealers to address the feature selection problem in…
counterfactualfeature selectionRecommendation SystemsRecommender systems inspired by the structure of quantum theory
Physicists use quantum models to describe the behavior of physical systems. Quantum models owe their success to their interpretability, to their relation to probabilistic models (quantization of classical models) and to …
QuantizationRecommendation Systems