传统的K-means 算法属于无监督机器学习算法的一员。该算法将无标记的训练向量集下的数据分为K类。在每次迭代中将训练向量重新分配至最近的质心，并对属于当前簇的向量求平均值计算出新的质心。使用Lloyds 版本的经典算法的时间复杂度O（N，M）线性依赖于大量特征N 和大量训练样例M。K-means 算法最耗费资源的步骤是计算向量间的距离，所以需要通过使用量子计算机检索距离来获得加速。量子K-means 算法可为非常高的维度的训练向量提供指数级的加速。
K均值聚类最简单的量子版本的计算方式是，计算中心并将向量分配给最近的中心，就像经典的版本一样，使用Grover 搜索来寻找最近的中心【88】。由于每一步中都要对每个向量进行测试，故复杂度为O（N log（Nd）。
如果允许输出结果为量子格式，复杂度可以进一步改进。该算法为每个N 输出进行聚类，再通过对结果进行量子叠加，消除了每个算法的复杂度至少为O（N）这个约束。输出为量子态结果【89】：
其状态断层显示为经典的聚类结构。如果用绝热（adiabatic）定理，构造精度为∈，其状态的复杂度为O（∈-1Klog（KNd））。如果绝热间隙是恒定的，在数据聚类效果良好的情况下，复杂度会更低，具体计算如：O（∈-1Klog（KNd））。
为了构造公式10.1 中的状态，首先选择带有ic标记的K 向量作为初始状态。执行第一步，即通过绝热定理将其余的向量分配到这些集群中。使用状态公式10.2来计算状态。
重复D 次，就为新状态∣ψ2>创造了D 个副本。在随后的迭代中重复这个集群分配步骤，最终收敛于等式10.1 中的叠加（叠加态）∣χ>。
量子K-means 算法(www.xing528.com)
输入：∣cj>∣j>、Hb=1-∣Φ><Φ∣
输出：∣χ>
步1 if 允许输出结果为量子格式。
步2 for 每个N 输出：对向量计算中心并将向量分配给（使用Grover 搜索来寻找）最近的中心，并输出量子态：∣χ>=（1/ N）Σj∣cj>∣j>=（1/ N）ΣcΣj∈c∣cj>∣j>
步4 计算初始聚类结果：
步6 repeat2-6 步D 次：收敛于叠加态∣χ>
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
