量子K最近邻算法

为减少经典K最近邻算法的时间复杂度,提出了量子K最近邻算法(QKNN)。介绍了QKNN算法的构造步骤,然后为减少量子计数子程序的运行时间,进一步将固定的K值修改为可变的k,形成改进的k可变的量子最近邻算法(QkvNN)。为弥补由于最近邻个数K变化带来的分类错误率上升的影响,在Boosting算法框架下,用三个由QkvNN算法训练的弱分类器,去构造了一个强分类器,从而提高单独运行QkvNN的分类精度。在此算法中,由于利用了量子计算的强大能力,使得经典K最近邻算法的时间复杂度从O(N)减小为O(N)。

Quantum K nearest neighbor algorithm

A novel quantum learning method is presented,which combines quantum computation with classical K-nearest-neighbor,called quantum K-nearest-neighbor.Its steps are introduced in detail.Further,in order to save to running time of quantum counting subroutine,the fired K is revised to the changeable K.Under the framework of Boosting algorithm,a strong classifier is build,which consists of three weak classifiers,each trained by the quantum k-varying nearest neighbor,to improve the performance of classification.In this algorithm,the time complexity of classical K-nearest-neighbor algorithm is reduced from O(N) to O(N) by means of the power of quantum algorithms.