A quantum-inspired classical algorithm for recommendation systems

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\times n$ matrix in a data structure supporting certain ${\ell }^2$-norm sampling operations, outputs an ${\ell }^2$-norm sample from a rank-$k$ approximation of that matrix in time $O(\text{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 ${\ell }^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.

arXiv comment32 pages; revised structure of document, improved runtime, simplified algorithm and notation

References in corpus (4)

• Quantum Computing in the NISQ era and beyond
• Strengths and Weaknesses of Quantum Computing
• Quantum principal component analysis
• A Simpler Approach to Matrix Completion

Cited by in corpus (70)

• Challenges and Opportunities in Quantum Machine Learning
• A rigorous and robust quantum speed-up in supervised machine learning
• Quantum computing for finance
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Quantum-Inspired Support Vector Machine
• Quantum Machine Learning for Chemistry and Physics
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Variational Quantum State Eigensolver
• Quantum-inspired algorithms in practice
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• The complexity of quantum support vector machines
• Quantum machine learning and quantum biomimetics: A perspective
• Feature Selection for Recommender Systems with Quantum Computing
• An improved quantum-inspired algorithm for linear regression
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Towards quantum advantage via topological data analysis
• Quantum Algorithm for Fidelity Estimation
• Convex optimization of programmable quantum computers
• Optimization and learning of quantum programs
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Quantum Differentially Private Sparse Regression Learning
• A brief introduction to quantum algorithms
• Learning with Density Matrices and Random Features
• Quantum algorithm for Neighborhood Preserving Embedding
• Fast Quantum Algorithms for Trace Distance Estimation
• Quantum Regularized Least Squares
• Quantum simulations of Fermionic Hamiltonians with efficient encoding and ansatz schemes
• Circuit complexity of quantum access models for encoding classical data
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Networked Quantum Services
• Quantum algorithms for scientific computing
• Quantum Machine Learning Implementations: Proposals and Experiments
• Quantum-inspired classical algorithm for molecular vibronic spectra
• Quantum Next Generation Reservoir Computing: An Efficient Quantum Algorithm for Forecasting Quantum Dynamics
• "Quantum supremacy" revisited: Low-complexity, deterministic solutions of the original Deutsch-Jozsa problem in classical physical systems
• Quantum algorithms for escaping from saddle points
• Entanglement-induced provable and robust quantum learning advantages
• Quantum Semi-Supervised Kernel Learning
• Qudit Machine Learning
• Quantum and Quantum-Inspired Stereographic K Nearest-Neighbour Clustering
• The quantum detection of projectors in finite-dimensional algebras and holography
• Synergies Between Operations Research and Quantum Information Science
• GraphStateVis: Interactive Visual Analysis of Qubit Graph States and their Stabilizer Groups
• QRAM: A Survey and Critique
• Amplitude Ratios and Neural Network Quantum States
• A Quantum Search Decoder for Natural Language Processing
• Quantum advantage from energy measurements of many-body quantum systems
• Sparse random Hamiltonians are quantumly easy
• Dimension reduction and redundancy removal through successive Schmidt decompositions
• The topology of data hides in quantum thermal states
• Approximating Hamiltonian dynamics with the Nyström method
• A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time
• Quantum Computing for Data Centric Engineering and Science
• The 7 faces of quantum NP
• Quantum contextual bandits and recommender systems for quantum data
• Quantum Advantage in Variational Bayes Inference
• Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
• Fast Extraction of Word Embedding from Q-contexts
• Quantum Alphatron: quantum advantage for learning with kernels and noise
• Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
• Des-q: a quantum algorithm to provably speedup retraining of decision trees
• Provable quantum speedups for computing persistence in topological data analysis
• Quantum Algorithms for tensor-SVD
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Lower bounds for quantum-inspired classical algorithms via communication complexity
• Quantum-Stable Robust Principal Component Analysis: Theory and Evidence from NISQ Regimes
• Quantum Computation