Towards Reproducible Evaluation of Distributed Quantum Circuit Partitioning Algorithms

AI summary

Overview

Research area: Quantum computing software and benchmarking — specifically distributed quantum computing (DQC) compiler evaluation and circuit partitioning.

Technical level: Intermediate. Readers should be comfortable with quantum circuit concepts (qubits, gate depth, entanglement, teleportation) and basic graph partitioning ideas, but the paper is a methodology/benchmarking study rather than a new algorithm paper.

Scope: The paper adapts established monolithic quantum-circuit benchmarking metrics to distributed circuits in order to quantify the structural and temporal overheads that today's DQC partitioning algorithms hide when they are judged only by entanglement (e-bit) cost.

What This Paper Is About

Distributed quantum computers network several small quantum processing units (QPUs) together, and compilers must split a single large quantum circuit across those QPUs — a step called circuit partitioning. Current partitioning algorithms are almost always judged by one number: how many entangled "e-bits" the split consumes, because inter-QPU communication is two to three orders of magnitude slower and noisier than local routing. The authors argue this single metric misses what actually happens to the circuit's structure — how deep it becomes, how much parallelism it loses, how long qubits sit idle — and build an open, automated pipeline to measure those penalties directly.

Key Contributions

1. Methodological evaluation. The authors port benchmarking metrics previously used only for monolithic circuits (from QASMBench and SupermarQ) onto partitioned, distributed circuits, exposing physical execution trade-offs that e-bit counts mask.
2. Open-source pipeline. They release an automated, reproducible benchmarking framework at https://github.com/cake-lab/dqc-evaluation/ that combines state-of-the-art partitioners, standardized workloads, configurable network topologies, and YAML-controlled experiment configuration.
3. Empirical analysis of distribution overheads. They quantify how heuristics that optimize purely for e-bits can severely inflate circuit depth and degrade gate density, and show that comparable e-bit costs do not imply comparable structural damage.
4. A unified wrapper and replication check. Because DISQCO and Pytket-DQC use different internal representations, the authors built a wrapper that ingests Qiskit-decomposed circuits, runs each partitioner under a 600-second timeout, and exports distributed circuits into a common format — then validated it by reproducing published e-bit counts.

Main Findings

• Success rates vary enormously across partitioners. Across all experiments, MLFM-R completed 90.41% of runs and FGP-rOEE 81.48%, while the three Pytket variants landed at roughly 33–34% (33.67% for P, 34.28% for PE, 32.81% for ESD). Failure rates stayed low (≤ 7.9%) for every method; the losses came from timeouts. FGP-rOEE's remaining 17.25% was almost entirely partitioning timeouts (0.00% postprocessing timeouts), whereas Pytket P lost 57.40% of runs to postprocessing timeouts and Pytket ESD lost 35.87% to partitioning timeouts.
• The pipeline reproduces prior e-bit results. Against reference values approximated from Burt et al. for 2-QPU and 4-QPU fully connected networks, reproduced e-bit counts for MLFM-R, FGP-rOEE, and the Pytket variants across CP, QAOA, QFT, and QV closely follow the parity line, with minor scatter attributed to stochastic partitioning and randomized benchmark circuits. FGP-rOEE generally shows higher e-bit costs for QAOA and QFT.
• Communication cost is driven by scale and concurrency. The strongest predictors of e-bit cost are gate count (Spearman r = 0.88) and parallelism (r = 0.84). The only metric that significantly reduces communication overhead is entanglement variance (r = −0.55), confirming that concentrating dense interaction hotspots on single nodes lowers e-bit cost.
• Distribution erodes gate density and lengthens qubit lifetimes. Non-local teleportation primitives force qubits to wait, reducing utilization and gate density (r = −0.81). High input parallelism and gate count correlate with expanded circuit depth (r = 0.78 and r = 0.85) because concurrent operations must be serialized across the network. Circuits with high initial entanglement ratio suffer a severe decrease in entanglement ratio (r = −0.84).
• Compiler runtime tracks circuit scale, not crowding. Partitioning execution time correlates with depth (r = 0.70), width (r = 0.65), and gate count (r = 0.68), while gate density shows no statistically significant correlation with execution time.
• Equal e-bit counts, unequal damage. MLFM-R and Pytket-ESD have comparable median e-bit counts, yet MLFM-R inflates circuit depth by a significantly higher ratio. All algorithms reduce gate density, with the most pronounced degradation in FGP-rOEE.
• Restricted topology is expensive. Moving from a fully connected 4-QPU network to a 4-QPU linear network forces multi-hop routing and significantly inflates e-bit consumption; the grid topology sits between them.

Methodology in Plain English

