Quantum Graph Partitioning for Distributed Computing
Minimizing inter-machine communication by optimally assigning operations to processors
When multiple computers collaborate on a task, operations have dependencies that require inter-machine messaging.
This project formulates graph k-partitioning as a Constrained Quadratic Model (CQM) and solves it
using D-Wave's hybrid quantum-classical solver. The goal: partition a dependency graph across k machines so that
cross-partition edges (messages) are minimized while keeping workloads balanced. This demo simulates the
partitioning process in-browser using the Kernighan-Lin heuristic.
Interactive Partitioning
Generate a graph, then partition it to minimize cross-partition edges. Nodes are colored by partition assignment.
CQM Formulation
How the graph partitioning problem is encoded as a Constrained Quadratic Model for D-Wave's quantum solver.
Binary variable for each (node, partition) pair. xi,p = 1 means node i is assigned to partition p.
Minimize the number of edges that cross partition boundaries. The term equals 0 when both endpoints share a partition, 1 otherwise.
Each node must be assigned to exactly one partition.
Each partition must contain exactly N/k nodes, ensuring balanced workloads across machines.
Pipeline
From dependency graph to optimized partition assignment.
Generate a dependency graph using one of several models: planted partition, random regular, Erdos-Renyi, or Barabasi-Albert scale-free.
Encode the k-partitioning problem as binary variables with one-hot and balance constraints, optimizing for minimum edge cuts.
Submit to D-Wave's LeapHybridCQMSampler, which combines quantum annealing with classical heuristics to find optimal solutions.
Extract the first feasible solution, compute partition sizes, and count inter/intra-partition edges to evaluate quality.
Graph partitioning is NP-hard — classical exact solvers scale exponentially. D-Wave's hybrid approach combines quantum annealing (which naturally explores low-energy states of combinatorial problems) with classical post-processing to find near-optimal solutions for problems with up to 5,000 binary variables. For distributed computing, even small improvements in partition quality can significantly reduce network latency and total computation time across thousands of operations.