qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices * Equal Contribution. The manuscript has been accepted for publication at IEEE BigData 2025.

Pedro Chumpitaz-Flores *, My Duong *, Ying Mao, Kaixun Hua · 2025

Read qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices * Equal Contribution. The manuscript has been accepted for publication at IEEE BigData 2025. by Pedro Chumpitaz-Flores *, My Duong *, Ying Mao, Kaixun Hua (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22540.txt.

Introduction

Clustering data on today's small quantum machines is limited by few qubits and hard data loading. Pedro Chumpitaz-Flores, My Duong, Ying Mao, and Kaixun Hua present qc-kmeans in 2025, a hybrid method that compresses a dataset before quantum steps begin.

A fixed size sketch, built from Fourier style features, summarizes the data without growing with sample count. Small quantum circuits then choose centers group by group, and a refinement step keeps the best result so far. Simulations used at most nine qubits on test data and handled nine real datasets. Quality stayed competitive, even under models of real device noise.

Catalog record

CREATORPedro Chumpitaz-Flores *, My Duong *, Ying Mao, Kaixun Hua
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-22540

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices * Equal Contribution. The manuscript has been accepted for publication at IEEE BigData 2025. Pedro Chumpitaz-Flores *, My Duong *, Ying Mao, Kaixun Hua Abstract Clustering on NISQ hardware is constrained by data loading and limited qubits. We present qc-kmeans , a hybrid compressive k 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 ) O(\varepsilon^{2}) for B , S = Θ ⁡ ( ε − 2 ) B,S=\Theta(\varepsilon^{-2}) , and the peak-qubit requirement q peak = max ⁡ { D , ⌈ log 2 ⁡ B ⌉ + 1 } 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 p{=}1 ), the method ran with ≤ 9 \leq 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 × 10 5 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. I Introduction Unsupervised k -means is a standard method for partitioning datasets into k cohesive groups, widely used in data mining, knowledge discovery, and pattern recognition [ 1 , 2 , 3 ] . In its standard Lloyd iteration, each step computes distances from all N points to k centroids in d dimensions, yielding a per-iteration cost of O(kNd) [ 4 , 3 ] . While many improvements have been proposed, clustering large, high-dimensional, and multi-cluster datasets remains computationally demanding, motivating the search for new algorithmic paradigms. Quantum computing has attracted interest for addressing clustering challenges [ 5 , 6 ] . Pure and hybrid approaches leverage quantum superposition and amplitude-estimation ideas to parallelize key subroutines and accelerate linear-algebraic steps such as eigenvalue estimation [ 7 , 8 , 9 ] . However, several proposals assume advanced data access (e.g., QPU, QRAM) and deep circuits suited to fault-tolerant regimes [ 10 , 6 , 11 , 12 ] . In practice, QRAM is unrealized on current hardware [ 13 ] , and today’s Noisy Intermediate-Scale Quantum (NISQ) devices have limited qubits and suffer decoherence and gate errors [ 12 ] . Moreover, while amplitude estimation can offer quadratic speedups for mean or distance estimation, standard variants require circuit depths that strain NISQ hardware, motivating low-depth or iterative alternatives [ 7 , 14 , 15 ] . These constraints have spurred interest in hybrid approaches that pair small quantum processors with classical data reduction to keep the quantum footprint small [ 16 , 17 , 18 ] . Our Contributions: We propose a hybrid Quantum Compressive k -Means (qc-kmeans) algorithm for scalable quantum clustering on NISQ hardware. Qc-kmeans compresses the dataset into a compact sketch and runs quantum subroutines only on this reduced representation, trading approximation for practicality and reducing memory and qubit requirements. The method isolates a small quantum subproblem; comparisons of SSE and runtime are restricted to quantum baselines and small-QUBO references , with classical baselines included only for context and without claims of superiority. II Related Works K -means clustering has been an early target for quantum algorithmic design. [ 10 ] first developed the q-means algorithm, which mirrors the classical k -means but uses quantum linear-algebra subroutines to accelerate centroid updates and distance computations. The q-means algorithm encodes data points in quantum amplitude vectors, typically assuming they reside in QRAM for efficient access. Under these conditions, q-means can find approximate cluster centroids with high probability. Q-means and its improved variants [ 19 , 6 ] run in polylogarithmic time per iteration, providing an exponential speedup over the O(kNd) classical cost. As discussed in § I , these speedups rely on assumptions such as QRAM and deeper circuits that are challenging for current NISQ devices. Given the gap between algorithmic theory and current quantum hardware resources, researchers have explored hybrid quantum–classical algorithms for clustering that better suit NISQ devices. [ 20 ] found approximate solutions to a weighted max- k -cut problem using the Quantum Approximate Optimization Algorithm (QAOA). [ 21 ] investigated a quantum k -means implementation on NISQ-era hardware using small circuits (based on the SWAP test) to estimate distances and identify noise-induced pitfalls, proposing a modified, parallelized quantum k -means that reduces depth by computing multiple distance estimations concurrently and reporting performance improvements on an energy grid dataset. Similarly, [ 22 ] introduced hybrid quantum clustering algorithms where the key speedup comes from computing distances from a data point to all k centroids simultaneously via superposition, and showed runtime benefits for sufficiently large datasets while maintaining clustering quality. Orthogonal to the quantum developments, the classical ML community has tackled clustering at scale using data summarization. Classical compressive k -means (CKM) , introduced by Keriven [ 23 ] , compresses the entire dataset into a fixed-size sketch via random nonlinear features, enabling clustering cost independent of N . Hybrid algorithms like [ 16 , 17 , 18 ] try creating classical coresets from the original data enables quantum clustering on hardware by compressing large datasets into small weighted sets suitable for variational algorithms, though they only address up to 2-means or 3-means clustering. [ 24 ] developed a quantum algorithm to construct coresets for clustering in \tilde{O}(\sqrt{Nk}\,d^{3/2}) time, achieving a quadratic speedup over classical methods for large N . Despite these advances, practical scalability still remains an open challenge. Fully quantum algorithms offer remarkable asymptotic speedups but are not deployable on present devices [ 18 ] . Hybrid algorithms have demonstrated only small-scale successes, limited to datasets of a few hundred points by hardware constraints. Compressive techniques reduce data size, but combining them with quantum speedups has not been well-studied. The current work addresses this gap by proposing and analyzing qc-kmeans, which unites quantum algorithms, hybrid parallelism, and compressive learning to push the boundary of quantum clustering on NISQ hardware. III Quantum Compressive k -Means via Fourier Features III-A Classical k -Means Given a dataset X=\{x_{1},\ldots,x_{N}\}\subset\mathbb{R}^{d} with N samples and d dimensions, the k -Means task assigns points to k clusters with centroids \{\mu_{j}\}_{j=1}^{k} that minimize the within-cluster sum of squares: \mathrm{WCSS}\;=\;\sum_{j=1}^{k}\sum_{x_{i}\in C_{j}}\bigl\|x_{i}-\mu_{j}\bigr\|_{2}^{2}, where \mu_{j} is the mean of points assigned to cluster j . Lloyd’s heuristic [ 4 ] has per-iteration cost O(kNd) , which becomes prohibitively expensive as the dataset grows in size and dimensionality. To address this scalability bottleneck, random projections can be applied to lower computational cost while approximately preserving clustering structure. III-B Quantum compressive k -Means Given X=\{x_{1},\ldots,x_{N}\}\subset\mathbb{R}^{d} , we construct a matrix of random frequencies as W=\begin{bmatrix}w_{11}&w_{12}&\cdots&w_{1d}\\ w_{21}&w_{22}&\cdots&w_{2d}\\ \vdots&\vdots&\ddots&\vdots\\ w_{m1}&w_{m2}&\cdots&w_{md}\end{bmatrix}\in\mathbb{R}^{m\times d}. Each row vector w_{j}=(w_{j1},\ldots,w_{jd})^{\top} for j\in\{1,\ldots,m\} is independently sampled from the multivariate normal distribution \mathcal{N}(0,\sigma^{2}I_{d}) . We then define the complex Fourier feature map \phi(x)\;=\;\exp\big(\mathbf{i}\,Wx\big)\in\mathbb{C}^{m}, where the exponential is applied elementwise for all x\in\mathbb{R}^{d} and where \mathbf{i}^{2}=-1 . The dataset is summarized by the compressed feature mean:

Read the complete text