Quantum Recommendation Systems

By Iordanis Kerenidis, Anupam Prakash. Information Technology Convergence and Services, 2016

451 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/87a0e58a7b64b47e3d95b70c78e3956fc9b690bb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Circuit-centric quantum classifiers (2018, unknown): “[10] Iordanis Kerenedis and Anupam Prakash.”
Quantum Computing in the NISQ era and beyond (2018, background): “thm is probably just too expensive to be executed successfully by a quantum computer which doesn’t use error correction. 6.7 Quantum recommendation systems Another recently proposed quantum algorithm [39] provides an exponential speedup over the best currently known classical algorithm for a useful ”
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, methodology): “A few algorithms, such as the procedure introduced in [64] actually do require that one write to QRAM; thus, for such use cases QROM would not be appropriate.”
Quantum machine learning (2016, unknown): “, exhibit promising applications in machine learning and data analysis [83, 84, 85, 86, 36, 87, 48, 88, 89, 90, 91, 92, 93, 21, 15, 22, 94, 95, 96].”
A generative modeling approach for benchmarking and training shallow quantum circuits (2018, background): “[31] Iordanis Kerenidis and Anupam Prakash, “Quantum rec-”
Quantum machine learning: a classical perspective (2017, methodology): “Prakash and Kerenidis [52,60] introduced the quantum singular value estimation (QSVE) algorithm, based on Szegedy’s work on quantum walks [81], which runs in time O(‖A‖F log MN/ ).”
A quantum-inspired classical algorithm for recommendation systems (2018, methodology): “Such a result would be interesting because Kerenidis and Prakash’s algorithm is a quantum machine learning (QML) algorithm.”
Continuous-variable quantum neural networks (2018, background): “Sufficiently powerful quantum computers can in principle provide computational speedups for key machine learning algorithms and subroutines such as data fitting [4], principal component analysis [5], Bayesian inference [6,7], Monte Carlo methods [8], support vector machines [9,10], Boltzmann machine”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “[35, 37], and our work fills a minor gap that was present in earlier implementation proposals.”