PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Reproducible Evaluation of Distributed Quantum Circuit Partitioning Algorithms

Javier Vela-Tambo, Davud Azizov, Tian Guo

arXiv:2608.27099v1quant-phcs.DC

TL;DR

Distributed quantum computing requires partitioning circuits across networked QPUs, but entanglement-only evaluations omit structural and temporal execution overheads. The paper introduces a reproducible pipeline that applies circuit-level metrics to distributed partitions and finds substantially different penalties among algorithms with similar e-bit costs.

  • Problem

    Existing DQC partitioning evaluations focus on total entanglement cost, leaving structural and temporal overheads insufficiently captured.

  • Method

    The paper applies established monolithic circuit metrics to distributed partitions using an open-source automated pipeline, standardized workloads, and configurable topologies.

  • Results

    Partitioning algorithms with comparable median e-bit counts can produce substantially different depth inflation and gate-density degradation.

  • Takeaways & Limitations

    Evaluating DQC partitioners requires structure-aware metrics alongside entanglement cost to capture distributed-circuit executability.

  • Takeaways & Limitations

    Results are not disaggregated by individual benchmark and circuit instance, and some completed runs were excluded after postprocessing timed out.

Abstract

from arXiv · show

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.

I. INTRODUCTION

DQC addresses monolithic processor scaling by networking QPUs, but partitioning introduces communication overheads that existing e-bit-focused evaluations do not fully capture. This work provides a reproducible, metric-rich evaluation methodology for exposing those penalties.

  • Motivation: DQC networks modular QPUs to address physical scaling constraints in monolithic NISQ processors.Distributed operation also introduces hardware, synchronization, memory, and entanglement-management challenges.
  • Motivation: Circuit partitioning maps monolithic circuits onto networked QPUs while minimizing inter-QPU communication caused by remote operations.The problem becomes difficult because distributed execution depends on communication across physically separate processors.
  • Evaluation gap: Existing evaluations emphasize total entanglement cost, leaving structural and temporal overheads from distributed network constraints insufficiently measured.The paper identifies this as a significant evaluation gap.
  • Contribution: The study adapts monolithic benchmarking metrics to partitioned circuits using standardized workloads and an open-source evaluation pipeline.The released framework includes code, benchmarks, and partitioned circuits for reproducibility.
  • Findings: Partitioners with comparable entanglement costs can produce different structural penalties, including increased depth and reduced gate density.The paper attributes reduced gate density to qubits remaining inactive during network routing.

A. Distributed Quantum Computing Primitives

Distributed circuit execution uses entanglement-assisted teleportation to implement non-local operations, while partitioning heuristics approximate an NP-hard mapping problem. Different methods emphasize time-sliced, global, or multilevel graph strategies and may optimize state and gate teleportation differently.

  • DQC primitives: Non-local operations consume shared EPR-pair entanglement, commonly measured in e-bits, through state or gate teleportation.State teleportation relocates a data-qubit state between QPUs using local operations and classical communication.
  • DQC primitives: Gate teleportation implements non-local controlled operations without moving the control qubit through cat-entangler and cat-disentangler primitives.The EJPP protocol also supports gate packing, allowing multiple gates to reuse one e-bit.
  • Execution overheads: Teleportation adds local operations, measurements, classical communication, circuit depth, latency, and qubit idling that can increase decoherence susceptibility.These effects extend beyond the entanglement cost itself.
  • Partitioning methods: Circuit partitioning is typically handled by classical heuristics because the partitioning and qubit-mapping problems are NP-hard.Exact optimization becomes intractable as circuit depth and qubit count grow.
  • Partitioning methods: FGP maps circuits one time-slice at a time, hypergraph methods optimize global edge cuts and gate packing, and multilevel methods jointly optimize state and gate teleportation.These approaches form the primary graph-based baselines evaluated in the study.
  • Alternative methods: Other approaches explore simulated annealing, Tabu search, and deep reinforcement learning for assignments or routing under heterogeneous distributed hardware constraints.

C. Quantum Circuit Benchmarking

