Quantum Recommendation Systems
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 7 Pith papers
-
Quantum Data Fitting Algorithm for Non-sparse Matrices
Quantum data fitting algorithm for non-sparse N x N Hermitian matrices achieves O(κ² √N polylog(N) / (ε log κ)) runtime via QSVE, eigenvalue sign recovery, and regularization.
-
A Quantum Spectral Framework for Solving PDEs
A quantum method solves linear PDEs by block-encoding Fourier filters with reversible arithmetic, positioned as a structure-exploiting alternative to standard QSVT-based matrix inversion.
-
Spectral methods: crucial for machine learning, natural for quantum computers?
Quantum computers may enable more natural manipulation of Fourier spectra in ML models via the Quantum Fourier Transform, potentially leading to resource-efficient spectral methods.
-
Universal Matrix Multiplication on Quantum Computer
Proposes a QFT-based quantum matrix multiplication framework claiming O(n) adder and O(n²) multiplier gate complexity plus a quantum Strassen variant for potential ML acceleration.
-
Sample efficient graph classification using binary Gaussian boson sampling
Binary-detector Gaussian boson sampling is proposed for sample-efficient graph classification, with an investigation into its connection to the Torontonian matrix function.
-
Mind the gaps: The fraught road to quantum advantage
The authors identify four transitions needed to reach fault-tolerant application-scale quantum computing from current NISQ devices.
-
Mind the gaps: The fraught road to quantum advantage
The paper identifies four key hurdles in the transition from NISQ to FASQ quantum computers and argues that targeting them will accelerate progress toward useful quantum advantage.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.