Ewin Tang
ABSTRACT
We give a classical analogue to Kerenidis and Prakash’s quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Our main result is an algorithm that, given an m × n matrix in a data structure supporting certain ℓ2-norm sampling operations, outputs an ℓ2-norm sample from a rank-k approximation of that matrix in time O(poly(k)log(mn)), only polynomially slower than the quantum algorithm. As a consequence, Kerenidis and Prakash’s algorithm does not in fact give an exponential speedup over classical algorithms. Further, under strong input assumptions, the classical recommendation system resulting from our algorithm produces recommendations exponentially faster than previous classical systems, which run in time linear in m and n.
The main insight of this work is the use of simple routines to manipulate ℓ2-norm sampling distributions, which play the role of quantum superpositions in the classical setting. This correspondence indicates a potentially fruitful framework for formally comparing quantum machine learning algorithms to classical machine learning algorithms.
- Scott Aaronson. 2015. Read the fine print. Nature Physics 11, 4 (2015), 291.Google Scholar
Cross Ref
- Dimitris Achlioptas and Frank McSherry. 2007. Fast computation of low-rank matrix approximations. Journal of the ACM (JACM) 54, 2 (2007), 9. Google ScholarDigital Library
- Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Mark Tuttle. 2005. Improved recommendation systems. In Symposium on Discrete Algorithms. Google ScholarDigital Library
- Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry, and Jared Saia. 2001. Spectral analysis of data. In Symposium on Theory of Computing. ACM. Google ScholarDigital Library
- Robert M Bell and Yehuda Koren. 2007. Lessons from the Netflix prize challenge. ACM SIGKDD Explorations Newsletter 9, 2 (2007), 75–79. Google ScholarDigital Library
- Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997.Google Scholar
- Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (1997), 1510–1523. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Petros Drineas, Iordanis Kerenidis, and Prabhakar Raghavan. 2002. Competitive recommendation systems. In Symposium on Theory of Computing. ACM. Google ScholarDigital Library
- P. Drineas, M. Mahoney, and S. Muthukrishnan. 2008. Relative-error CU R matrix decompositions. SIAM J. Matrix Anal. Appl. 30, 2 (2008), 844–881. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.01838Google Scholar
- Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum algorithm for linear systems of equations. Physical review letters 103, 15 (2009), 150502.Google Scholar
- Elad Hazan, Tomer Koren, and Nati Srebro. 2011. Beating SGD: Learning SVMs in sublinear time. In Neural Information Processing Systems. Google ScholarDigital Library
- Ravindran Kannan and Santosh Vempala. 2017. Randomized algorithms in numerical linear algebra. Acta Numerica 26 (2017), 95–135.Google ScholarCross Ref
- Iordanis Kerenidis and Anupam Prakash. 2017. Quantum gradient descent for linear systems and least squares. (2017). arXiv: 1704.04992Google Scholar
- Iordanis Kerenidis and Anupam Prakash. 2017. Quantum recommendation systems. In Innovations in Theoretical Computer Science.Google Scholar
- Jon Kleinberg and Mark Sandler. 2008. Using mixture models for collaborative filtering. J. Comput. System Sci. 74, 1 (2008), 49–69. Google ScholarDigital Library
- Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factorization techniques for recommender systems. Computer 42, 8 (2009).Google Scholar
- Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. 2001. Recommendation systems: a probabilistic analysis. J. Comput. System Sci. 63, 1 (2001), 42 – 61. Google ScholarDigital Library
- Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. (2013). arXiv: 1307.0411Google Scholar
- Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. 2014. Quantum principal component analysis. Nature Physics 10, 9 (2014), 631.Google ScholarCross Ref
- John Preskill. 2018. Quantum Computing in the NISQ era and beyond. Quantum 2 (2018), 79.Google ScholarCross Ref
- Benjamin Recht. 2011.Google Scholar
- A simpler approach to matrix completion. Journal of Machine Learning Research 12 (2011), 3413–3430.Google Scholar
Index Terms
- A quantum-inspired classical algorithm for recommendation systems
Recommendations
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing Quantum machine learning
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingWe present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by ...
Supercomputing leverages quantum machine learning and Grover’s algorithm
AbstractThe complexity of searching algorithms in classical computing is a classic problem and a research area. Quantum computers and quantum algorithms can efficiently compute some classically hard problems. In addition, quantum machine learning ...
Analysis of Classical and Quantum Resources for the Quantum Linear Systems Algorithm
ITNG '13: Proceedings of the 2013 10th International Conference on Information Technology: New GenerationsThe quantum algorithm by Harrow, Hassidim, and Lloyd solves a system of N linear equations and achieves exponential speedup over classical algorithms under certain conditions. The advantage to the algorithm is that log(N) rather than N registers are ...
Comments