CoChat
Sign Up
Cited by 360Quantum Computing Algorithms and ArchitectureRecommender Systems and TechniquesComplexity and Algorithms in Graphs

A quantum-inspired classical algorithm for recommendation systems

Open access
Tang, Ewin·2019·Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
DOI 10.1145/3313276.3316310
Open this paper in CoChat — free accountOpen PDF

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 × 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 claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3313276.3316310

Cites

5 of 5 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Dequantization attempts have eliminated examples of speed-up for some problems in linear algebra.

    “Such attempts have eliminated examples of speed-up for some problems in linear algebra.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Tang, 2019

    The Abstract (p. 1) says Tang’s classical algorithm shows that a quantum recommendation-system algorithm does not provide an exponential speedup; §1.1 (p. 2) describes the underlying task as sampling from a low-rank matrix approximation. This supports one linear-algebra-related example, but the paper does not establish that dequantization eliminated speedups for multiple problems, nor does it rule out smaller speedups. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • Dequantized machine learning algorithms have been developed for recommendation systems, principal component analysis and supervised clustering, stochastic regression, and low-rank linear systems.

    “So far, dequantized machine learning algorithms have been developed for recommendation systems (Tang, 2019), principal component analysis and supervised clustering (Tang, 2018), stochastic regression (Gilyén et al. , 2018) and low-rank linear systems (Arrazola et al. , 2019; Chia et al. , 2018).”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Tang, 2019

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 19

  1. [AFK + 01] Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry, and Jared Saia. Spectral analysis of data. In Symposium on Theory of Computing . ACM, 2001.
  2. [AM07] Dimitris Achlioptas and Frank McSherry. Fast computation of low-rank matrix approximations. Journal of the ACM (JACM) , 54(2):9, 2007.
  3. [APSPT05] Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Mark Tuttle. Improved recommendation systems. In Symposium on Discrete Algorithms , 2005.
  4. [BJ99] Nader H. Bshouty and Jeffrey C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM J. Comput. , 28(3):1136-1153, 1999.
  5. [BK07] Robert M Bell and Yehuda Koren. Lessons from the Netflix prize challenge. ACM SIGKDD Explorations Newsletter , 9(2):75-79, 2007.
  6. [DKM06] P. Drineas, R. Kannan, and M. Mahoney. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM Journal on Computing , 36(1):132-157, 2006.
  7. [DKR02] Petros Drineas, Iordanis Kerenidis, and Prabhakar Raghavan. Competitive recommendation systems. In Symposium on Theory of Computing . ACM, 2002.
  8. [DMM08] P. Drineas, M. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix decompositions. SIAM Journal on Matrix Analysis and Applications , 30(2):844-881, 2008.
  9. [DV06] Amit Deshpande and Santosh Vempala. Adaptive sampling and fast low-rank matrix approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pages 292-303. Springer, 2006.
  10. [FKV04] Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast Monte-Carlo algorithms for finding low-rank approximations. Journal of the ACM (JACM) , 51(6):1025-1041, 2004.
  11. [GSLW18] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. arXiv , 2018.
  12. [HKS11] Elad Hazan, Tomer Koren, and Nati Srebro. Beating SGD: Learning SVMs in sublinear time. In Neural Information Processing Systems , 2011.
  13. [KBV09] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer , 42(8), 2009.
  14. [KP17a] Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. arXiv , 2017.
  15. [KRRT01] Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. Recommendation systems: a probabilistic analysis. Journal of Computer and System Sciences , 63(1):42 - 61, 2001.
  16. [KS08] Jon Kleinberg and Mark Sandler. Using mixture models for collaborative filtering. Journal of Computer and System Sciences , 74(1):49-69, 2008.
  17. [LMR13] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv , 2013.
  18. [Rec11] Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research , 12:3413-3430, 2011.
  19. [SWZ16] Zhao Song, David P. Woodruff, and Huan Zhang. Sublinear time orthogonal tensor decomposition. In Neural Information Processing Systems , 2016.

Cited by

Sorted by citations

Authors
Tang, E.
Affiliations
The University of Texas at Austin (US)
Corresponding author
Tang, Ewin
Venue
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
Publisher
ACM
Published
2019-06-23
Pages
217-228
DOI
10.1145/3313276.3316310
OpenAlex
W2880299821
Cited by
360
References
5
Citations by year
2026: 48 · 2025: 35 · 2024: 36 · 2023: 47 · 2022: 48 · 2021: 52 · 2020: 67 · 2019: 20 · 2018: 6 · 2017: 1
FWCI
17.89
Type
conference paper
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
  • ACM Symposium on Theory of Computing (STOC) (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Information Systems › Recommender Systems and Techniques
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
recommender systems, quantum machine learning, quantum advantage

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review