结合K-means算法和角编码技术, 提出了一种无需量子随机存储 (QRAM) 的量子K-means算法。该算法利用量子操作的并行性, 仅需对数数量的时间复杂度就能完成数据的加载; 并且通过对输入数据进行参数预处理操作,确定数据分量的参数阈值, 解决了样本不同特征尺度差异的问题。该算法由编码数据、相似度度量、量子最小值搜索和质心迭代更新四个主要步骤组成, 细致描述了这些步骤所涉及的算子和线路构建, 并对关键线路进行了仿真模拟。实验结果和经典预测结果一致, 验证了所提量子K-means算法的可靠性。此外, 理论分析表明所提出算法相比于经典算法在运行时间上有平方级加速。

A quantum K-means algorithm without quantum random access memory (QRAM) is proposed by combining K-means algorithm and angle encoding technology. This algorithm makes use of parallel quantum operations and can complete data loading with only logarithmic time complexity. And by pre-processing the input data, the parameter threshold of the data components is determined, so the problem of different characteristic scales of samples can be solved according to the algorithm. The main body of the algorithm consists of four main steps: coding data, similarity measurement, quantum minimum search and centroid iterative update. The operators and circuit construction involved in these steps are described in detail. Numerical experiments based on the proposed circuit show that the results of the proposed algorithm are consistent with the classical prediction results, verifying the reliability of the quantum K-means algorithm combined with parameters. In addition, theoretical analysis shows that the proposed algorithm has square acceleration in running time compared with the classical algorithms.