License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.49
URN: urn:nbn:de:0030-drops-81541
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8154/
Go to the corresponding LIPIcs Volume Portal

Kerenidis, Iordanis ; Prakash, Anupam

Quantum Recommendation Systems

pdf-format:
LIPIcs-ITCS-2017-49.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{kerenidis_et_al:LIPIcs:2017:8154,
  author =	{Iordanis Kerenidis and Anupam Prakash},
  title =	{{Quantum Recommendation Systems}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{49:1--49:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8154},
  URN =		{urn:nbn:de:0030-drops-81541},
  doi =		{10.4230/LIPIcs.ITCS.2017.49},
  annote =	{Keywords: Recommendation systems, quantum machine learning, singular value estimation, matrix sampling, quantum algorithms.}
}

Keywords: Recommendation systems, quantum machine learning, singular value estimation, matrix sampling, quantum algorithms.
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI