Automated distribution of quantum circuits via hypergraph partitioning

I. INTRODUCTION

• Relevant quantum circuits can grow large, while near-term architectures cannot execute such large circuits.The unique shortest vector problem at lattice dimension 3 is cited as requiring 842 qubits and 95,624 gates.Source: §I · p. 1
• Distributed architectures combine smaller QPUs, but using more processors increases quantum communication costs.In the extreme case of one QPU per qubit, every multi-qubit gate would require inter-QPU communication.Source: §I · p. 1
• The paper automates circuit distribution across any number of QPUs, minimizing communication by reducing the problem to hypergraph partitioning.The partitioning problem has fast heuristic solvers.Source: §I · p. 2

II. DISTRIBUTED QUANTUM COMPUTING

• Communication across QPUs is identified as the main bottleneck in distributed quantum computing.The section also introduces distributed-architecture characteristics, the distribution problem and related work, and execution of nonlocal multi-qubit gates.Source: §II · p. 2

A. Distributed quantum architectures

• The assumed architecture includes limited-workspace QPUs, classical communication, ebit-generation hardware, and memory for ebit halves.QPUs should support two-qubit gates between ebit and workspace qubits so entanglement can spread within each QPU.Source: A. Distributed quantum architectures · p. 2
• The distribution objective is to minimize ebits, since entanglement across distant parties is expected to be harder to achieve than neighboring-qubit interactions.The cited ion-trap proposal estimates ebit generation at roughly 300 times the cost of a local two-qubit gate.Source: A. Distributed quantum architectures · p. 2
• The paper avoids assumptions about the technology used to implement distributed-architecture features.This choice is made because there is no clear technology choice.Source: A. Distributed quantum architectures · p. 2

B. Nonlocal quantum gates

• The assumed circuit gateset consists of one-qubit gates and CZ gates, with CZ chosen for its input symmetry.The paper states that this gateset is universal and locally equivalent to Clifford+T.Source: B. Nonlocal quantum gates · p. 3
• A CZ gate acting on qubits in different QPUs is nonlocal and requires communication; one-qubit gates require none.Source: B. Nonlocal quantum gates · p. 3
• A cat-entangler scheme uses one ebit to share a common qubit with a remote QPU, apply its CZ gates locally, and then remove residual entanglement.Teleporting the qubit there and back would use two ebits, but can use one if the qubit need not return.Source: B. Nonlocal quantum gates · p. 3

C. The circuit distribution problem

• The objective is to minimize the ebits needed to distribute a circuit; the model assumes any pair of QPUs can be entangled directly.When direct connectivity is unavailable, an intermediary QPU can establish the desired entanglement using two physical ebits; the paper treats the resulting log N factor as secondary to overall ebit use.Source: C. The circuit distribution problem · p. 3
• Unlike topological-constrained simulation, circuit distribution treats two-qubit gates as realizable but distinguishes local gates from nonlocal gates requiring communication.Topological-constrained simulation seeks shallow circuits, whereas distribution focuses on reducing communication operations, which need not minimize circuit depth.Source: C. The circuit distribution problem · p. 3
• Figure 2 contrasts an original circuit with its distributed version, marking the QPU split, an ebit, and classical communication of measurement outcomes.Figure 3 depicts two initial ebits connecting QPUs A and B to intermediary C, resulting in an ebit between A and B using two ebits and two classical communications.Source: Figure 2 · p. 4, Figure 3 · p. 4
• Distribution optimizes global qubit interactions by grouping highly interacting qubits together, rather than optimizing each nonlocal operation separately.The paper assumes no internal QPU topology constraints; separate routing or circuit redesign methods may address such constraints later.Source: C. The circuit distribution problem · pp. 3–4
• The earlier graph-partitioning approach adds an exhaustive gate-implementation search with exponential runtime, while this paper encodes distribution choices in a hypergraph for partitioning across any number of QPUs.The earlier authors identified distribution across any number of QPUs as an open problem.Source: C. The circuit distribution problem · p. 4

III. AUTOMATED CIRCUIT DISTRIBUTION

