HackerPapers

arXiv:1807.04271cs.IR

A quantum-inspired classical algorithm for recommendation systems

Ewin Tang

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 \times n$ matrix in a data structure supporting certain $\ell^2$-norm sampling operations, outputs an $\ell^2$-norm sample from a rank-$k$ approximation of that matrix in time $O(\text{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 $\ell^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.

arXiv comments
32 pages; revised structure of document, improved runtime, simplified algorithm and notation
Journal reference
DOI
doi:10.1145/3313276.3316310
Subjects
cs.IRInformation Retrieval cs.DSData Structures and Algorithms cs.LGMachine Learning quant-phQuantum Physics

On Hacker News

Linked by 6 identifiable commenters in 6 comments across 3 threads, from Jul 2018 to Nov 2019. Found in 1 HN submission from Jul 2018 to Jul 2018. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Quantum advantage, or a practical demonstration that quantum computers work 1 comment

    • From the article > So far there has been a lot of excitement but also a lot of crushed dreams and backtracking, when solutions giving a quantum boost were later again beaten by classical computers, e.g. Ewin Tang showed this in some cases last summer (check his paper or story in…

      chrispeelView on HNParent context

  2. Proof emerges that a quantum computer can outperform a classical one 1 comment

    • I'd like to take the opportunity to clear a misunderstanding that I've seen in several threads related to quantum computing. ————————————————————————————————————————————————————————— The classes of complexity of interest here are P, NP, BPP, and BQP. — P corresponds to the…

      noname120View on HNParent context

  3. Teenager Finds Classical Alternative to Quantum Recommendation Algorithm 4 comments

    • It's worth noting that the title of the paper does emphasize this: A quantum-inspired classical algorithm for recommendation systems. The abstract does too: https://arxiv.org/abs/1807.04271

      gonehomeView on HNParent context

    • The preprint has no mention of Scott Aaronson as an author though. https://arxiv.org/abs/1807.04271

      denzil_correaView on HNParent context

    • The paper [1] states: > There is a classical algorithm whose output distribution is O(ε)-close in total variation distance to the distribution given by l2-norm sampling from the ith row of a low- rank approximation D of A in query and time complexity [O(poly-func)] where δ is…

      tsucresView on HNParent context

    • Looking at the paper, I think the fact that this is a recommendation algorithm is fairly important. The big thing is that broadly "the recommendation algorithm" is not some single problem in combinatorics. Rather, it a initially ill-posed problem that yields concrete problems…

      joe_the_userView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.