量子K-近邻算法

Quantum K-nearest neighbor algorithm

为了提高经典K-近邻算法的效率,引入量子计算理论,将Grover算法中的Oracle算子以及相位估计算法嵌入经典K-近邻算法,提出一种量子K-近邻算法.该算法首先将样本点和待分类点的向量信息制备成量子叠加态,采用可逆的量子控制交换门并行计算待分类点和样本点的相似度,然后利用相位估计算法将相似度信息存储到量子比特中,最后使用Grover算法一次性搜索出最相似的k个点.对嵌入的量子计算部分的理论分析结果表明,量子K-近邻算法可以明显降低经典计算复杂度,且提出的算法在已有算法计算复杂度O(RkM)的基础上,再次带来了k值的二次加速O(RkM),其中R为Oracle算子的执行次数,M为样本全局个数.

A novel quantum K-nearest neighbor algorithm is designed to improve the efficiency by introducing the theory of quantum computation and embedding the Oracle operator of Grover algo- rithm and the phase estimation algorithm in classic K-nearest neighbor algorithm. In the proposed al- gorithm, the vector information of sample points and to-be-classified points is prepared to be quan- tum superposition, and quantum reversible c-swap gate is used to parallel compute the similarity. Then the similarity is stored in qubit by using quantum phase estimation, and the k most similar points are found once by the Grover algorithm. Through theoretical analysis of the embedded quan- tum computing, the results show that the quantum K-nearest neighbor algorithm can significantly re- duce the computational complexity of classical algorithms and the proposed algorithm runs faster than other existing algorithms O（Rk√M） with the k value of the second acceleration O（Rk√M） for solving the same problem. Wherein R represents Oracle execution times and M is global number of samples.