PaperlayerView exact revision on arXiv

Source-linked AI summary

EPR Count for Runtime Prediction in Distributed Quantum Computing

Fatih E. Bilgen, Ozgur B. Akan

arXiv:2609.39851v1cs.DCquant-ph

TL;DR

EPR-pair count is commonly used to measure communication cost, but its reliability as a proxy for distributed runtime has received limited direct characterization. This paper evaluates EPR cost and runtime across balanced two-QPU mappings and communication conditions. It finds that their relationship varies: equal- or lower-EPR mappings need not have equal or shorter runtimes.

  • Problem

    Although EPR cost is commonly used in distributed compilation, minimizing aggregate communication cost does not necessarily minimize runtime, and its reliability as a runtime proxy has received limited direct characterization.

    Source: §I · p. 1

  • Method

    The paper exhaustively evaluates EPR cost and runtime across balanced mappings of QFT, QAOA, and CDKM circuits, using ordering, equal-cost ambiguity, rank reversals, and EPR-minimization regret while varying latency and concurrency.

    Source: §I · p. 1

  • Results

    Across mappings, equal-EPR choices can have substantially different runtimes, lower-EPR choices can be slower, and minimum-EPR mappings can be runtime-suboptimal; 81 of 84 baseline equal-EPR groups had multiple runtimes (96.43%).

    Source: 1) Equal EPR Cost, Unequal Runtime · p. 4, §VI · p. 8

  • Takeaways & Limitations

    EPR count is useful in some workload and communication regimes, while others require explicit consideration of communication timing and execution dependencies.

    Source: §VI · p. 8

Abstract

from arXiv · show

EPR-pair consumption is commonly used as a communication-cost objective in distributed quantum computing, but minimizing EPR cost does not necessarily minimize distributed execution time. Despite its widespread use, the reliability of EPR count as a runtime surrogate has received limited direct characterization across different workloads and communication conditions. This work addresses this gap by systematically evaluating the relationship between EPR cost and runtime over all balanced two-QPU mappings of QFT, QAOA, and CDKM circuits. The results show that mappings with identical EPR cost can have substantially different execution times, lower-EPR mappings can be slower, and minimum-EPR mappings can be runtime-suboptimal. The reliability of EPR count is strongly workload dependent and also changes with the communication operating regime: increasing EPR-generation latency amplifies runtime differences hidden by equal EPR cost, while increased communication concurrency can reduce the ability of EPR count to preserve runtime ordering. These results show that EPR count and execution time are related but distinct optimization objectives, and identify regimes in which explicit communication-aware runtime modeling is necessary.

I. INTRODUCTION

The paper asks when EPR-pair count reliably predicts distributed execution time, since minimizing communication cost need not minimize runtime. It evaluates that relationship across mappings and communication regimes, building on prior work that considers both communication resources and execution time.

I. INTRODUCTION

  • EPR cost and runtime are related but distinct objectives: equal-cost mappings can run differently, and lower-cost mappings can be slower or runtime-suboptimal.The paper studies this relationship rather than proposing a new partitioning or compilation algorithm.Source: §I · p. 1
  • The study exhaustively evaluates 1,908 balanced static two-QPU mappings of QFT, QAOA, and CDKM circuits with 4–12 logical qubits.Source: §I · p. 1

II. RELATED WORK

  • Prior work considers entanglement resources and execution time, while partitioning and scheduling studies examine communication efficiency and network constraints,,, [6], [7], [8].These studies motivate distinguishing communication-resource minimization from execution-time minimization.Source: §II · pp. 1–2
  • The reliability of EPR-based ordering has received less direct characterization across circuit structures and communication regimes, motivating exhaustive mapping analysis with varied latency and concurrency.Source: §II · p. 2

III. SYSTEM MODEL AND PROBLEM FORMULATION

  • For each candidate mapping of a fixed circuit, the paper evaluates EPR communication cost and distributed execution time to formalize the proxy-reliability question.Source: §III · p. 2

A. Two-QPU Distributed Execution Model

The model uses two identical QPUs with a balanced, static mapping and distinguishes local from non-local two-qubit operations. Its baseline EPR cost counts one pair per non-local operation, while explicitly excluding several mechanisms that could change consumption.

A. Two-QPU Distributed Execution Model

  • Each QPU hosts half of the logical qubits throughout execution, and a two-qubit operation is non-local when its operands map to different QPUs.Source: A. Two-QPU Distributed Execution Model · p. 2
  • Local operations have normalized duration 1; non-local operations add EPR-generation latency, and communication concurrency limits how many may be active simultaneously.The baseline assumes unconstrained concurrency; finite Ncomm models communication contention.Source: A. Two-QPU Distributed Execution Model · p. 2

