2025/10/26 by Chumpitaz-Flores, Pedro, Duong, My, Mao, Ying +1
#Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2510.22540
Clustering on NISQ hardware is constrained by data loading and limited qubits. We present 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(ε2) for B,S=Θ(ε-2), and the peak-qubit requirement qpeak=max\D,\lceil log2 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 ≤ 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× 105 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.