Clustering by Contour Coreset and Variational Quantum Eigensolver

Abstract

Recent work has proposed solving the k‐means clustering problem on quantum computers via the Quantum Approximate Optimization Algorithm (QAOA) and coreset techniques. Although the current method demonstrates the possibility of quantum k‐means clustering, it does not ensure high accuracy and consistency across a wide range of datasets. The existing coreset techniques are designed for classical algorithms, and there is no quantum‐tailored coreset technique designed to boost the accuracy of quantum algorithms. This study proposes solving the k‐means clustering problem with the variational quantum eigensolver (VQE) and a customized coreset method, the Contour coreset, which is formulated with a specific focus on quantum algorithms. Extensive simulations with synthetic and real‐life data demonstrated that the VQE+Contour Coreset approach outperforms existing QAOA+Coreset k‐means clustering approaches with higher accuracy and lower standard deviation. This research demonstrates that quantum‐tailored coreset techniques can remarkably boost the performance of quantum algorithms compared to generic off‐the‐shelf coreset techniques.