Implementing quantum k-means clustering algorithm

Abstract

The thesis reviewed a previous quantum approach for k-means clustering, identified its limitations, and proposed a method to address these shortcomings. Additionally, it introduced an algorithm to calculate multiple distances simultaneously, aiming to enhance the efficiency of the quantum k-means clustering program.

Through the thesis studies, the following conclusions were drawn: Firstly, employing quantum computers for computing Euclidean distances, a crucial task in the k-means clustering algorithm, is feasible. The Euclidean distances computed by quantum computers closely approximate those calculated by classical computers. Secondly, the thesis demonstrated the possibility of calculating multiple distances simultaneously in one quantum circuit, thus improving efficiency. Thirdly, the quantum k-means clustering algorithm, which utilizes this quantum circuit for Euclidean distance calculation, performs equally well with classical k-means clustering algorithms in small-scale problems. However, in large-scale problems, the quantum k-means clustering algorithm produces slightly less accurate results.

Regarding quantum advantage, theoretically, quantum computers would exponentially speed up the state preparation process for calculating quantum distance, as it requires only logarithmic qubits to represent the dataset. However, since classical calculation is still needed to compute the distance from the results obtained from the quantum computer, the quantum speedup for the whole task is not significant.