计算机应用

作者：钟静, 林晨, 盛志伟, 张仕斌

单位：成都信息工程大学 网络空间安全学院，成都 610225

关键词：量子机器学习,量子算法,量子K-Means算法,汉明距离,Grover搜索算法

基金：国家自然科学基金资助项目(62076042)

K-Means算法在处理大规模异构数据时，通常使用欧氏距离来衡量数据点之间的相似度，然而这样存在效率低下以及计算复杂性过高的问题。受到汉明距离在处理数据相似性计算上存在显著优势的启发，提出一种基于汉明距离的量子K-Means（QKMH）算法来计算相似度。首先，将数据制备成量子态，并使用量子汉明距离计算待聚类点和K个聚类中心之间的相似度；然后，改进了Grover最小值搜索算法查找距离待聚类点最近的聚类中心；最后，循环以上步骤，直到达到规定迭代次数或者聚类中心不再改变。基于量子模拟计算框架QisKit，将提出的算法在MNIST手写数字数据集上进行了验证并与传统和改进的多种方法进行了对比，实验结果表明，QKMH算法的F1值相较于基于曼哈顿距离的量子K-Means算法提高了10个百分点，相较于最新优化的基于欧氏距离的量子K-Means算法提高了4.6个百分点；同时经计算，QKMH算法时间复杂度比上述对比算法更低。

来源：2023年第8期

《计算机应用》期刊编辑部

查看计算机应用杂志2023年第8期