Quantum k-means algorithm based on Manhattan distance

Traditional k-means algorithm measures the Euclidean distance between any two data points, but it is not applicable in many scenarios, such as the path information between two cities, or when there are some obstacles between two data points. To solve the problems, we propose a quantum k-means algorithm based on Manhattan distance (QKMM). The main two steps of the QKMM algorithm are calculating the distance between each training vector and k cluster centroids, and choosing the closest cluster centroid. The quantum circuit is designed, and the time complexity is O(log(Nd) + 2 n root k), where N is number of training vectors, d is number of features for each training vector, n is number of bits for each feature, and k is the number of clustering classes. Different from other quantum k-means algorithms, our algorithm has wide applications and reduces the complexity. Compared with classical k-means algorithm, our algorithm reaches quadratic speedup.