Hybrid Quantum-Classical Framework for Clustering: a Comprehensive Approach with QMeans

EasyChair Preprint 12862

Abstract

The Kmeans algorithm is a cornerstone in unsupervised learning for clustering, with a temporal complexity of O(iknm), where i represents the number of iterations, k the number of clusters, n the number of points, and m the dimensionality of the observation space. The quantum-inspired variant, QMeans, was introduced to address these limitations, albeit primarily on a theoretical front. This chapter bridges this gap by elucidating and implementing Q-means within a hybrid quantum-classical framework. Initially, a comprehensive overview of Kmeans and d-Kmeans clustering models is provided. Subsequently, the paper covers quantum distance computation, quantum minimum finding in a list, and the quantum version of the Kmeans++ initialization method, QMeans++, along with their respective mathematical formulations, circuit designs, and implementations with Qiskit. Finally, these elements are assembled to formulate the QMeans algorithm.

Keyphrases: Clustering, Q-means, Quantum Machine Learning

@booklet{EasyChair:12862,
  author    = {Antonin Lefevre},
  title     = {Hybrid Quantum-Classical Framework for Clustering: a Comprehensive Approach with QMeans},
  howpublished = {EasyChair Preprint 12862},
  year      = {EasyChair, 2024}}