B. EPR Communication Cost

C. Execution-Time Model

The execution-time model schedules a fixed circuit dependency graph, with a mapping determining which two-qubit operations are local or non-local. Non-local operations can also be delayed by finite communication capacity.

C. Execution-Time Model

  • A circuit is represented as a fixed dependency DAG; mapping changes which two-qubit operations are local or non-local, not the dependencies.Source: C. Execution-Time Model · p. 2
  • With unconstrained communication, operations start when their predecessors finish and run for Tlocal if local or Tlocal + TEPR if non-local.Dependency-independent operations can overlap under the earliest-start scheduler.Source: C. Execution-Time Model · p. 2
  • With finite Ncomm, a non-local operation starts only when its dependencies are satisfied and a communication slot is available.The scheduler uses an earliest-feasible-start list schedule; local operations start when dependencies are ready.Source: C. Execution-Time Model · pp. 2–3
  • Equal-EPR mappings can have different runtimes when their non-local operations occupy different dependency positions, allow different overlap, or encounter different communication contention.Source: C. Execution-Time Model · p. 3

IV. EXPERIMENTAL METHODOLOGY

The study compares three quantum-circuit families using fixed canonical workloads and exhaustively enumerated balanced mappings onto two QPUs. This design isolates mapping and execution-model differences rather than recompilation effects.

A. Benchmark Circuits and Candidate Mappings

  • QFT, QAOA, and CDKM cover dense global interactions, repeated graph-defined interactions, and sequential carry propagation, respectively, at 4–12 logical qubits.QAOA uses p = 2 with seed 10; CDKM uses the full ripple-carry configuration.Source: A. Benchmark Circuits and Candidate… · p. 3
  • Each benchmark is converted to a common canonical representation, with final measurements and barriers removed before level-0 transpilation.The logical basis is an abstraction, not a native gate set for a particular hardware platform.Source: A. Benchmark Circuits and Candidate… · p. 3
  • Optimization is disabled during generation and canonical transpilation, keeping each benchmark's logical workload identical across mappings.Consequently, measured differences arise from distributed mapping and execution rather than circuit recompilation.Source: A. Benchmark Circuits and Candidate… · p. 3
  • Across the three families, 1908 candidate mappings were evaluated, with 3, 10, 35, 126, and 462 mappings per family for 4, 6, 8, 10, and 12 qubits.Exchanging QPU labels is treated as an equivalent partition, with q0 fixed to QPU 0.Source: A. Benchmark Circuits and Candidate… · p. 3
  • Exhaustive enumeration covers the complete balanced two-QPU mapping space, rather than mappings selected by a particular partitioning heuristic.Table I summarizes the resulting circuit properties, including gate counts and depth.Source: A. Benchmark Circuits and Candidate… · p. 3, Table I · p. 3

B. Scheduling and Validation

The scheduler preserves the circuit dependency structure while accounting for communication capacity. Validation checks precedence, circuit depth, and expected concurrency behavior.

B. Scheduling and Validation

  • Each mapping changes operation locality and duration while reusing the same dependency DAG for its canonical circuit.The underlying circuit dependency structure remains fixed across candidate mappings.Source: B. Scheduling and Validation · p. 3
  • With unconstrained concurrency, operations start after their predecessors finish; finite communication capacity additionally requires an available slot for non-local operations.The finite-capacity list scheduler models contention but does not seek globally optimal resource-constrained schedules.Source: B. Scheduling and Validation · p. 3
  • Validation checked DAG depths against Qiskit circuit depths and verified that generated schedules satisfy precedence constraints.Finite-capacity schedules also showed the expected monotonic behavior as communication concurrency increased.Source: B. Scheduling and Validation · pp. 3–4

C. Evaluation Metrics

The evaluation uses complementary measures to test equal-cost runtime ambiguity, overall ordering, pairwise reversals, and whether minimizing EPR cost recovers a runtime-optimal mapping.

C. Evaluation Metrics

  • Equal-cost runtime spread compares the minimum and maximum runtimes among mappings with the same EPR cost; a nonzero value reveals variation hidden by EPR count.The spread is defined relative to the minimum runtime in that equal-cost group.Source: C. Evaluation Metrics · p. 4
  • Spearman’s rank correlation ρs measures ordering agreement between EPR cost and runtime across mappings, but is undefined if either quantity is constant.Values approaching 1 indicate strong agreement between the two orderings.Source: C. Evaluation Metrics · p. 4
  • The rank-reversal fraction counts strictly comparable mapping pairs where lower EPR cost corresponds to higher runtime, excluding ties in either measure.It is the fraction of pairs satisfying the strict reversal condition.Source: C. Evaluation Metrics · p. 4
  • Best- and worst-case regret compare runtimes among minimum-EPR mappings with the global minimum: zero best regret means at least one is optimal, while positive best regret means none is.When worst regret is zero, every minimum-EPR mapping is runtime-optimal.Source: C. Evaluation Metrics · p. 4

