Document Open Access Logo

Quantum Recommendation Systems

Authors Iordanis Kerenidis, Anupam Prakash

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.49.pdf
  • Filesize: 0.49 MB
  • 21 pages

Document Identifiers

Author Details

Iordanis Kerenidis
Anupam Prakash

Cite AsGet BibTex

Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ITCS.2017.49

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.
Keywords
  • Recommendation systems
  • quantum machine learning
  • singular value estimation
  • matrix sampling
  • quantum algorithms.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson. Read the fine print. Nature Physics, 11(4):291-293, 2015. Google Scholar
  2. Dimitris Achlioptas and Frank McSherry. Fast computation of low rank matrix approximations. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 611-618. ACM, 2001. Google Scholar
  3. Gediminas Adomavicius and Alexander Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. Knowledge and Data Engineering, IEEE Transactions on, 17(6):734-749, 2005. Google Scholar
  4. Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Mark Tuttle. Improved recommendation systems. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1174-1183. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  5. Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry, and Jared Saia. Spectral analysis of data. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 619-626. ACM, 2001. Google Scholar
  6. Robert M Bell and Yehuda Koren. Lessons from the netflix prize challenge. ACM SIGKDD Explorations Newsletter, 9(2):75-79, 2007. Google Scholar
  7. Andrew M Childs. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathematical Physics, 294(2):581-603, 2010. Google Scholar
  8. Petros Drineas, Iordanis Kerenidis, and Prabhakar Raghavan. Competitive recommendation systems. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, pages 82-90. ACM, 2002. Google Scholar
  9. Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph/0208112, 2002. Google Scholar
  10. Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009. Google Scholar
  11. Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665-674. ACM, 2013. Google Scholar
  12. A Yu Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/9511026, 1995. Google Scholar
  13. Yehuda Koren and Robert Bell. Advances in collaborative filtering. In Recommender systems handbook, pages 145-186. Springer, 2011. Google Scholar
  14. Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009. Google Scholar
  15. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. Arxiv preprint:1307.0411, 2013. Google Scholar
  16. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum self analysis. Arxiv preprint:1307.1401, 2013. Google Scholar
  17. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum support vector machine for big feature and big data classification. Arxiv preprint:1307.0471, 2013. Google Scholar
  18. Christos H Papadimitriou, Hisao Tamaki, Prabhakar Raghavan, and Santosh Vempala. Latent semantic indexing: A probabilistic analysis. In Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 159-168. ACM, 1998. Google Scholar
  19. Anupam Prakash. Quantum algorithms for linear algebra and machine learning. Ph.D Thesis, University of California, Berkeley., 2014. Google Scholar
  20. Anand Rajaraman and Jeffrey D Ullman. Mining of massive datasets, volume 77. Cambridge University Press Cambridge, 2012. Google Scholar
  21. Elaine Rich. User modeling via stereotypes*. Cognitive science, 3(4):329-354, 1979. Google Scholar
  22. Cyril Stark. Recommender systems inspired by the structure of quantum theory. arXiv preprint arXiv:1601.06035, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact