Abstract Prototype-based clustering algorithms such as k-means are sensitive to the selection of initial cluster centroids, with poor initialization leading to slower convergence and suboptimal solutions trapped in local minima. We present Adaptive Quantum Optimized Centroid Initialization (AQOCI), a method that formulates the centroid initialization problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem and solves it using quantum annealing or quantum-inspired solvers. AQOCI extends a prior method (QOCI) by introducing an iterative refinement mechanism inspired by the Gauss-Seidel and Jacobi methods, enabling the recovery of real-valued centroid coordinates from binary solver outputs through adaptive scaling and offset adjustments. We evaluate AQOCI using three solver backends: TABU search, simulated annealing, and D-Wave’s HybridBQM on synthetic Gaussian data with controlled sweeps over cluster separation, cluster count, dimensionality, and sample size, as well as on the MOTIF malware classification dataset, comparing against standard k-means with random initialization and k-means++ initialization. On the MOTIF dataset, AQOCI produces clusterings that are competitive with and, at smaller sample sizes, superior to k-means++, with V-measure improvements of up to 26%. On synthetic data with heavily overlapping clusters, AQOCI–SimAnn outperforms k-means++ in V-measure. On well-separated synthetic data, k-means++ is clearly superior, and AQOCI exhibits a consistent performance plateau attributable to the binary encoding resolution. The dimensionality sweep demonstrates scalability to at least d = 10 without degradation. These results demonstrate that QUBO-based centroid initialization is a viable alternative formulation whose performance advantage is data-structure-dependent, strongest when clusters overlap and sample sizes are small, and whose potential for quantum speedup may be realized as quantum annealing hardware continues to mature.
Abstract Prototype-based clustering algorithms such as k-means are sensitive to the selection of initial cluster centroids, with poor initialization leading to slower convergence and suboptimal solutions trapped in local minima. We present Adaptive Quantum Optimized Centroid Initialization (AQOCI), a method that formulates the centroid initialization problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem and solves it using quantum annealing or quantum-inspired solvers. AQOCI extends a prior method (QOCI) by introducing an iterative refinement mechanism inspired by the Gauss-Seidel and Jacobi methods, enabling the recovery of real-valued centroid coordinates from binary solver outputs through adaptive scaling and offset adjustments. We evaluate AQOCI using three solver backends: TABU search, simulated annealing, and D-Wave’s HybridBQM on synthetic Gaussian data with controlled sweeps over cluster separation, cluster count, dimensionality, and sample size, as well as on the MOTIF malware classification dataset, comparing against standard k-means with random initialization and k-means++ initialization. On the MOTIF dataset, AQOCI produces clusterings that are competitive with and, at smaller sample sizes, superior to k-means++, with V-measure improvements of up to 26%. On synthetic data with heavily overlapping clusters, AQOCI–SimAnn outperforms k-means++ in V-measure. On well-separated synthetic data, k-means++ is clearly superior, and AQOCI exhibits a consistent performance plateau attributable to the binary encoding resolution. The dimensionality sweep demonstrates scalability to at least d = 10 without degradation. These results demonstrate that QUBO-based centroid initialization is a viable alternative formulation whose performance advantage is data-structure-dependent, strongest when clusters overlap and sample sizes are small, and whose potential for quantum speedup may be realized as quantum annealing hardware continues to mature.
Prototype-based clustering is sensitive to initial centroid placement. We characterize a QUBO formulation of the initialization problem, Adaptive Quantum Optimized Centroid Initialization (AQOCI), across two workload classes, synthetic Gaussian data with controlled cluster separation and the MOTIF malware reference dataset, using classical (TABU, simulated annealing) and hybrid quantum-classical backends. The central finding is that the payoff is data-structure-dependent rather than solver-dependent. On overlapping and complex real-world structure, QUBO initialization beats k-means++ by up to 26% in V-measure at small sample sizes. On well-separated data it plateaus at V-measure near 0.648 and k-means++ dominates. A bit-resolution sweep from 3 to 6 bits triples QUBO size and solve time with no quality change, ruling out encoding precision and localizing the bottleneck in the refinement dynamics. We report the resource cost of the formulation and identify the workload regimes where it is worth paying.
This article investigates the potential of quantum clustering, specifi cally through quantum annealing, to enhance supply chain segmentation compared with classical K-Means. Using a proof-of-concept framework, clustering is translated into a Quadratic Unconstrained Binary Optimisation formulation, tested on customer datasets via both classical Simulated Annealing and D-Wave’s Leap hybrid solver, with penalty parameter optimisation introduced to address solver sensitivity. Performance is benchmarked against K-Means on runtime, accuracy metrics, and scalability, across dataset sizes from 200 to 5,000 points. Results show that while K-Means maintains superior inertia and stability, the hybrid quantum approach achieves faster solver-reported runtimes and, on a simplifi ed 200-point, two-feature benchmark, delivers improved silhouette, Davies-Bouldin, Calinski-Harabasz, and Dunn scores once penalties are optimised — metrics which, it is noted, reward the balanced partitions structurally favoured by the pairwise QUBO objective. However, scalability remains constrained by current qubit capacity and solver access, limiting practical deployment beyond mid-sized datasets. The study concludes that classical methods remain dominant for industrial-scale segmentation; the demonstrated framework, penalty-optimisation pipeline, and objective-level analysis nonetheless provide a documented foundation, grounded in a customer segmentation case study, upon which future quantum-assisted supply chain clustering can build as hardware matures.
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(ε2) for B,S=Θ(ε−2), and the peak-qubit requirement qpeak=max{D,⌈log2B⌉+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.
This work introduces a hybrid quantum-classical method to correlation clustering, a graph-based unsupervised learning task that seeks to partition the nodes in a graph based on pairwise agreement and disagreement. In particular, we adapt GCS-Q [1], a quantum-assisted solver originally designed for coalition structure generation, to maximize intra-cluster agreement in signed graphs through recursive divisive partitioning. The proposed method encodes each bipartitioning step as a quadratic unconstrained binary optimization problem, solved via quantum annealing. This integration of quantum optimization within a hierarchical clustering framework enables handling of graphs with arbitrary correlation structures, including negative edges, without relying on metric assumptions or a predefined number of clusters. Empirical evaluations on synthetic signed graphs and real-world hyperspectral imaging data demonstrate that, when adapted for correlation clustering, GCS-Q outperforms classical algorithms in robustness and clustering quality on real-world data and in scenarios with cluster size imbalance. Our results highlight the promise of hybrid quantum-classical optimization for advancing scalable and structurally-aware clustering techniques in graph-based unsupervised learning.
This paper explores the applications of quantum annealing (QA) and classical simulated annealing (SA) to a suite of combinatorial optimization problems in machine learning, namely feature selection, instance selection, and clustering. We formulate each task as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implement both quantum and classical solvers to compare their effectiveness. For feature selection, we propose several QUBO configurations that balance feature importance and redundancy, showing that quantum annealing (QA) produces solutions that are computationally more efficient. In instance selection, we propose a few novel heuristics for instance-level importance measures that extend existing methods. For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement, and demonstrate consistent improvements in cluster compactness and retrieval metrics. Our results suggest that QA can be a competitive and efficient tool for discrete machine learning optimization, even within the constraints of current quantum hardware.
Quadratic Unconstrained Binary Optimization (QUBO) provides a versatile framework for representing NP-hard combinatorial problems, yet existing solvers often face trade-offs among speed, accuracy, and scalability. In this work, we introduce a quantum-inspired solver (QIS) that unites branch-and-bound pruning, continuous gradient-descent refinement, and quantum-inspired heuristics within a fully adaptive control architecture. We benchmark QIS3 against eight state-of-the-art solvers, including genetic algorithms, coherent Ising machines, simulated bifurcation, parallel tempering, simulated annealing, our prior QIS2 version, D-Wave's simulated-annealing (Neal), and Gurobi on three canonical QUBO problem classes: Max-Cut, NAE-3SAT, and Sherrington-Kirkpatrick spin glass problems. Under a uniform runtime budget, QIS3 attains the best solution on nearly all instances, achieving optimality in 94% of max-cut instances. These results establish QIS3 as a robust, high-performance solver that bridges classical exact strategies and quantum-inspired heuristics for scalable QUBO optimization.