Quantum K nearest neighbor algorithm
Jiang Jing-ping · Systems engineering and electronics · 2008
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.