V. RESULTS

The results section first evaluates the baseline relationship between EPR cost and runtime, then varies EPR-generation latency and communication concurrency. The baseline covers all balanced two-QPU mappings of the benchmark instances.

V. RESULTS

  • The baseline operating point uses ρEPR = 5 with unconstrained communication concurrency; further experiments vary latency and concurrency.These variations assess how EPR-cost reliability changes across communication regimes.Source: §V · p. 4

A. Baseline Relationship Between EPR Cost and Runtime

1) Equal EPR Cost, Unequal Runtime:

At ρEPR = 5, equal EPR cost often fails to identify a unique runtime, and EPR-to-runtime ordering agreement varies substantially by workload and circuit size.

1) Equal EPR Cost, Unequal Runtime:

2) Global Ordering Between EPR Cost and Runtime:

3) Strict Rank Reversals:

At ρEPR = 5, lower EPR cost can correspond to longer runtime, and minimizing EPR cost has workload-dependent consequences for recovering a runtime-optimal mapping.

3) Strict Rank Reversals:

  • QFT rank reversals rise from none for QFT-4 to 50.00% for QFT-6 and 38.81%, 41.63%, and 42.67% for QFT-8, QFT-10, and QFT-12.A reversal means the lower-EPR mapping has longer execution time; ties in either quantity are excluded.Source: 3) Strict Rank Reversals · p. 5, Figure 3 · p. 6
  • QAOA-8 through QAOA-12 have reversal fractions of 22.53%, 26.14%, and 23.54%, while CDKM-8 through CDKM-12 have 3.41%, 2.57%, and 2.28%.CDKM-6 has an 8.33% reversal fraction; QAOA-4 and QAOA-6 have none.Source: 3) Strict Rank Reversals · pp. 5–6, Figure 3 · p. 6

4) Runtime Consequences of EPR-Cost Minimization:

  • QFT best-case regret is zero, but worst-case regret reaches 20.0%, 16.4%, 38.2%, and 33.7% for QFT-6 through QFT-12.The minimum-EPR set contains a runtime-optimal mapping for each instance, but tied minimum-cost mappings can differ in runtime.Source: 4) Runtime Consequences of EPR-Cost… · p. 6, Table III · p. 6
  • QAOA-8 has 48.4% worst-case regret, while QAOA-10 and QAOA-12 have positive best-case regrets of 6.4% and 1.7%.For QAOA-10 and QAOA-12, no minimum-EPR mapping reaches the globally minimum execution time.Source: 4) Runtime Consequences of EPR-Cost… · p. 6
  • CDKM-6 through CDKM-12 have zero best- and worst-case regret, so every minimum-EPR mapping is runtime-optimal under the baseline model.CDKM-4 has zero best-case regret and 5.2% worst-case regret.Source: 4) Runtime Consequences of EPR-Cost… · p. 6
  • Minimizing EPR cost recovers the runtime optimum in some instances, leaves ambiguity among tied minima in others, and excludes the optimum in still others.For larger CDKM instances, every minimum-EPR mapping is runtime-optimal; QAOA-10 and QAOA-12 have no runtime-optimal mapping in their minimum-EPR sets.Source: 4) Runtime Consequences of EPR-Cost… · p. 6

B. Effect of EPR-Generation Latency

Equal-EPR mappings increasingly diverge in runtime as EPR-generation latency rises, with the magnitude of the effect varying by workload. QFT and QAOA show larger spreads than CDKM.

B. Effect of EPR-Generation Latency

C. Effect of Communication Concurrency

The relationship between EPR cost and runtime ordering changes with communication concurrency and workload. The implications and conclusion stress evaluating EPR-based objectives against the target architecture and, where needed, accounting for communication timing and dependencies.

C. Effect of Communication Concurrency

D. Implications for Communication-Aware DQC Compilation

  • EPR-based objectives should be evaluated for the target architecture; when runtime ambiguity or ordering violations are substantial, compilation should account for temporal information and communication resources.Source: D. Implications for… · p. 8

VI. CONCLUSION

  • Across balanced two-QPU mappings of QFT, QAOA, and CDKM, EPR minimization and runtime minimization were distinct objectives; larger systems and more detailed entanglement models remain future work.Source: §VI · p. 8
Loading 2609.39851v1…