A quantum algorithm of K-means toward practical use

Clustering problems in image recognition are recurrent in unsupervised machine learning. The K-means algorithm is a simple and popular algorithm for solving the clustering problem. However, for example, the calculation of the distance between the cluster center and data is time-consuming in the centroid calculation of the K-means algorithm, in particular, for large data sizes. In the present paper, we investigate the possibility of quantum computation to speedup K-means algorithm for large data sizes. We describe a quantum-enhanced K-means algorithm from which centroid calculations are removed. For mean and distance calculations of vector data, we propose a quantum subroutine based on quantum entanglement with a potential speedup to make the speed of the proposed subroutine comparable to its classical counterpart. The proposed K-means algorithm is evaluated on three datasets: synthetic, Iris, and image datasets. The numerical experimental results show that the clustering performance of the proposed algorithm is comparable to that of the classical K-means algorithm.