Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Workload Characterization

Characterizing QUBO-Based Centroid Initialization: When Does Quantum-Inspired Clustering Pay Off?

Nicholas R. Allgood, Ajinkya Borle, Charles Nicholas

Published Sep 1, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1109/iiswc71020.2026.00068

Related papers

Adaptive Quantum Optimized Centroid Initialization

Nicholas R. Allgood, Ajinkya Borle, Charles Nicholas

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.

arXiv:2401.11258•Jan 20, 2024•0 citations

qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices

Pedro Chumpitaz-Flores, My Duong, Ying Mao +1 more

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.

arXiv:2510.22540•IEEE International Conference on Big Data (BigData)•Dec 8, 2025•3 citations

Quantum Portfolio Optimization Under Realistic Frictions: A Rigorous Comparison with Classical Baselines

Ekow Tawiah Andoh

We test whether quantum-inspired optimization, specifically Quadratic Unconstrained Binary Optimization (QUBO) solved via simulated annealing, can improve implementable portfolio performance compared to classical baselines when realistic frictions are included. Our experimental design uses daily returns from the Center for Research in Security Prices (CRSP) for S&P500 constituents spanning 2014–2025, with monthly rebalancing, explicit transaction costs, and turnover accounting. We compare QUBO portfolios against equal-weight and convex mean–variance portfolios across multiple universe sizes (20, 50, 67 assets), lookback windows, and transaction-cost levels. Statistical significance is assessed via paired moving-block bootstrap on out-of-sample net returns. A hyperparameter sweep over encoding depth, penalty coefficients, and turnover reveals 19 of 81 QUBO configurations beat the equal-weight baseline, with the best achieving a Sharpe of 1.59 versus 1.42. However, under a fair walk forward model-selection protocol that eliminates look-ahead bias, the QUBO strategy does not achieve statistically significant superiority over either classical benchmark (∆Sharpe vs. equal weight: −0.13, 95% CI [−0.46,0.16]; vs. mean–variance: −0.29, 95% CI [−0.63,0.06]). Excessive turnover (averaging ∼1.0 per rebalance) is identified as the primary bottleneck. We conclude that current QUBO formulations with simulated annealing do not yet deliver a robust, implementable edge over well-tuned convex optimizers, though the framework remains a promising research direction as quantum hardware and hybrid solvers mature.

•Mar 24, 2026•0 citations

Quantum Annealing for Customer Segmentation: A Proof-of-Concept QUBO Framework for Supply Chain Clustering

Raphaël Bouchet, Alena Puchkova

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.

•Nov 11, 2026•0 citations

Hardware-Aware Quantum Optimization

Gerlach, Thore Thassilo

Quantum Optimization (QO) is emerging as a promising approach to tackle hard combinatorial optimization problems by leveraging the unique computational properties of quantum hardware. In recent years, QO has gained traction in Machine Learning (ML), where problems such as clustering and vector quantization can be naturally expressed as Quadratic Unconstrained Binary Optimization (QUBO) problems. These ML applications often involve complex, high-dimensional data, which directly influences both the structure and scale of the resulting QUBO formulations. However, current quantum devices fall under the category of Noisy Intermediate-Scale Quantum (NISQ) hardware, which imposes significant limitations on qubit counts and small error rates. This dissertation investigates the impact of data complexity and data scale—as encountered in ML settings—on the effectiveness and feasibility of QO on NISQ devices. We propose novel, hardware-aware methods to overcome these challenges. The first part of this thesis focuses on the effect of data complexity for QO. We analyze how problem structure—particularly when QUBO formulations are derived from ML tasks—affects quantum solvability. We identify the spectral gap as a key factor in the success of adiabatic quantum algorithms and provide a theoretical and empirical analysis linking data-induced complexity to optimization performance.To address noise sensitivity and limited precision, we introduce a preprocessing framework based on a principled Branch-and-Bound algorithm that reduces dynamic range while preserving global optima. This improves robustness on both quantum annealers and classical solvers. In the second part, the thesis addresses challenges introduced by data scale. First, we propose a recursive Divide-and-Conquer strategy that breaks down large QUBO problems into tractable subproblems, demonstrated through an application to Bundle Adjustment in 3D scene reconstruction. Second, we introduce a variable and constraint generation method inspired by column generation for Integer Linear Programming, enabling dynamic QUBO size growth. This technique is successfully applied to Multi-Agent Pathfinding, where it scales well on NISQ devices while maintaining compatibility with classical solvers. Finally, we explore QUBO reformulations that reduce problem size through compact encodings and cyclic expansion, enabling the use of quantum hardware for tasks such as FPGA placement in chip design. Across all contributions, the developed algorithms are evaluated both theoretically and empirically, with experiments conducted on real quantum and quantum-inspired hardware. These methods significantly improve solution quality, scalability, and hardware compatibility, paving the way for more effective use of QO in practical settings. While tailored for NISQ era constraints, the results remain relevant for fault-tolerant quantum computing, offering insights into the long-term viability of QO across hardware generations.

