Research On Quantum K Nearest Neighbor Algorithm

With the rapid development of the quantum computation area and machine learning algorithms, many quantum machine learning algorithms have been designed and implemented in the past decade. By taking advantages of basic concepts, theory and method in quantum computation, researchers have achieved fruitful results in improving the execution efficiency and accuracy of different machine learning algorithms. Besides the significant achievement in theoretical research, the results of real-world physical implementation of quantum machine learning algorithms is also inspiring. Some physicist have successfully completed the physical realization of these algorithms. The theoretical results as well as the meaning physical realizations of the quantum machine learning method will be good references for further study in this area.In this paper, we firstly introduce basic theory of quantum algorithms, including qubit, quantum gates and the parallelism of quantum computing. Then two classic quantum algorithms are reviewed:Grover Search Algorithm and the Phase Estimation Algorithm. After that, the classic k-nearest neighbor machine learning algorithm is explored. We focus on three aspects of the k-nearest neighbor:measure of similarity, searching method of the closest k points, and advantages and disadvantages of this algorithm.Next, A novel quantum K-nearest neighbor algorithm is designed to reduce the amount of calculations for K-nearest neighbors method. Quantum superposition and quantum parallel computing features are utilized to accelerate the considered algorithm. We have proved that the proposed algorithm can bring secondary acceleration of k value, and run faster than other existing algorithms for solving the same problem.