A quantum-inspired classical algorithm for recommendation systems

E. Tang · 2019 · STOC

| 编号 QR052 | 主题 算法与批判 | 链接 arXiv:1807.04271 |

摘要

摘要保留原文（英文）

摘要取自 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-\mathrm{norm}$ sampling operations, outputs an ℓ2-norm sample from a rank-k approximation of that matrix in time $O(\mathrm{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$ .

本站词条在引用该文献时，会以 wikilink（sources/QR052）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。