Clustering is a fundamental task in data science that aims to group data based on their similarities. However, defining similarity is often ambiguous, making it challenging to determine the most appropriate objective function for a given dataset. Traditional clustering methods, such as the k -means algorithm and weighted maximum k -cut, focus on specific objectives—typically relying on average or pairwise characteristics of the data—leading to performance that is highly data-dependent. Moreover, incorporating practical constraints into clustering objectives is not straightforward, and these problems are known to be NP-hard. In this study, we formulate the clustering problem as a search for the ground state of a Hamiltonian, providing greater flexibility in defining clustering objectives and incorporating constraints. This approach enables the application of various quantum simulation techniques, including both circuit-based quantum computation and quantum annealing, thereby opening a path toward quantum advantage in solving clustering problems. We propose various Hamiltonians to accommodate different clustering objectives, including the ability to combine multiple objectives and incorporate constraints. We evaluate the clustering performance through numerical simulations and implementations on the D-Wave quantum annealer. The results demonstrate the broad applicability of our approach to a variety of clustering problems on current quantum devices. Furthermore, we find that Hamiltonians designed for specific clustering objectives and constraints impose different requirements for qubit connectivity, indicating that certain clustering tasks are better suited to specific quantum hardware. Our experimental results highlight this by identifying the Hamiltonian that optimally utilizes the physical qubits available in the D-Wave System.
Clustering is a fundamental task in data science that aims to group data based on their similarities. However, defining similarity is often ambiguous, making it challenging to determine the most appropriate objective function for a given dataset. Traditional clustering methods, such as the k -means algorithm and weighted maximum k -cut, focus on specific objectives—typically relying on average or pairwise characteristics of the data—leading to performance that is highly data-dependent. Moreover, incorporating practical constraints into clustering objectives is not straightforward, and these problems are known to be NP-hard. In this study, we formulate the clustering problem as a search for the ground state of a Hamiltonian, providing greater flexibility in defining clustering objectives and incorporating constraints. This approach enables the application of various quantum simulation techniques, including both circuit-based quantum computation and quantum annealing, thereby opening a path toward quantum advantage in solving clustering problems. We propose various Hamiltonians to accommodate different clustering objectives, including the ability to combine multiple objectives and incorporate constraints. We evaluate the clustering performance through numerical simulations and implementations on the D-Wave quantum annealer. The results demonstrate the broad applicability of our approach to a variety of clustering problems on current quantum devices. Furthermore, we find that Hamiltonians designed for specific clustering objectives and constraints impose different requirements for qubit connectivity, indicating that certain clustering tasks are better suited to specific quantum hardware. Our experimental results highlight this by identifying the Hamiltonian that optimally utilizes the physical qubits available in the D-Wave System.
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.
Recently, a clustering method using a combinatorial optimization problem, called combinatorial clustering, has been drawing attention due to the rapid spreads of quantum annealing and simulated annealing.Combinatorial clustering is performed by minimizing an objective function under a condition to satisfy a one-hot constraint.The objective function and the constraint function are generally formulated to a unified objective function of a QUBO (Quadratic Unconstrained Binary Optimization) problem using the method of the Lagrange multiplier.The coefficients of the QUBO function can be represented by a square matrix, which is called the QUBO matrix.Although the Lagrange multiplier needs to be large enough to avoid violating the constraint, it is usually hard to be set appropriately due to the limitation of the bit precision.For example, the latest quantum annealer can handle values represented by only six or fewer bits.Even conventional computing systems cannot control the larger value of the Lagrange multiplier as the number of data points increases.Besides, the execution time for combinatorial clustering increases exponentially as the problem size increases.This is because the time for the QUBO matrix generation is long and a dominant factor of the total execution time when the problem size is large.To solve these problems, this paper proposes combinatorial clustering that overcomes the limitation of the method of the Lagrange multiplier.The proposed method uses a QUBO solver that can externally define the one-hot constraint independent from the objective function, and the externally-defined constraint is satisfied by the operations with multiple bit-flips.As the QUBO function contains only the objective function, the method of the Lagrange multiplier is not necessary.The proposed method can optimize the objective function sufficiently even when the problem size is large.Since the constraint function is not included in the QUBO function, the proposed method also reduces the time for the QUBO matrix generation.The experimental results obtained using the artificial and real data show that the proposed method can improve the quality of annealing-based clustering results in all data sets.The experimental results also clarify that the quality of the proposed method is almost equal to or better than that of quasi-optimal clustering methods such as K-means.The evaluation using the multiple traveling salesman problem shows that the proposed method can obtain shorter tour lengths than the conventional annealing-based clustering in all 13 cases and K-means++ in 6 out of 12 cases with a significant difference.Furthermore, the proposed method can accelerate the execution time for combinatorial clustering because there is no need to calculate the coefficients of the constraint function.
The quantum approximation optimisation algorithm (QAOA) is one of the leading
candidates for testing the applicability of gate-model quantum resources at solving
optimisation problems on small-sized quantum hardware. A combinatorial problem that
has been understudied with QAOA is correlation clustering: given a weighted (+1,-1)
graph, where the edge weights indicate whether two nodes are similar (positive edge
weight) or different (negative edge weight), the task in correlation clustering is to find a
clustering that either maximises agreements, minimises disagreements or a combination
of both. In this thesis, we design Hamiltonian formulations that encode correlation
clustering problems such that they can be solved with QAOA. For all Hamiltonian
formulations we propose circuit implementations and study their complexities. To
benchmark the performances of a basic QAOA algorithm using these formulations, we
use numerical simulations on complete graph data sets. For one of the formulations,
which uses a multi-level approach naturally suitable to qudit systems, we investigate
the performances of several optimisers and introduce heuristic strategies to further
improve its performance. On all instances in our data-sets, which include complete as
well as Erdős–Renyi graphs, the improved algorithm shows competitive performances
for QAOA depth p ≥ 2. We also show that for this algorithm at p = 1 parameters exists
such that it has a performance guarantee of 0.670 on 3-regular graphs.
Recently, a clustering method using a combinatorial optimization problem, called combinatorial clustering, has been drawing attention due to the rapid spreads of quantum annealing and simulated annealing. Combinatorial clustering is performed by minimizing an objective function under a condition to satisfy a constraint. The objective function and the constraint function are generally formulated to a unified objective function of a QUBO (Quadratic Unconstrained Binary Optimization) problem by the method of the Lagrange multiplier.Although the Lagrange multiplier needs to be large enough to avoid violating the one-hot constraint, the Lagrange multiplier usually cannot be set appropriately due to the limitation of the bit precision. The latest quantum annealer can handle values represented by only six or fewer bits. Even conventional computing systems cannot handle the larger value of the Lagrange multiplier as the number of data points increases.To solve this problem, this paper proposes combinatorial clustering that overcomes the limitations of the method of the Lagrange multiplier. The proposed method uses a QUBO solver that can externally define the one-hot constraint independent from the objective function, and the externally-defined constraint is satisfied by the bit-flip operations. Since the constraint function is not included in the objective function, it is no longer needed to determine the Lagrange multiplier. The experimental results show that the proposed method can improve the quality of clustering results.
Current quantum hardware prohibits any direct use of large classical datasets. Coresets allow for a succinct description of these large datasets and their solution in a computational task is competitive with the solution on the original dataset. The method of combining coresets with small quantum computers to solve a given task that requires a large number of data points was first introduced by Harrow [arXiv:2004.00026]. In this paper, we apply the coreset method in three different well-studied classical machine learning problems, namely Divisive Clustering, 3-means Clustering, and Gaussian Mixture Model Clustering. We provide a Hamiltonian formulation of the aforementioned problems for which the number of qubits scales linearly with the size of the coreset. Then, we evaluate how the variational quantum eigensolver (VQE) performs on these problems and demonstrate the practical efficiency of coresets when used along with a small quantum computer. We perform noiseless simulations on instances of sizes up to 25 qubits on CUDA Quantum and show that our approach provides comparable performance to classical solvers.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.