改进的量子K最近邻算法

An Improved Quantum Algorithm for KNN Based on Hamming Distance

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

In this paper,we propose an improved quantum algorithm of KNN for Hamming distance based on Grover algorithm.To solve the K-nearest neighbor problem of test sample,at first,we calculate the Hamming distance between samples using the quantum computation.Then,the Grover algorithm is used to search K-nearest neighbors.Finally,the test sample’s category is determined by the category with the highest frequency among K-nearest neighbors.The runtime of our algorithm is O(√M),with quadratic acceleration compared with the classic algorithm.