A quantum algorithm of K-means toward practical use

Zhihao Wu, Tingting Song, Yanbing Zhang

Min Hou, Shibin Zhang, Jinyue Xia

Bach Nhat Hoang, Dang Tien Sy, Doan Trung Thanh +1 more

In the big data era, traditional machine learning algorithms like K-means face computational challenges in processing large, high-dimensional datasets, particularly for underwater acoustic signal classification. This study investigates the application of the quantum clustering algorithm Q-means, a quantum-enhanced variant of K-means, to real passive sonar datasets. The purpose is to evaluate Q-means' effectiveness in classifying propeller-driven ship signals under noisy conditions, leveraging quantum principles such as superposition and entanglement for exponential speedup. The research extends classical K-means to δ-k-means for robustness, implementing quantum subroutines including distance estimation, cluster assignment, and state tomography. Preprocessed features from power spectral density analysis of real datasets (from prior studies on varying ship speeds) are used as input to avoid issues with raw time-series data, such as high dimensionality and sensitivity to shifts. Simulations on 15,000 passive sonar samples demonstrate that Q-means achieves clustering quality comparable to K-means, with clear separation of three clusters and accurate centroids, while reducing complexity from O(n) to O(polylog(n)). This validates Q-means as a promising tool for large-scale, noisy acoustic data in national security applications, bridging quantum theory with practical machine learning.

Kornélia Sára Szatmáry, Prof Miklós Kozlovszky

International literature suggests that quantum computers hold the potential for exponential speedup over classical computers, particularly for certain types of optimization problems. However, the practical application of quantum k-means is currently limited by the capabilities of available quantum hardware. As quantum technology improves and more efficient algorithms are developed, quantum k-means may offer advantages for larger datasets and high-dimensional data. This essay presents a comparative study of the k-means clustering algorithm implemented in two runtime environments, C# and Qiskit, with a focus on investigating the potential existence of quantum supremacy for a defined problem. The experiment involves randomly generated data and data tables of different sizes and dimensions. The classical approach utilizes a brute-force enumeration method, while the quantum approach employs a quadratic programming algorithm on a quantum computer using Qiskit. Results show that for small problem sizes, the classical brute-force approach exhibits superior runtime performance compared to the quantum approach. However, the study highlights the challenges in achieving quantum supremacy, as the performance of quantum computers is highly dependent on machine capabilities and qubit numbers.

Usha Rani J, Ganesan Anandhi

Ó, Francisco Loureiro Rosa Ramos do

Classical machine learning algorithms are increasingly challenged by the growing complexity of datasets, motivating the exploration of quantum computing as a potential solution. However, current literature lacks comprehensive empirical analyses directly benchmarking classical algorithms against quantum-assisted counterparts for small but high-dimensional standardized datasets. This research aims to address this gap by comparing the performance of the k-means clustering algorithm on classical and hybrid quantum-classical computing platforms. Using a small dataset, we assess computational speed, clustering accuracy, and scalability. Our findings reveal that while hybrid quantum implementations offer theoretical benefits, in practice they incur significantly higher computational overhead and reduced clustering accuracy due to current technological constraints. These insights highlight the critical need for improved quantum hardware and algorithms, guiding future research directions in quantum-enhanced machine learning.