Quantum K-nearest neighbors classification algorithm based on Mahalanobis distance

Abstract

Mahalanobis distance is a distance measure that takes into account the relationship between features. In this paper, we proposed a quantum K NN classification algorithm based on the Mahalanobis distance, which combines the classical K NN algorithm with quantum computing to solve supervised classification problem in machine learning. Firstly, a quantum sub-algorithm for searching the minimum of disordered data set is utilized to find out K nearest neighbors of the testing sample. Finally, its category can be obtained by counting the categories of K nearest neighbors. Moreover, it is shown that the proposed quantum algorithm has the effect of squared acceleration compared with the classical counterpart.