A quantum-inspired classical algorithm for recommendation systems

2018/07/10 by Ewin Tang · 3 voices · 23 citations
Computer Science · #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #cs.DS #cs.IR #cs.LG #quant-ph

paper · pdf · doi:10.1145/3313276.3316310

openalex created_date 2018/07/19 · openalex publication_date 2019/06/20 · openalex updated_date 2026/07/30

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.

Citations

• Fast monte-carlo algorithms for finding low-rank approximations
• Strengths and Weaknesses of Quantum Computing
• A Simpler Approach to Matrix Completion
• Quantum Computing in the NISQ era and beyond

Cited by

• Practical Quantum Advantage before Fault Tolerance via Quantum-Informed Machine Learning
• How hard is it to verify a classical shadow?
• Low-depth measurement-based deterministic quantum state preparation
• Accelerating Inference for Multilayer Neural Networks with Quantum Computers
• Quantum-inspired Benchmark for Estimating Intrinsic Dimension
• Dequantization and Hardness of Spectral Sum Estimation
• Data Complexity: a threshold between Classical and Quantum Machine Learning -- Part I
• On the Complexity of Decoded Quantum Interferometry
• Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
• A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
• Advances in Machine Learning: Where Can Quantum Techniques Help?
• Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Classical optimization algorithms for diagonalizing quantum Hamiltonians
• One Polynomial Strategy for Computing Local Projections on Square-Lattice Cluster States
• A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
• Networked Quantum Services
• "Quantum supremacy" challenged. Instantaneous noise-based logic with benchmark demonstrations
• Assessing Quantum Advantage for Gaussian Process Regression
• Quantum-assisted anomaly detection with multivariate Gaussian distribution
• A distillation-teleportation protocol for fault-tolerant QRAM
• On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
• Quantum Computing and AI: Perspectives on Advanced Automation in Science and Engineering

Discussions

• [1807.04271] A quantum-inspired classical algorithm for recommendation systems [lobsters, 5 points, 0 comments]
• A quantum-inspired classical algorithm for recommendation systems [hn, 1 points, 0 comments]
• Ewin Tang Agrees. arxiv.org/abs/1807.04271 [bsky, 0 points, 0 comments]

Related

• Quantum Recommendation Systems
• An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
• Parametrized Complexity of Quantum Inspired Algorithms
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• Quantum Machine Learning For Classical Data