•Nov 3, 2025•0 citations

Quantum-Assisted Correlation Clustering

Antonio Macaluso, Supreeth Mysore Venkatesh, Diego Arenas +2 more

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.

arXiv:2509.03561•IEEE International Conference on Quantum Artificial Intelligence (QAI)•Nov 2, 2025•2 citations
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.
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.
Clustering on NISQ hardware is constrained by data loading and limited qubits. We present \textbf{qc-kmeans}, a hybrid compressive kkk-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)O(ε2) for B,S=Θ(ε−2)B,S=Θ(\varepsilon^{-2})B,S=Θ(ε−2), and the peak-qubit requirement qpeak=max⁡{D,⌈log⁡2B⌉+1}q_{\text{peak}}=\max\{D,\lceil \log_2 B\rceil + 1\}qpeak​=max{D,⌈log2​B⌉+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=1p{=}1p=1), the method ran with ≤9\le 9≤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×1054.3\times 10^54.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.
We test whether quantum-inspired optimization, specifically Quadratic Unconstrained Binary Optimization (QUBO) solved via simulated annealing, can improve implementable portfolio performance compared to classical baselines when realistic frictions are included. Our experimental design uses daily returns from the Center for Research in Security Prices (CRSP) for S&P500 constituents spanning 2014–2025, with monthly rebalancing, explicit transaction costs, and turnover accounting. We compare QUBO portfolios against equal-weight and convex mean–variance portfolios across multiple universe sizes (20, 50, 67 assets), lookback windows, and transaction-cost levels. Statistical significance is assessed via paired moving-block bootstrap on out-of-sample net returns. A hyperparameter sweep over encoding depth, penalty coefficients, and turnover reveals 19 of 81 QUBO configurations beat the equal-weight baseline, with the best achieving a Sharpe of 1.59 versus 1.42. However, under a fair walk forward model-selection protocol that eliminates look-ahead bias, the QUBO strategy does not achieve statistically significant superiority over either classical benchmark (∆Sharpe vs. equal weight: −0.13, 95% CI [−0.46,0.16]; vs. mean–variance: −0.29, 95% CI [−0.63,0.06]). Excessive turnover (averaging ∼1.0 per rebalance) is identified as the primary bottleneck. We conclude that current QUBO formulations with simulated annealing do not yet deliver a robust, implementable edge over well-tuned convex optimizers, though the framework remains a promising research direction as quantum hardware and hybrid solvers mature.
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.
Quantum Optimization (QO) is emerging as a promising approach to tackle hard combinatorial optimization problems by leveraging the unique computational properties of quantum hardware. In recent years, QO has gained traction in Machine Learning (ML), where problems such as clustering and vector quantization can be naturally expressed as Quadratic Unconstrained Binary Optimization (QUBO) problems. These ML applications often involve complex, high-dimensional data, which directly influences both the structure and scale of the resulting QUBO formulations. However, current quantum devices fall under the category of Noisy Intermediate-Scale Quantum (NISQ) hardware, which imposes significant limitations on qubit counts and small error rates. This dissertation investigates the impact of data complexity and data scale—as encountered in ML settings—on the effectiveness and feasibility of QO on NISQ devices. We propose novel, hardware-aware methods to overcome these challenges. The first part of this thesis focuses on the effect of data complexity for QO. We analyze how problem structure—particularly when QUBO formulations are derived from ML tasks—affects quantum solvability. We identify the spectral gap as a key factor in the success of adiabatic quantum algorithms and provide a theoretical and empirical analysis linking data-induced complexity to optimization performance.To address noise sensitivity and limited precision, we introduce a preprocessing framework based on a principled Branch-and-Bound algorithm that reduces dynamic range while preserving global optima. This improves robustness on both quantum annealers and classical solvers. In the second part, the thesis addresses challenges introduced by data scale. First, we propose a recursive Divide-and-Conquer strategy that breaks down large QUBO problems into tractable subproblems, demonstrated through an application to Bundle Adjustment in 3D scene reconstruction. Second, we introduce a variable and constraint generation method inspired by column generation for Integer Linear Programming, enabling dynamic QUBO size growth. This technique is successfully applied to Multi-Agent Pathfinding, where it scales well on NISQ devices while maintaining compatibility with classical solvers. Finally, we explore QUBO reformulations that reduce problem size through compact encodings and cyclic expansion, enabling the use of quantum hardware for tasks such as FPGA placement in chip design. Across all contributions, the developed algorithms are evaluated both theoretically and empirically, with experiments conducted on real quantum and quantum-inspired hardware. These methods significantly improve solution quality, scalability, and hardware compatibility, paving the way for more effective use of QO in practical settings. While tailored for NISQ era constraints, the results remain relevant for fault-tolerant quantum computing, offering insights into the long-term viability of QO across hardware generations.
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.