Established quantum benchmark suites provide structural metrics for monolithic circuits, whereas distributed partitioning studies primarily report entanglement cost and classical runtime. This paper ports those metrics into distributed circuit evaluation.

  • Existing benchmarks: QASMBench and SupermarQ are established benchmark suites for evaluating quantum software and optimization frameworks.QASMBench uses OpenQASM routines and introduces metrics including gate density, retention lifespan, and entanglement variance.
  • Evaluation gap: These benchmark suites remain focused on monolithic circuits, while partitioning algorithms are evaluated mainly by total e-bit cost and classical runtime.The separation leaves distributed structural behavior outside the usual evaluation scope.
  • Proposed evaluation: The evaluation pipeline ingests and decomposes monolithic OpenQASM circuits, distributes them across a specified topology, and profiles original and distributed versions.A YAML configuration controls the pipeline to support reproducible experiments.
  • Proposed evaluation: The paper bridges this gap by applying established structural metrics directly to distributed circuit partitions.

III. EVALUATION DESIGN & METHODOLOGY

The study uses an automated pipeline and varied workloads to compare partitioning across distributed settings. The benchmark collection spans structured, randomized, and non-uniform circuits with different implications for routing and teleportation.

  • Evaluation pipeline: The automated pipeline decomposes OpenQASM circuits, partitions them onto target network topologies, and profiles both monolithic and distributed outputs.YAML configuration files control execution for repeatable experiments.
  • Circuit benchmarks & workloads: Workloads combine QASMBench circuits with regenerated circuits based on Burt et al.’s methodology to cover diverse algorithmic structures.The generated workloads span 16 to 96 qubits.
  • Circuit benchmarks & workloads: The QFT benchmark creates heavy non-local routing with O(n^2) communication overhead while retaining regular gate structure suitable for gate-teleportation evaluation.
  • Circuit benchmarks & workloads: QAOA circuits use naturally commuting interactions that permit gate reordering and provide a test of how well partitioners exploit circuit structure.The evaluation uses QAOA circuits with 50% edge probability.
  • Circuit benchmarks & workloads: Quantum Volume circuits alternate randomized single- and two-qubit gate blocks with random qubit permutations, providing an intermediate structure between regular and fully random circuits.
  • Circuit benchmarks & workloads: CP-fraction circuits randomly pair qubits for two-qubit gates, making their non-uniform structure unfavorable to state-teleportation-only partitioning.

B. Partitioning Algorithms

The evaluation covers three families of state-of-the-art partitioning algorithms, unified through a wrapper that standardizes circuit inputs and distributed outputs.

  • Algorithm families: Three algorithm families are evaluated using open-source software frameworks provided by their authors.
  • Algorithm families: The study evaluates MLFM-R, FGP-rOEE, and three Pytket-DQC variants: P, PE, and ESD.MLFM-R and FGP-rOEE are implemented in DISQCO, while the Pytket variants are implemented in Pytket-DQC.
  • Unified evaluation: A unified wrapper ingests Qiskit-decomposed circuits, executes each partitioner, and exports distributed circuits in a common format.The exported format includes the gates and measurements required for remote operation.

C. Network Topologies

The evaluation compares four inter-QPU configurations—linear, grid, and fully connected networks—under explicit qubit-capacity and execution-time constraints.

  • Inter-QPU configurations: The study evaluates 4-QPU linear, 4-QPU grid, 2-QPU fully connected, and 4-QPU fully connected networks.Linear networks connect immediate neighbors, grid networks connect horizontal and vertical neighbors, and fully connected networks link every QPU directly.
  • Capacity and assumptions: Each QPU receives ⌈nq/k⌉+1 qubits, where nq is the total circuit-qubit count and k is the number of QPUs.The additional qubit provides auxiliary capacity for non-local teleportation primitives.
  • Capacity and assumptions: Intra-QPU connectivity is fully connected, so interactions within a module incur no internal routing penalties.An abstraction layer translates the evaluated topologies into DISQCO and Pytket-DQC network definitions.
  • Execution constraint: All partitioning executions use a 600-second timeout enforced by the evaluation wrapper.

D. Evaluation Metrics

