k-Means 的量子逼近方案

本文介绍了QRAM模型中解决k-均值聚类问题的量子逼近方案，运行时间依赖于数据点数量的对数多项式，能够高概率输出一个包含k个中心的集合，成本不超过最优解的（1+ε）倍。这是第一个具有对k-均值问题具有（1+ε）可证逼近保证且具有多项式对数运行时间的量子算法。与先前的无监督学习方法不同，该算法不需要量子线性代数子程序，运行时间与参数无关。