qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices
This work addresses clustering for quantum computing applications on NISQ devices, but it is incremental as it builds on existing methods with specific optimizations.
The authors tackled the problem of clustering on NISQ hardware by developing qc-kmeans, a hybrid compressive k-means algorithm that uses Fourier-feature sketches and shallow QAOA circuits, achieving competitive sum-of-squared errors in simulations with up to 9 qubits and maintaining constant peak-qubit usage on real datasets.
Clustering on NISQ hardware is constrained by data loading and limited qubits. We present \textbf{qc-kmeans}, a hybrid compressive $k$-means that summarizes a dataset with a constant-size Fourier-feature sketch and selects centroids by solving small per-group QUBOs with shallow QAOA circuits. The QFF sketch estimator is unbiased with mean-squared error $O(\varepsilon^2)$ for $B,S=Θ(\varepsilon^{-2})$, and the peak-qubit requirement $q_{\text{peak}}=\max\{D,\lceil \log_2 B\rceil + 1\}$ does not scale with the number of samples. A refinement step with elitist retention ensures non-increasing surrogate cost. In Qiskit Aer simulations (depth $p{=}1$), the method ran with $\le 9$ qubits on low-dimensional synthetic benchmarks and achieved competitive sum-of-squared errors relative to quantum baselines; runtimes are not directly comparable. On nine real datasets (up to $4.3\times 10^5$ points), the pipeline maintained constant peak-qubit usage in simulation. Under IBM noise models, accuracy was similar to the idealized setting. Overall, qc-kmeans offers a NISQ-oriented formulation with shallow, bounded-width circuits and competitive clustering quality in simulation.