Quantum Hamlets: Distributed Compilation of Large Algorithmic Graph States

• URL: http://arxiv.org/abs/2603.06387v1
• Date: Fri, 06 Mar 2026 15:36:22 GMT
• Title: Quantum Hamlets: Distributed Compilation of Large Algorithmic Graph States
• Abstract summary: We show that our algorithm, BURY, partitions graph states to require fewer Bell pairs for generation than state-of-the-art k partition algorithms.<n>We discuss how one could straightforwardly apply our methods to the dynamic case where the graph state generation and measurement are performed concurrently.
• Score: 1.7856410179559383
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of compiling the generation of graph states to arbitrarily many distributed homogeneous quantum processing units (QPUs), providing a scalable partitioning algorithm and graph state generation protocol to minimize the number of Bell pairs required. To this goal, we consider the problem of balanced k graph partitioning with the objective of minimizing the sizes of the maximum matchings between partitions, a more natural measure of entanglement compared to the naive but common metric of cut edges. We show that our heuristic algorithm, BURY, partitions graph states to require fewer Bell pairs for generation 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 future improved 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.

Related papers

• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule.<n>We analyze the algorithm under the block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves proportional sampling to cluster size.
  arXiv  Detail & Related papers  (2026-07-30T02:45:31Z)
• Efficient Preparation of Graph States using the Quotient-Augmented Strong Split Tree [1.5006258585503878]
  Graph states are a key resource for measurement-based quantum computation and quantum networking.<n>We introduce a split-fuse construction for arbitrary DH graph states, achieving linear scaling with respect to entangling gates, time steps, and auxiliary qubits.<n>We also discuss a generalized divide-and-conquer split-fuse strategy and a simple greedy for generic graphs based on triangle enumeration.
  arXiv  Detail & Related papers  (2026-03-25T03:30:57Z)
• Finding trail covers: near-optimal decompositions of graph states as linear fusion networks [1.7842332554022695]
  We study three graph-theoretic problems which can be seen as generalisations of the Eulerian and Hamiltonian path problems.<n>These arise in photonic implementations of measurement-based quantum computing.<n>We propose new rewrite strategies for graph states that reduce the number of fusions required to build a given graph.
  arXiv  Detail & Related papers  (2025-08-25T18:06:53Z)
• Quantum algorithms through graph composition [0.40792653193642503]
  We introduce the graph composition framework, a generalization of the st-connectivity framework for generating quantum algorithms.<n>We show how the st-connectivity framework subsumes the learning graph framework, the weighted-decision-tree framework, and a zero-error version of the latter.<n>We also simplify existing quantum algorithms for the space-efficient directed st-connectivity problem, the pattern-matching problem and the infix-search problem.
  arXiv  Detail & Related papers  (2025-04-02T20:20:51Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Graph Cuts with Arbitrary Size Constraints Through Optimal Transport [18.338458637795263]
  We propose a new graph cut algorithm for partitioning graphs under arbitrary size constraints. We solve it using an accelerated proximal GD algorithm which guarantees global convergence to a critical point.
  arXiv  Detail & Related papers  (2024-02-07T10:33:09Z)
• Multipartite Entanglement Distribution in Quantum Networks using Subgraph Complementations [8.194910516215462]
  We propose a novel approach for distributing graph states across a quantum network.<n>We classify common classes of graph states, along with their optimal distribution time using subgraph complementations.
  arXiv  Detail & Related papers  (2023-08-25T23:03:25Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
  We address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system. We apply this algorithm to rate distortion and its variants including the quantum setting.
  arXiv  Detail & Related papers  (2022-01-07T13:33:28Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNN is a universal framework to scale up any convolution-based GNNs using Vector Quantization (VQ) without compromising the performance. Our framework avoids the "neighbor explosion" problem of GNNs using quantized representations combined with a low-rank version of the graph convolution matrix.
  arXiv  Detail & Related papers  (2021-10-27T11:48:50Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.