Source-linked AI summary
Graph Partitioning using Quantum Annealing on the D-Wave System
Hayato Ushijima-Mwesigwa, Christian F. A. Negre, Susan M. Mniszewski
TL;DR
The paper addresses how graph partitioning can reduce computational complexity while coping with the NP-hardness of the problem and the size limits of quantum-annealing hardware. It formulates partitioning for the D-Wave system using QUBO and concurrent k-way methods, combined with hybrid processing for larger graphs. Quantum and hybrid approaches produced partitions comparable to or better than traditional tools, including reductions of cut edges by tens to hundreds in concurrent experiments.
Problem
Graph partitioning is widely used to divide arbitrarily large graphs into smaller subproblems, but it is NP-hard and exact efficient solutions appear unlikely unless P = NP.
Method
The paper maps constrained graph partitioning to QUBO, uses super-nodes for concurrent k-way partitioning, and applies complement-graph and hybrid classical-quantum methods to fit D-Wave hardware.
Results
Quantum and hybrid approaches were comparable to or better than existing graph-partitioning tools, with concurrent partitioning reducing cut edges by tens to hundreds and matching the best known results on some graphs.
Takeaways & Limitations
The results support using D-Wave-based quantum and hybrid methods for 2-part and concurrent k-part graph partitioning on benchmark, random, and QMD electronic-structure graphs.
Takeaways & Limitations
Strictly quantum approaches are limited by available graph nodes, while larger graphs require hybrid classical-quantum approaches because of current hardware constraints.
Abstract
from arXiv · showhide
In this work, we explore graph partitioning (GP) using quantum annealing on the D-Wave 2X machine. Motivated by a recently proposed graph-based electronic structure theory applied to quantum molecular dynamics (QMD) simulations, graph partitioning is used for reducing the calculation of the density matrix into smaller subsystems rendering the calculation more computationally efficient. Unconstrained graph partitioning as community clustering based on the modularity metric can be naturally mapped into the Hamiltonian of the quantum annealer. On the other hand, when constraints are imposed for partitioning into equal parts and minimizing the number of cut edges between parts, a quadratic unconstrained binary optimization (QUBO) reformulation is required. This reformulation may employ the graph complement to fit the problem in the Chimera graph of the quantum annealer. Partitioning into 2 parts, 2^N parts recursively, and k parts concurrently are demonstrated with benchmark graphs, random graphs, and small material system density matrix based graphs. Results for graph partitioning using quantum and hybrid classical-quantum approaches are shown to equal or out-perform current "state of the art" methods.
1. Introduction
The introduction motivates graph partitioning as a way to reduce computational complexity and presents quantum-annealing formulations designed around D-Wave hardware constraints. It covers unconstrained community detection, constrained equal-size partitioning, recursive and concurrent partitioning, and hybrid classical-quantum extensions.
- Quantum annealing: Quantum annealing uses quantum-mechanical effects to minimize and sample from energy-based models on hardware such as the D-Wave computer.The D-Wave system represents optimization problems through Ising variables, local fields, and pairwise couplings.
- Hardware-aware methods: QUBO, complement-graph, modularity-thresholding, and hybrid classical-quantum techniques are used to fit graph problems within D-Wave’s sparse hardware architecture.The hybrid qbsolv approach decomposes problems into CPU-generated subgraphs that are run on the quantum processing unit and assembled into a final result.
- Motivation: Graph partitioning reduces large graphs into smaller subproblems for applications including efficient computation and quantum molecular dynamics simulations.In the motivating QMD approach, density-matrix calculations are reduced to smaller subsystems at each timestep using the previous density matrix as the new graph’s adjacency matrix.
- Graph partitioning: Unconstrained partitioning produces communities characterized through a modularity metric, whereas constrained partitioning creates similar-sized parts while minimizing cut edges.The constrained formulation is addressed initially for 2 parts and can extend to 2^N parts through recursive bisection.
- Graph partitioning: The work develops quantum graph partitioning that can split a graph into k parts concurrently using a super-node formulation inspired by graph coloring.Concurrent partitioning avoids recursion or stages, but the formulation quickly exceeds available hardware space for large graphs and partitionings.
- Evaluation: The study evaluates D-Wave implementations against existing benchmarks and state-of-the-art graph-partitioning tools.The methods include traditional algorithms implemented on the annealer and formulations designed to take advantage of the hardware.
2. Methods
The paper formulates graph partitioning and community detection for quantum annealing, then maps constrained and concurrent variants onto D-Wave-compatible Ising or QUBO objectives.
- Graph Clustering/Community Detection: Community detection treats unconstrained partitions as communities and evaluates their quality with the modularity metric.Community sizes are not predefined, unlike usual graph partitioning.
- The Graph Partitioning Problem: Graph partitioning divides n vertices into k equal parts while minimizing cut edges between different parts.The paper first formulates the problem for k = 2 and later generalizes it to arbitrary k.
- The Graph Partitioning Problem: The constrained partitioning objective is relaxed into an Ising formulation that balances partition sizes against the number of cut edges using weight parameters α and β.Increasing α emphasizes balance, whereas increasing β emphasizes obtaining a smaller cut.
- The Graph Partitioning Problem: The resulting variables can be transformed from Ising spins to QUBO binary variables and mapped onto the D-Wave Chimera graph.When α = β, using the graph complement can reduce the qubits and couplers required for embedding dense graphs.
- k-Concurrent Approach for Graph Partitioning: The k-Concurrent approach partitions a graph into k parts in parallel by representing each vertex as a super-node with k unary-encoded subnodes.Exactly one subnode is set to 1 for each vertex, producing a kN × kN matrix representation.
- k-Concurrent Approach for Graph Partitioning: The method also considers recursive subdivision for producing 2^N communities and uses graph-coloring ideas to construct concurrent partitioning formulations.Super-edges pair corresponding subnodes across super-nodes, while internal constraints select one subnode per vertex.
3. Results and Discussion
The experiments evaluate quantum and hybrid quantum-classical graph partitioning across community detection, benchmark graphs, random graphs, and molecular electronic-structure graphs. Results show hardware-aware formulations can achieve comparable or better partition quality while extending the size or concurrency of solvable problems.
- Community Detection with Thresholding: A threshold of 0.12 reduced modularity by ≥30% while reducing the required number of edges by ≥65%.The sparsification lowers embedding demands on D-Wave hardware.
- Community Detection with Thresholding: Thresholding is possible for recursive 4-clustering, but the clustering quality is significantly reduced.This contrasts with the embedding benefit observed for sparse modularity matrices.
- Community Detection with Thresholding: Sparse modularity matrices reduce the qubits and couplers needed for embedding, enabling larger community-clustering problems.The approach retains a representative version of the original matrix.
- Graph Partitioning: The graph complement enabled direct quantum partitioning of dense random graphs with up to 70 vertices despite approximately 45 fully embeddable vertices.All reported solutions had quality comparable to METIS and KaHIP.
- Graph Partitioning: Hybrid qbsolv partitioned Walshaw benchmark graphs with over 100 vertices, producing smaller cut sizes than METIS and KaHIP in every case.The solutions matched the best known results for the last two graphs.
- Graph Partitioning: Recursive bisection on molecular electronic-structure graphs produced equal or reduced edge cuts for two-way partitioning versus METIS and KaHIP.Four- and eight-way recursion remained comparable overall, with increased cuts for the Phenyl dendrimer and better results for Peptide 1aft.
- k-Concurrent Graph Partitioning: Direct QPU k-Concurrent GP produced equal-sized partitions with quality comparable to METIS and qbsolv on small random graphs.The experiments were limited by embedding size, with a 15-node graph split into four parts using almost all available qubits.
- k-Concurrent Graph Partitioning: Hybrid k-Concurrent GP on dense graphs produced partitionings comparable to METIS while consistently reducing cut edges by tens to hundreds.Molecular cases were comparable or better than METIS for the Phenyl dendrimer and Peptide 1aft, although METIS had many cuts for four-way Phenyl-dendrimer partitioning.
4. Conclusion
The paper reports that quantum and hybrid quantum-classical approaches produce quality graph partitions across benchmark, random, and QMD electronic-structure graphs. Its k-Concurrent GP approach improves partition quality over existing tools while adapting execution to graph size.
- k-Concurrent GP ran directly on the QPU for small graphs and used hybrid classical-quantum qbsolv for large graphs.
- Quantum annealing GP produced quality partitions for example graphs and electronic-structure graphs from QMD simulations.
- The authors propose applying k-Concurrent GP to other domains and extending it to community detection.