Hamiltonian formulations of centroid-based clustering

Abstract

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.

17 pages, 8 figures

References in corpus (24)

• Scikit-learn: Machine Learning in Python
• Natural Scales in Geographical Patterns
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• High-fidelity parallel entangling gates on a neutral atom quantum computer
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Near-optimal ground state preparation
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Assembly and coherent control of a register of nuclear spin qubits
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Preparing ground states of quantum many-body systems on a quantum computer
• Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
• Quantum Annealing for Combinatorial Clustering
• Quantum logic and entanglement by neutral Rydberg atoms: methods and fidelity
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Rydberg blockade based parity quantum optimization
• Aquila: QuEra's 256-qubit neutral-atom quantum computer
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Universal quantum algorithmic cooling on a quantum computer
• Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All