E. Tang, “A quantum-inspired classical algorithm for recommendation systems,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Jun. 2019, pp. 217–228. doi: 10.1145/3313276.3316310.\
“Introduction | IBM Quantum Learning,” IBM Quantum Learning, 2021. https://quantum.cloud.ibm.com/learning/en/courses/quantum-machine-learning/introduction (accessed Feb. 20, 2026).
Paper Summary: Classical Analogue to Quantum Recommendation Systems
Author: Ewin Tang
Key Finding:
The Kerenidis and Prakash quantum algorithm does not provide an exponential speedup over classical algorithms.
Algorithm Performance
- New Runtime:
O(poly(k) log(mn)). - Status: Only polynomially slower than the quantum version.
- Previous Classical: Ran in time linear in m and n.
The “Core Insight”
The algorithm uses $l^{2}$-norm sampling distributions to play the role typically reserved for quantum superpositions.
Classical Sampling ↔ Quantum State