The authors built a four-stage automated pipeline controlled by YAML configuration files so experiments can be repeated. First, monolithic circuits written in OpenQASM are loaded and decomposed with Qiskit. Second, they are handed to one of three partitioner families: MLFM-R and FGP-rOEE (both from the DISQCO framework) and three Pytket-DQC variants (Partitioning, Partitioning with Embedding, and Cover Embedding Steiner Detached). Third, the circuit is distributed onto a chosen inter-QPU topology: a 4-QPU linear line, a 4-QPU grid, or 2-QPU and 4-QPU fully connected networks. In every configuration each QPU is given ⌈n_q/k⌉ + 1 qubits — one extra communication qubit for teleportation primitives — and intra-QPU connectivity is assumed fully connected. Fourth, both the original monolithic circuit and the resulting distributed circuit (which contains explicit remote-gate instructions) are profiled by parsing Qiskit's directed acyclic graph representation, and the metrics are compared as absolute values, ratios, and deltas.

The workloads are QASMBench circuits spanning the small (2–10 qubits), medium (11–27 qubits), and large (28–433 qubits) categories, plus a regenerated dataset following Burt et al.'s methodology (16 to 96 qubits, 10 distinct instances per size for randomized circuit types), plus four structured benchmark families: QFT (all-to-all interactions, O(n²) communication overhead), QAOA at 50% edge probability, Quantum Volume with layers set equal to the number of qubits, and CP-fraction circuits at gate densities of 0.3, 0.5, 0.7, and 0.9. Metrics include direct costs (e-bit count, partitioning execution time), standard circuit properties (width, depth, gate count), and structural features (gate density, retention lifespan, liveness, parallelism, entanglement ratio, entanglement variance). Correlations are reported only when statistically significant (p ≤ 0.05) and above a strength threshold (|r| ≥ 0.20).

Why This Matters

Impact on research. The paper reframes DQC partitioning evaluation: an algorithm that wins on e-bits can lose badly on depth and gate density, which determine whether the distributed circuit is executable at all on real hardware with limited coherence. It also establishes a shared, open artifact so results across partitioner papers become comparable rather than reported in incompatible formats.

Real-world applications.

• Compiler and toolchain development for modular, network-linked quantum processors.
• Hardware/network co-design: choosing inter-QPU topologies (linear vs. grid vs. fully connected) knowing the concrete e-bit penalty of restricted connectivity.
• Benchmarking and procurement: giving hardware vendors and users structure-aware metrics for distributed execution rather than single-number entanglement costs.
• Scheduling and resource planning for future networked quantum data centers where remote operations dominate latency.

Industry relevance. Any organization pursuing modular scaling — networking small QPUs instead of building one large processor — needs compiler decisions that respect coherence budgets. The finding that postprocessing into a common representation timed out for up to 57.40% of Pytket P runs is also a practical warning about toolchain maturity for production-grade DQC compilation.

Future Directions

• Noisy-hardware simulation. The authors plan to integrate noise simulation to directly quantify execution fidelity, moving from structural proxies to predicted success probability.
• Broadening the partitioner set. Adding more partitioning algorithms to the framework to test whether the observed trade-offs generalize.
• More faithful topology models. Extending network-topology abstractions to reflect precise physical constraints of real QPU architectures.
• Finer-grained analysis. The current study does not disaggregate results by individual benchmark and circuit instance, and some completed partitioning runs were dropped because postprocessing into the common representation timed out — both gaps the authors flag as work to close.

Target Audience

DQC compiler and toolchain researchers, quantum benchmarking practitioners, and graduate students working on distributed quantum architectures will get the most from this paper. It is also useful for systems researchers entering quantum computing who want a concrete, reproducible entry point into partitioning evaluation, and for hardware architects deciding how much inter-QPU connectivity is worth paying for. Readers seeking new partitioning heuristics will not find them here — the contribution is evaluation methodology.

Authors’ abstract

Distributed Quantum Computing (DQC) addresses the physical scaling limitations of monolithic quantum processors by networking modular Quantum Processing Units (QPUs). Efficient execution of quantum algorithms on DQC architectures requires compiling them across QPUs while minimizing inter-QPU communication bottlenecks, primarily through circuit partitioning. However, current evaluations of state-of-the-art partitioning heuristics focus primarily on the total entanglement cost of the partitions, failing to capture the broader structural and temporal overheads introduced by distributed network constraints. This paper addresses this evaluation gap by applying established monolithic benchmarking metrics to partitioned distributed circuits to quantify the performance impact of network constraints. Using an open-source, automated evaluation pipeline, we systematically assess diverse partitioning algorithms across standardized workloads and quantum network topologies. Our empirical results reveal that partitioning algorithms with comparable entanglement costs can still introduce drastically different physical execution penalties. By exposing these hidden trade-offs, such as severe increases in circuit depth and substantial reductions in gate density, this study demonstrates that comprehensive circuit-level metrics are essential for guiding the future design of DQC compilers.