A quantum-inspired classical algorithm for recommendation systems

By Ewin Tang. Electron. Colloquium Comput. Complex., 2018

481 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/6804cfe98379f00d9fe304babc66677114201d82

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Potential of quantum computing for drug discovery (2018, background): “However, we note that such claims of quantum advantage are not without caveats [11, 151, 152], especially in light of recent works [153–155] showing classical algorithms with comparable performance. networks for classiﬁcation tasks [123].”
Quantum Computing in the NISQ era and beyond (2018, methodology): “3Note added: After this paper was submitted, Tang [45] exhibited a “quantum-inspired” classical algorithm which returns a high-value recommendation in runtime O(poly(k)polylog(mn)); thus the quantum algorithm proposed in [44] does not in fact achieve an exponential speedup compared to the best class”
Challenges and opportunities in quantum machine learning (2022, background): “Such a sample complexity advantage can be proven rigorously without the possibility of being dequantized [12, 65, 117] in the future, i.e., it is impossible to ﬁnd improved classical algorithms such that there is no exponential advantage.”
Entanglement Induced Barren Plateaus (2020, background): “[9] Ewin Tang.”