Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/89347
Title: Quantum recommendation systems
Authors: Kerenidis, Iordanis
Prakash, Anupam
Keywords: Quantum Machine Learning
Recommendation Systems
DRNTU::Science::Physics
Issue Date: 2017
Source: Kerenidis, I., & Prakash, A. (2017). Quantum recommendation systems. Leibniz International Proceedings in Informatics, 67, 49-. doi:10.4230/LIPIcs.ITCS.2017.49
Series/Report no.: Leibniz International Proceedings in Informatics
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.
URI: https://hdl.handle.net/10356/89347
http://hdl.handle.net/10220/46208
DOI: http://dx.doi.org/10.4230/LIPIcs.ITCS.2017.49
Rights: © 2017 Iordanis Kerenidis and Anupam Prakash; licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Quantum recommendation systems.pdf504.99 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.