Quantum Recommendation Systems

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.

22 pages

References in corpus (3)

• Quantum algorithms for supervised and unsupervised machine learning
• Creating superpositions that correspond to efficiently integrable probability distributions
• Recommender systems inspired by the structure of quantum theory

Cited by in corpus (41)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Circuit-centric quantum classifiers
• A generative modeling approach for benchmarking and training shallow quantum circuits
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Quantum Algorithm for Linear Regression
• Quantum-inspired algorithms in practice
• Quantum-assisted Helmholtz machines: A quantum-classical deep learning framework for industrial datasets in near-term devices
• Quantum Methods for Neural Networks and Application to Medical Image Classification
• Quantum data compression by principal component analysis
• Variational Quantum Singular Value Decomposition
• Quantum classification of the MNIST dataset with Slow Feature Analysis
• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• A Survey of Quantum Learning Theory
• Tower: Data Structures in Quantum Superposition
• Quantum Interior Point Methods for Semidefinite Optimization
• Quantum algorithms for training Gaussian Processes
• Optimal Usage of Quantum Random Access Memory in Quantum Machine Learning
• Quantum advantage for differential equation analysis
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• A quantum algorithm for simulating non-sparse Hamiltonians
• Quantum Finite Volume Method for Computational Fluid Dynamics with Classical Input and Output
• Quantum-inspired canonical correlation analysis for exponentially large dimensional data
• Quantum secure learning with classical samples
• Quantum matching pursuit: A quantum algorithm for sparse representations
• Inverse iteration quantum eigensolvers assisted with a continuous variable
• QFCNN: Quantum Fourier Convolutional Neural Network
• Quantum Bayesian Neural Networks
• Quantum-Inspired Classical Algorithm for Principal Component Regression
• Quantum Machine Learning Algorithm for Knowledge Graphs
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum-Inspired Classical Algorithm for Slow Feature Analysis
• When Quantum and Classical Models Disagree: Learning Beyond Minimum Norm Least Square
• Towards a Pattern Language for Quantum Algorithms
• Quantum algorithm for finding the negative curvature direction in non-convex optimization
• The Holy Grail of Quantum Artificial Intelligence: Major Challenges in Accelerating the Machine Learning Pipeline
• The Interplay between Quantum Contextuality and Wigner Negativity
• Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian
• Variational Quantum Circuit Model for Knowledge Graphs Embedding