2026-08-14 –, Room 3
We investigate the problem of partitioning graph states for distributed quantum computing. Graph states are a way of representing certain quantum entangled states as graphs. Due to the nature of entanglement, it's far better to partition graphs to minimize the size of the maximum matchings between partitions rather than the number of edges, as traditional algorithms do. We provide an algorithm for this in our Julia software package for graph state partitioning evaluation, QuantumHamlets.jl.
For people without quantum information science (QIS) background, and mainly interested in graph algorithms, we heuristically address the problem of balanced graph k partitioning with the objective of minimizing the sizes of the maximum matchings between partitions, rather than the number of edges cut. By this metric of minimizing matching sizes, we outperform nearly all existing algorithms for edge minimization k partition on most input graphs.
For those with QIS background:
We investigate the problem of compiling the generation of graph states to arbitrarily many distributed homogeneous quantum processing units (QPUs). To do so, we provide a protocol we term vertex cover grafting (VCG) for graph state generation, and design a heuristic algorithm we term BURY for the balanced partitioning of the graph state between the QPUs in order to reduce the number of required long-range Bell pairs utilized by VCG.
In this effort, we consider the problem of balanced k graph partitioning with the objective of minimizing the sizes of the maximum matchings between partitions, rather than the number of edges cut. We show that our heuristic algorithm, BURY, requires fewer Bell pairs to generate most graph states than state-of-the-art k partition algorithms. Furthermore, we show that BURY reduces the cut-rank of the partitions, demonstrating that the partitioning found by our algorithm is likely to minimize the Bell pair utilization of any distributed graph state generation protocol. Additionally, we discuss how one could straightforwardly apply our methods to the dynamic case where the graph state generation and measurement are performed concurrently. Our study of the balanced minimum maximum matching k-partition problem and the heuristic algorithm we design provides a scalable foundation for reducing quantum network overhead for distributed measurement-based quantum computation (MBQC), as well as any scheme where distributed graph state generation is desired.
Furthermore, this talk will attempt to introduce all QIS concepts needed for understanding, assuming the audience has a proper computer science background. Specifically, one goal of this talk is to explain graph states to the subset of the audience that is interested in graph algorithms but may be unaware of graph problems in QIS. We hope this can foster further development of algorithms for graph states.
Anthony Micciche is a PhD student at the University of Massachusetts Amherst. He studies topics related to quantum computation, quantum error correction and fault tolerance, and quantum circuit compilation.