Hamiltonian formulations of centroid-based clustering

Myeonghwan Seong, Daniel K. Park

Clustering is a fundamental unsupervised learning task, often formulated as an optimization problem. Traditional quantum approaches using Quadratic Unconstrained Binary Optimization (QUBO) have been limited by assumptions of equal cluster sizes. This paper introduces a unified Hamiltonian framework for centroid-based clustering that accommodates uneven cluster sizes and integrates real-world constraints. By mapping clustering to an Ising Hamiltonian and optimizing for intracluster and intercluster distances, the proposed method demonstrates superior accuracy and stability on physical quantum hardware (D-Wave) compared to classical baselines like $k$-means.

The Challenge of Subjective Clustering

Clustering involves grouping data points such that those in the same group are more similar to each other than to those in other groups. This task is inherently subjective, with outcomes varying significantly based on whether local pairwise distances or global centroids are prioritized. Incorporating practical constraints—such as mandatory groupings ("Must-Link") or specific cluster sizes—elevates clustering to an NP-hard optimization problem.

Previous attempts to leverage quantum computing for clustering via QUBO formulations often relied on the simplifying assumption of balanced cluster sizes. This limitation restricts their applicability to real-world datasets, which are rarely uniform. This work bridges this gap by developing a flexible Hamiltonian framework capable of handling imbalanced data and diverse constraints.

Methods: Mapping Clustering to Ising Hamiltonians

The researchers map the clustering problem to an Ising Hamiltonian, where binary variables (qubits) denote cluster assignments (+1 or -1). For multi-cluster scenarios ($k > 2$), a hierarchical recursive binary clustering approach is employed to optimize qubit usage.

A significant challenge in centroid-based clustering is the presence of fractional variables in the objective function due to dividing by cluster size ($N_{\pm}$). Since quantum annealers cannot natively handle these, the authors reformulate the objective by multiplying by powers of $N_{\pm}$, effectively linearizing the problem and preventing trivial solutions where all points collapse into a single cluster.

Three primary Hamiltonian variants were developed:

  1. Intracluster: Minimizes the distance between points and their respective cluster centroids (similar to $k$-means).
  2. Intercluster: Maximizes the distance between points and the centroid of the opposing cluster.
  3. Intra-Inter Combined: A weighted combination of the two.
Conceptual diagram of intracluster and intercluster distances used in the Hamiltonian formulations.

Key Insights and Hardware Performance

A critical finding is the importance of hardware-algorithm co-design. The Intra-Inter combined Hamiltonian proved exceptionally well-suited for current quantum hardware. Unlike the Intercluster-only variant, which requires auxiliary qubits for higher-order terms, the combined method maps directly to quadratic terms.

On the D-Wave Pegasus topology, the stability of the Intra-Inter combined method was remarkable. While physical qubits are often "chained" to represent logical qubits, these chains can break during the annealing process, leading to errors. The combined method achieved zero chain breaks across hundreds of samples, ensuring high-fidelity results even as the number of logical qubits increased.

Performance metrics showing chain break fraction and Rand Index across varying numbers of logical qubits on D-Wave hardware.

Results and Accuracy

The proposed methods were validated on datasets including Iris, Wine, MNIST (digits 0 and 1), and synthetic Gaussian distributions. The Intra-Inter combined method consistently outperformed classical $k$-means in terms of Rand Index (RI). For instance, it achieved an RI of 0.989 on the MNIST subset (vs. 0.981 for $k$-means) and 0.798 on overlapping Gaussian data (vs. 0.729 for $k$-means).

Furthermore, the framework demonstrated robust constraint recovery. By adding quadratic penalty terms, the algorithm successfully identified true labels even when provided with only 30% of the pairwise relationships. It also allowed for precise control over cluster cardinality, enabling specific imbalanced splits (e.g., 90/10) that unconstrained classical methods struggle to maintain.

Conclusion

This research provides a scalable and flexible path for quantum-enhanced clustering. By moving beyond the equal-size assumption and demonstrating high stability on actual QPU hardware, the authors show that Hamiltonian-based clustering is a viable tool for complex, constrained optimization tasks. Future work will focus on automated determination of the number of clusters and applying these techniques to high-dimensional time-series data in fields like drug discovery and finance.

Summary updated

BibTeX
@inproceedings{seong2025hamiltonian,
  author = {Myeonghwan Seong and Daniel K. Park},
  title = {{Hamiltonian formulations of centroid-based clustering}},
  booktitle = {Frontiers in Physics},
  year = {2025},
  doi = {10.3389/fphy.2025.1544623},
}
Figure