k-Means 的量子逼近方案
原文中文，约400字，阅读约需1分钟。发表于：。我们给出了在 QRAM 模型中，对于经典 k - 均值聚类问题的量子逼近方案（即对于每个 ε>0，具有（1+ε）- 逼近），其运行时间只有数据点数量的对数多项式依赖。具体而言，对于存储在 QRAM 数据结构中的包含 N 个在 R^d 中的点的数据集 V，我们的量子算法以时间 Γ(O)((2^(Γ(O)(k/ε)))η^2d) 运行，并且以高概率输出一个包含 k 个中心的集合 C，其中...
本文介绍了QRAM模型中解决k-均值聚类问题的量子逼近方案，运行时间依赖于数据点数量的对数多项式，能够高概率输出一个包含k个中心的集合，成本不超过最优解的（1+ε）倍。这是第一个具有对k-均值问题具有（1+ε）可证逼近保证且具有多项式对数运行时间的量子算法。与先前的无监督学习方法不同，该算法不需要量子线性代数子程序，运行时间与参数无关。
