“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”
A quantum-inspired classical algorithm for recommendation systems
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.
候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“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 the probability of failure. So the classical algorithm would give a "sufficien…”
“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 based on simplifying assumptions. IE, sure, the FINAL, SOLVED problem is as Aar…”
“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 problems that can be solved by a classical computer (deterministic Turing machin…”
- A quantum-inspired classical algorithm for recommendation systems ↗nabla9 · 2018-07-14 · 1 分