摘要：本文利用量子Grover搜索技术,,提出了一种改进的基于汉明距离的量子欠近邻算法。在算法中,为了解决了求解未知类样本的欠近邻问题,首先利用量子计算得到样本之间的汉明距离,然后利用量子Grover搜索算法,搜索出最近邻,最后找到未分类样本的欠最近邻样本中出现频率最大的类别。本算法的时间复杂度为O(√M),与经典算法相比有二次加速。

关键词：量子计算 量子机器学习 量子k最近邻算法 k最近邻算法 

单位：福建师范大学数学与信息学院; 福州350117