推荐系统基于用户偏好数据向用户推荐产品,通常通过解决秩为 k 的 m×n 矩阵问题进行建模。我们给出第一个经典算法,可以在 O(poly(k)polylog(m,n))的时间内产生推荐内容,这是对之前以 m 和 n 线性时间运行的算法的指数级改进。我们的策略受到 Kerenidis 和 Prakash 的量子算法的启发:与量子算法一样,我们只是从用户的偏好中寻找一个随机样本,而不是重建用户的完整偏好列表。我们的算法根据输入矩阵的自然采样假设,在与 m 和 n 无关的时间内从输入矩阵的低秩近似中对高权重元素进行采样。因此,我们证明了 Kerenidis 和 Prakash 的量子机器学习(QML)算法(它是 QML 中可证明指数加速的最强候算法之一)实际上并不会给经典算法带来指数级的加速。