  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 has been no quantum-tailored coreset technique
which is designed to boost the accuracy of quantum algorithms. In this work, we
propose solving the k-means clustering problem with the variational quantum
eigensolver (VQE) and a customised coreset method, the Contour coreset, which
has been formulated with specific focus on quantum algorithms. Extensive
simulations with synthetic and real-life data demonstrated that our VQE+Contour
Coreset approach outperforms existing QAOA+Coreset k-means clustering
approaches with higher accuracy and lower standard deviation. Our work has
shown that quantum tailored coreset techniques has the potential to
significantly boost the performance of quantum algorithms when compared to
using generic off-the-shelf coreset techniques.
