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 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.
The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.
Clustering remains a cornerstone of unsupervised learning, yet classical algorithms often struggle with the inherent complexities of modern datasets, such as high dimensionality, non-linear separability, and significant noise. This paper introduces the Hybrid Quantum-Classical Clustering Algorithm (HQCA), a novel framework that leverages the power of quantum computation and the robustness of classical machine learning to overcome these limitations. HQCA integrates a quantum kernel estimation phase, utilizing a parameterized quantum circuit to project data into a high-dimensional Hilbert space, thereby enhancing cluster separability where classical kernels fail. Furthermore, it employs a quantum-enhanced optimization routine, based on the Quantum Approximate Optimization Algorithm (QAOA), to determine optimal cluster centroids, thereby mitigating the common pitfall of local minima encountered by algorithms like K-Means. The algorithm also incorporates a quantum-inspired gap statistic to autonomously determine the optimal number of clusters. We rigorously evaluate HQCA against state-of-the-art classical clustering methods, including K-Means, DBSCAN, and Spectral Clustering, on multiple real-world benchmark datasets from the UCI repository, such as Iris, Wine, and a high-dimensional image dataset (Fashion-MNIST). Our results demonstrate that HQCA consistently achieves superior performance across multiple evaluation metrics, including Purity, Silhouette Score, and Adjusted Rand Index (ARI), particularly excelling in scenarios involving complex, non-linear data manifolds. The proposed hybrid paradigm not only signifies a substantial leap in clustering accuracy and robustness but also provides a scalable pathway for leveraging current Noisy Intermediate-Scale Quantum (NISQ) devices in practical data analytics workflows, marking a critical step toward potential quantum advantage in unsupervised learning. We emphasize that the demonstrated advantage is algorithmic and representational, not an asymptotic runtime advantage.
Graph partitioning is a fundamental problem in various fields, including computer graphics, high-performance computing, and network design. Traditional graph partitioning algorithms often suffer from high computational complexity, particularly when dealing with large and complex graphs. This research investigates the potential of quantum-inspired optimization techniques, specifically leveraging concepts from quantum annealing, to accelerate the graph partitioning process. We formulate the graph partitioning problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, allowing us to simulate the behavior of a quantum annealer on classical hardware. The core of our approach involves mapping the graph's connectivity structure onto a QUBO, representing nodes as binary variables and edges as constraints. By exploiting the inherent parallelism of quantum annealing, we aim to find optimal or near-optimal partitions significantly faster than conventional methods. The results demonstrate the feasibility and potential advantages of this quantum-inspired strategy for graph partitioning, offering a promising direction for tackling computationally intensive graph problems.
The increasing number of Low Earth Orbit (LEO) satellites, driven by lower manufacturing and launch costs, is proving invaluable for Earth observation missions and low-latency internet connectivity. However, as the number of satellites increases, the number of communication links to maintain also rises, making the management of this vast network increasingly challenging and highlighting the need for clustering satellites into efficient groups as a promising solution. This paper formulates the clustering of LEO satellites as a coalition structure generation (CSG) problem and leverages quantum annealing to solve it. We represent the satellite network as a graph and obtain the optimal partitions using a hybrid quantum-classical algorithm called GCS-Q. The algorithm follows a top-down approach by iteratively splitting the graph at each step using a quadratic unconstrained binary optimization (QUBO) formulation. To evaluate our approach, we utilize real-world three-line element set (TLE/3LE) data for Starlink satellites from Celestrak. Our experiments, conducted using the D-Wave Advantage annealer and the state-of-the-art solver Gurobi, demonstrate that the quantum annealer significantly outperforms classical methods in terms of runtime while maintaining the solution quality. The performance achieved with quantum annealers surpasses the capabilities of classical computers, highlighting the transformative potential of quantum computing in optimizing the management of large-scale satellite networks.
Of late, we are witnessing spectacular developments in Quantum Information Processing with the availability of Noisy Intermediate-Scale Quantum devices of different architectures and various software development kits to work on quantum algorithms. Different problems, which are hard to solve by classical computation, but can be sped up (significantly in some cases) are also being populated. Leveraging these aspects, this paper examines unsupervised graph clustering by quantum algorithms or, more precisely, quantum-assisted algorithms. By carefully examining the two cluster Max-Cut problem within the framework of quantum Ising model, an extension has been worked out for max 3-cut with the identification of an appropriate Hamiltonian. Representative results, after carrying out extensive numerical evaluations, have been provided including a suggestion for possible futuristic implementation with qutrit devices. Further, extrapolation to more than 3 classes, which can be handled by qudits, of both annealer and gate-circuit varieties, has also been touched upon with some preliminary observations; quantum-assisted solving of Quadratic Unconstrained D-ary Optimisation is arrived at within this context. As an additional novelty, a qudit circuit to solve max-d cut through Quantum Approximate Optimization algorithm is systematically constructed.
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.