基于参数化角编码的量子K-means算法  

Quantum K-means algorithm based on parameterized angle enc oding

作　　者：冯微军 郭躬德[1] 林崧[1] FENG Weijun;GUO Gongde;L IN Song(College of Computer and Cyber Security,Fuji an Normal University,Fuzhou 350007,China)

机构地区：[1]福建师范大学计算机与网络空间安全学院,福建福州350007

出　　处：《量子电子学报》2024年第1期113-124,共12页Chinese Journal of Quantum Electronics

基　　金：国家自然科学基金(62171131,61976053,61772134);福建省高等学校新世纪优秀人才支持计划;福建省自然科学基金(2018J01776)。

摘　　要：结合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.

关 键 词：量子光学 量子K-means算法 角编码 量子相位估计 多量子比特交换测试 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]