Quantum version of the k-NN classifier based on a quantum sorting algorithm
This work addresses the challenge of implementing machine learning algorithms on quantum computers, but it is incremental as it builds on prior quantum k-NN methods.
The authors tackled the problem of developing a quantum version of the k-NN classifier by introducing a quantum sorting algorithm with adaptable memory and circuit depth, resulting in a quantum k-NN that matches classical performance and outperforms an existing quantum version.
In this work we introduce a quantum sorting algorithm with adaptable requirements of memory and circuit depth, and then use it to develop a new quantum version of the classical machine learning algorithm known as k-nearest neighbors (k-NN). Both the efficiency and performance of this new quantum version of the k-NN algorithm are compared to those of the classical k-NN and another quantum version proposed by Schuld et al. \cite{Int13}. Results show that the efficiency of both quantum algorithms is similar to each other and superior to that of the classical algorithm. On the other hand, the performance of our proposed quantum k-NN algorithm is superior to the one proposed by Schuld et al. and similar to that of the classical k-NN.