The evaluation combines direct partitioning costs with standard and structure-aware circuit metrics, analyzing changes between monolithic and distributed circuits.

  • Direct and standard metrics: Direct costs include e-bit count and partitioning execution time, while standard properties include width, depth, and gate count.E-bit count measures remote entanglement-pair consumption, and execution time captures classical compiler overhead.
  • Structural metrics: Structural metrics measure gate density, retention lifespan, liveness, parallelism, entanglement ratio, and entanglement variance.These features capture occupancy, qubit activity and noise exposure, concurrency, entangling-gate prevalence, and interaction concentration.
  • Comparative analysis: Metrics are reported as absolute values, ratios, and deltas between monolithic and distributed circuits.All metrics are extracted from Qiskit’s Directed Acyclic Graph circuit representation.
  • Correlation analysis: The correlation matrix maps input circuit properties against DQC partitioning costs and structural penalties using Spearman correlations.Darker shades indicate stronger correlations; missing entries are non-significant or below |r| < 0.20.

IV. RESULTS & ANALYSIS

The results quantify DQC partitioning overheads using only circuit instances that completed successfully within the timeout across compared methods and applicable topologies.

  • Comparison criteria: Reported comparisons include only circuit instances completing successfully within the timeout for all compared partitioners and, where applicable, network topologies.
  • Execution status: 90.4% and 81.5% completion rates were achieved by MLFM-R and FGP-rOEE, respectively.FGP-rOEE’s remaining overhead was driven almost entirely by partitioning timeouts at 17.3%.
  • Execution status: Approximately 33–34% success rates were observed for Pytket variants, mainly limited by postprocessing and partitioning timeouts.Postprocessing timeouts reached 57.4% for Pytket P, while partitioning timeouts reached 35.9% for Pytket ESD.
  • Execution status: Failure rates remained low, at no more than 7.9%, across all evaluated methods.

A. Replication Analysis

The evaluation pipeline reproduces published e-bit costs across benchmark workloads and examines how partitioning overhead varies with circuit properties and network topology.

  • Replication: Reproduced e-bit counts for MLFM-R, FGP-rOEE, and Pytket variants closely track published values across CP, QAOA, QFT, and QV benchmarks.The comparison covers 2-QPU and 4-QPU fully connected inter-QPU networks.
  • Multidimensional evaluation: The evaluation contrasts e-bit cost, circuit depth ratio, ∆gate density, and ∆entanglement variance across partitioning methods.These metrics are presented as grouped box plots in Fig. 4.
  • Predictors: Gate count (r = 0.88) and parallelism (r = 0.84) are the strongest predictors of communication overhead.Entanglement variance significantly reduces communication overhead (r = −0.55).
  • Structural penalties: Non-local teleportation primitives reduce gate density through qubit waiting, with a correlation of r = −0.81.The correlation analysis links remote-operation overhead to reduced utilization and gate density.
  • Network topology: The topology comparison measures e-bit cost across linear, grid, and fully connected 4-QPU networks and partitioning methods.Fig. 5 focuses on how network topology changes partitioning cost.

C. The Cost of Distribution and Network Connectivity

Distribution creates structural and temporal costs beyond e-bit consumption, while restricted network connectivity further increases communication overhead through multi-hop routing.

  • Structural overheads: Comparable median e-bit counts can produce substantially different circuit-depth inflation across partitioning methods.MLFM-R inflates circuit depth more than Pytket-ESD despite comparable median e-bit counts.
  • Structural overheads: All evaluated algorithms reduce gate density, but the degradation varies widely and is most pronounced for FGP-rOEE.These differences show that e-bit minimization does not capture all distribution penalties.
  • Network connectivity: Linear 4-QPU topology significantly increases e-bit consumption relative to fully connected topology because partitioning requires multi-hop routing.Fig. 5 compares linear, grid, and fully connected networks.
  • Conclusion: Similar e-bit costs can still entail expanded circuit depth, reduced gate density, and longer qubit lifetimes.The conclusion identifies these as structural penalties missed by evaluating total entanglement cost alone.
Loading 2608.27099v1…