• The section explains how hypergraph partitioning can solve the quantum circuit distribution problem.It develops the reduction as the section's central approach.Source: §III · p. 4
• The section also discusses practical aspects of implementing the distribution approach.The passage identifies implementation as a topic alongside the reduction.Source: §III · p. 4
• Further technical details are supplied in Appendices A and B.Source: §III · p. 4

A. Reduction to hypergraph partitioning

• Partitioning assigns hypergraph vertices to k blocks, with load balance limiting each block's vertex count according to the imbalance tolerance ω.The partitioning objective also seeks the lowest possible cut score.Source: A. Reduction to hypergraph partitioning · p. 4
• A hyperedge's cut count is the number of distinct blocks containing its vertices minus one, so it counts the extra blocks that need the wire's state.Each extra block reached requires an ebit, making the hyperedge cuts correspond to communication cost.Source: A. Reduction to hypergraph partitioning · pp. 4–5
• The mapping treats wire-vertices as qubit allocations, CZ-vertices as gate assignments, and blocks as QPUs; the objective pairs load balance with fewest cuts.The pseudocode translates circuit interaction information into the hypergraph being partitioned.Source: A. Reduction to hypergraph partitioning · p. 5, Figure 4 · p. 5
• The linear-time hypergraph construction represents wires and CZ gates as vertices and groups CZ gates that may share an ebit into hyperedges.The algorithm encodes the circuit's relevant grouping information in O(n) time for n gates.Source: A. Reduction to hypergraph partitioning · p. 5
• Each possible distributed implementation corresponds to a unique partition of the circuit hypergraph, and its number of cuts equals the required ebit count.This correspondence enables third-party hypergraph partitioners to produce distributions with low ebit use.Source: A. Reduction to hypergraph partitioning · p. 5
• After partitioning, the distributed circuit is built by adding cat-entanglers and cat-disentanglers for cuts and assigning CZ gates to their QPUs, in O(n) time.The construction takes O(cuts + gates) steps; because cuts ≤ 2 gates, it is linear in the original circuit's gate count.Source: A. Reduction to hypergraph partitioning · p. 5

B. Implementation

• The implementation uses preprocessing and post-processing in addition to hypergraph extraction and distributed-circuit construction.Source: B. Implementation · p. 5
• Preprocessing first converts the input to an equivalent circuit containing only one-qubit gates and CZ gates.Quipper provides specialized functionality for this transformation.Source: B. Implementation · p. 5
• Reordering CZ and some one-qubit gates can bring CZ gates together so larger nonlocal groups can share one ebit.The reordering may create Pauli X byproducts that can be pushed to the end and canceled; the overhead is at most one extra X-Z pair per wire.Source: B. Implementation · p. 5
• When qubit connectivity changes significantly across circuit stages, preprocessing splits the circuit into segments and distributes each segment separately.Source: B. Implementation · pp. 5–6
• Post-processing applies a cat-disentangler after an ebit group's last CZ gate, freeing its storage space for reuse.Source: B. Implementation · p. 6

IV. RESULTS

• The five Quipper circuits included BF’s quantum-walk fragment, BWT at height 200, GSE with 150 precision qubits, USV-R at lattice dimension 3, and QFT with 200 qubits.These configurations differ from defaults for BWT, GSE, USV-R, and QFT.Source: §IV · p. 6
• Each circuit was distributed across 4–16 QPUs; Table I reports the worst ebit-space overhead and runtime across those distributions.Source: Table I · p. 6
• Circuits of the evaluated sizes could be distributed in a few minutes on a standard desktop computer.The five circuits were selected from Quipper’s library and discussed as examples of quantum-computing speedup.Source: §IV · p. 6
• The implementation reduced ebit-space overhead by limiting how many gates could occur between nonlocal CZ gates sharing an ebit.This limits how long the corresponding ebit must remain stored.Source: §IV · p. 6
• Over 60% of CZ gates were implemented locally or for free in every case, while using more QPUs increased communication and ebit use.Figure 7 shows ebit proportions across 4, 6, 8, 10, 12, 14, and 16 QPUs with equal qubit allocation.Source: §IV · p. 6, Figure 7 · p. 7
• For GSE, hypergraph partitioning saved approximately half the ebits, while USV-R showed almost no improvement because most CZ gates were already local.Figure 8 compares the hypergraph approach with standard graph partitioning.Source: §IV · p. 7

