按年被提到
20182018 · 4 次2026
物理与量子›量子计算·arXiv:1807.04271 · cs.IR

A quantum-inspired classical algorithm for recommendation systems

Ewin Tang · 2018
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 5 人首次 2018-07-14 · 最近 2019-09-29
5不同的人
2活跃月份
3讨论串
376被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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 条,统计用全部提及
评论fossuser · 2018-07

“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”

Teenager Finds Classical Alternative to Quantum Recommendation Algorithm原评论 ↗
评论tsucres · 2018-07

“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…”

Teenager Finds Classical Alternative to Quantum Recommendation Algorithm原评论 ↗
评论joe_the_user · 2018-07

“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…”

Teenager Finds Classical Alternative to Quantum Recommendation Algorithm原评论 ↗
评论noname120 · 2019-09

“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…”

Proof emerges that a quantum computer can outperform a classical one原评论 ↗
被提交为 story · 1 次