A quantum-inspired classical algorithm for recommendation systems. (English) Zbl 1433.68436
Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 217-228 (2019).
MSC:
| 68T35 | Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence |
| 68P05 | Data structures |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68W40 | Analysis of algorithms |
Keywords:
exponential speedup; low-rank approximation; quantum machine learning; recommender systems; samplingReferences:
| [1] | Scott Aaronson. 2015. Read the fine print. Nature Physics 11, 4 (2015), 291. |
| [2] | Dimitris Achlioptas and Frank McSherry. 2007. Fast computation of low-rank matrix approximations. Journal of the ACM (JACM) 54, 2 (2007), 9. 10.1145/1219092.1219097 · Zbl 1311.94031 |
| [3] | Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Mark Tuttle. 2005. Improved recommendation systems. In Symposium on Discrete Algorithms. · Zbl 1297.68254 |
| [4] | Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry, and Jared Saia. 2001. Spectral analysis of data. In Symposium on Theory of Computing. ACM. 10.1145/380752.380859 · Zbl 1323.68426 |
| [5] | Robert M Bell and Yehuda Koren. 2007. Lessons from the Netflix prize challenge. ACM SIGKDD Explorations Newsletter 9, 2 (2007), 75-79. 10.1145/1345448.1345465 |
| [6] | Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. |
| [7] | Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (1997), 1510-1523. 10.1137/S0097539796300933 · Zbl 0895.68044 |
| [8] | Nader H. Bshouty and Jeffrey C. Jackson. 1999. Learning DNF over the uniform distribution using a quantum example oracle. SIAM J. Comput. 28, 3 (1999), 1136-1153. 10.1137/S0097539795293123 · Zbl 0918.68033 |
| [9] | Amit Deshpande and Santosh Vempala. 2006. Adaptive sampling and fast lowrank matrix approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 292-303. 10.1007/11830924_28 · Zbl 1155.68575 |
| [10] | P. Drineas, R. Kannan, and M. Mahoney. 2006. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM J. Comput. 36, 1 (2006), 132-157. 10.1137/S0097539704442684 · Zbl 1111.68147 |
| [11] | Petros Drineas, Iordanis Kerenidis, and Prabhakar Raghavan. 2002. Competitive recommendation systems. In Symposium on Theory of Computing. ACM. 10.1145/509907.509922 · Zbl 1192.91076 |
| [12] | P. Drineas, M. Mahoney, and S. Muthukrishnan. 2008. Relative-error CU R matrix decompositions. SIAM J. Matrix Anal. Appl. 30, 2 (2008), 844-881. 10.1137/07070471X · Zbl 1183.68738 |
| [13] | Alan Frieze, Ravi Kannan, and Santosh Vempala. 2004. Fast Monte-Carlo algorithms for finding low-rank approximations. Journal of the ACM (JACM) 51, 6 (2004), 1025-1041. 10.1145/1039488.1039494 · Zbl 1125.65005 |
| [14] | András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. 2018. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. (2018). arXiv: 1806.01838 · Zbl 1433.68147 |
| [15] | Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum algorithm for linear systems of equations. Physical review letters 103, 15 (2009), 150502. |
| [16] | Elad Hazan, Tomer Koren, and Nati Srebro. 2011. Beating SGD: Learning SVMs in sublinear time. In Neural Information Processing Systems. |
| [17] | Ravindran Kannan and Santosh Vempala. 2017. Randomized algorithms in numerical linear algebra. Acta Numerica 26 (2017), 95-135. · Zbl 1378.65084 |
| [18] | Iordanis Kerenidis and Anupam Prakash. 2017. Quantum gradient descent for linear systems and least squares. (2017). arXiv: 1704.04992 · Zbl 1402.68189 |
| [19] | Iordanis Kerenidis and Anupam Prakash. 2017. Quantum recommendation systems. In Innovations in Theoretical Computer Science. · Zbl 1402.68189 |
| [20] | Jon Kleinberg and Mark Sandler. 2008. Using mixture models for collaborative filtering. J. Comput. System Sci. 74, 1 (2008), 49-69. 10.1016/j.jcss.2007.04.013 · Zbl 1129.68327 |
| [21] | Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factorization techniques for recommender systems. Computer 42, 8 (2009). |
| [22] | Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. 2001. Recommendation systems: a probabilistic analysis. J. Comput. System Sci. 63, 1 (2001), 42 - 61. 10.1006/jcss.2001.1757 · Zbl 0984.68152 |
| [23] | Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. (2013). arXiv: 1307.0411 |
| [24] | Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. 2014. Quantum principal component analysis. Nature Physics 10, 9 (2014), 631. |
| [25] | John Preskill. 2018. Quantum Computing in the NISQ era and beyond. Quantum 2 (2018), 79. |
| [26] | Benjamin Recht. 2011. |
| [27] | A simpler approach to matrix completion. Journal of Machine Learning Research 12 (2011), 3413-3430. · Zbl 1280.68141 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