Bonus: Distributing CCZ gates

• The extension represents each CCZ gate as a hypergraph vertex reached by three wire hyperedges, and uses cuts to determine ebit consumption.The same cat-entangler and cat-disentangler can implement groups of nonlocal CCZ and CZ gates.Source: Bonus: Distributing CCZ gates · p. 7
• A CCZ gate whose three wires are on different QPUs requires two ebits; replacing a CZ with a CCZ in the described grouped implementation can use one ebit.Source: Bonus: Distributing CCZ gates · p. 7
• Distributing CCZ gates saves a remarkable proportion of ebits for BF and BWT, but does not change results for QFT.Figure 9 compares distributed CCZ gates with decomposing them into CZ gates; QFT uses only two-qubit gates.Source: Bonus: Distributing CCZ gates · p. 8, Figure 9 · p. 8

• A better circuit-distribution optimiser would also yield a hypergraph partitioner beating KaHyPar unless it lifts the approach's constraints.The authors frame the constraints as open problems for reducing communication further.Source: §V · p. 8
• The evaluation uses every one-qubit gate and CZ as its gateset; other multi-qubit gates may improve results, and the best gateset may depend on architecture.Source: §V · p. 8
• Rearranging multi-qubit gates may change circuit connectivity in a way that favors distribution; the described preprocessing instead rearranges one-qubit gates.Source: §V · p. 8
• Optimal hypergraph partitions are unavailable in practice because finding them is NP-hard, so the reported results use efficiently found close-to-optimal partitions.Source: §V · p. 8
• Qubit decoherence limits NISQ execution to no more than 1,000 consecutive two-qubit gates, so the authors recommend optimizing circuit depth before distribution.They identify exploiting parallelism across QPUs to reduce coherent storage time as a research direction.Source: §V · p. 8
• Five literature test circuits, too large for one near-term QPU, were evaluated favorably with the automated communication-minimizing distribution approach.Source: §V · p. 8

APPENDIX A

• Each allowed circuit distribution corresponds to a unique hypergraph partition, with cut count equal to the required ebit count.The correspondence preserves the gate set and gate order.Source: Appendix A · p. 10
• A polynomial-size dummy circuit built from any hypergraph yields an extended hypergraph whose optimal partition recovers an optimal partition of the input.The construction uses one wire per vertex and CZ gates for each hyperedge; merging added CZ-vertices retrieves the input hypergraph.Source: Appendix A · pp. 10–11
• Merging the auxiliary CZ-vertices from an optimal extended-hypergraph partition preserves optimality for the input hypergraph.Figure 10 illustrates the extended hypergraph and the vertex merges used to retrieve the input.Source: Appendix A · p. 11, Figure 10 · p. 12
• Quantum circuit distribution is NP-hard because hypergraph partitioning reduces to it in polynomial time.The cited hardness result for hypergraph partitioning is.Source: Appendix A · p. 11

APPENDIX B

• Pre-processing splits a circuit near dramatic changes in qubit connectivity, then distributes the resulting segments using the Section III A approach.The segments are executed sequentially, and moving qubits between segments may require teleportation whose ebit cost is included in the reported results.Source: Appendix B · p. 11
• The procedure begins with user-set segment size and discrepancy threshold, compares neighboring segment partitions, and merges segments when their discrepancy is below the threshold.The version used for Section IV instead merges when discrepancy is minimal and continues until further merging no longer decreases the ebit count.Source: Appendix B · p. 11
• The discrepancy score compares segment partitions using wire reallocation and connectivity, weighting each wire by its lower segment-specific hyperedge count and normalizing by the smaller total count.A wire allocated to the same QPU in both segments contributes zero; a wire rarely used in one segment is relatively cheap to reallocate.Source: Appendix B · p. 11
• KaHyPar's performance gain from partitioning smaller segment hypergraphs outweighed the cost of running the partitioner multiple times.The passage attributes the gain to the reduced input size of an NP-hard partitioning problem.Source: Appendix B · p. 12