EPR Count for Runtime Prediction in Distributed Quantum Computing

EPR Count for Runtime Prediction in Distributed Quantum Computing Fatih E. Bilgen∗ , Ozgur B. Akan∗† ∗ Centre for neXt Communications (CXC), Electrical Engineering Division, Department of Engineering,

University of Cambridge, Cambridge, UK † Centre for neXt Communications (CXC), Department of Electrical and Electronics Engineering,

arXiv:2609.39851v1 [cs.DC] 30 Sep 2026

Koç University, Istanbul, Turkey Email: {feb49, oba21}@cam.ac.uk

Abstract—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 communicationaware runtime modeling is necessary. Index Terms—distributed quantum computing, quantum circuit partitioning, communication-aware compilation, quantum circuit scheduling, EPR-pair consumption

I. I NTRODUCTION Distributed quantum computing (DQC) seeks to scale quantum computation by executing a quantum algorithm across multiple interconnected quantum processing units (QPUs). When logical qubits participating in the same two-qubit operation reside on different QPUs, the corresponding operation becomes non-local and requires inter-QPU communication, typically supported through shared entanglement, local operations, measurements, and classical communication [1]. Circuit partitioning therefore determines which interactions become non-local and strongly influences the communication requirements of distributed execution. A common objective in distributed compilation is to reduce the number of non-local interactions or the entanglement resources required to realize them. Several partitioning and compilation approaches use non-local gate count, teleportation cost, or EPR-pair consumption as measures of communication efficiency [2], [3]. However, minimizing aggregate communication cost does not necessarily minimize runtime. Runtime

also depends on where non-local operations occur within the circuit dependency structure, whether they can overlap, the latency of entanglement generation, and the availability of communication resources. These observations motivate the central question of this work: When is EPR-pair count a reliable proxy for distributed quantum execution time? Our results show that EPR count can be a strong runtime indicator in some workload and communication regimes, while in others equal or lower EPR cost can correspond to substantially different or even longer execution times. This work studies EPR-pair consumption as a runtime surrogate rather than proposing a new partitioning or compilation algorithm. The main contributions are as follows: • We characterize the relationship between EPR cost and runtime over alternative mappings of the same quantum circuit using rank correlation, equal-cost runtime ambiguity, rank reversals, and EPR-minimization regret. • We exhaustively evaluate balanced static two-QPU mappings of QFT, QAOA, and CDKM circuits with 4–12 logical qubits, yielding 1908 candidate mappings. • We characterize how proxy quality changes with EPRgeneration latency and finite communication concurrency, showing that its reliability depends jointly on circuit structure and the communication operating regime. II. R ELATED W ORK Communication cost has long been a central objective in distributed quantum compilation. Researchers in [4] already considered both entanglement-resource consumption and execution time, while the compiler framework in [5] combines partitioning and remote-operation scheduling with EPRconsumption and delay considerations. At the same time, increasingly sophisticated partitioning methods continue to target entanglement efficiency. For example, the temporally extended hypergraph formulation in [3] accounts for multiple teleportation mechanisms while minimizing entanglement consumption. These works motivate an important distinction between minimizing communication resources and minimizing execution time. A complementary line of research shows that runtime depends strongly on how communication demand interacts with

the underlying execution resources. Network-aware scheduling under finite communication capacity is studied in [6], where the benefit of scheduling depends on available communication resources and the degree of entanglement parallelism exposed by the circuit. The subsequent benchmarking study in [7] further shows that end-to-end latency emerges from the interaction between workload structure and network conditions. More recently, architecture-aware compilation in [8] explicitly considers both EPR-pair consumption and communication runtime, reflecting the broader move toward joint computation– communication optimization. Although prior work increasingly considers communication cost and execution time jointly, the validity of EPR count itself as a runtime surrogate has received less direct characterization. In particular, it remains important to understand whether EPRbased ordering of alternative mappings is preserved across different circuit structures and communication operating regimes. This work addresses this question through exhaustive mapping analysis while varying EPR-generation latency and communication concurrency, thereby identifying conditions under which EPR minimization is sufficient and conditions under which explicit runtime-aware modeling becomes necessary.

duration, whereas local operations consume no communication capacity. The baseline execution model assumes unconstrained communication concurrency, while finite Ncomm is used to model communication contention.

III. S YSTEM M ODEL AND P ROBLEM F ORMULATION

Each canonical circuit is represented as a directed acyclic graph (DAG), G = (V, E), where each node v ∈ V represents one gate occurrence and each directed edge (u, v) ∈ E represents an immediate precedence constraint. The dependency graph is fixed for a given circuit; a mapping π changes which two-qubit operations are local or non-local, but does not alter the circuit dependencies. Under mapping π, the duration of a circuit operation is ( Tlocal , if v is local, dπ (v) = (5) Tlocal + TEPR , if v is non-local.

For a fixed canonical circuit C, let Π(C) denote the set of candidate mappings of its logical qubits onto two QPUs. For each mapping π ∈ Π(C), we evaluate its EPR communication cost CEPR (π) and distributed execution time Tdist (π). We formalize the question introduced in Section I as ?

arg min CEPR (π) = arg min Tdist (π). π∈Π(C)

(1)

π∈Π(C)

The remainder of this section defines the communication and execution models used to evaluate this relationship. A. Two-QPU Distributed Execution Model We consider two identical QPUs and a balanced, static logical-qubit mapping π : {q0 , . . . , qNq −1 } → {0, 1},

(2)

B. EPR Communication Cost Let NNL (π) denote the number of canonical two-qubit operations whose operands are assigned to different QPUs under mapping π. In the baseline model, each such operation is assumed to consume one EPR pair, giving CEPR (π) = NNL (π).

This controlled abstraction isolates aggregate entanglement demand from the temporal effects that determine execution time. It does not account for mechanisms that can alter EPR consumption, such as EPR reuse, pre-generation, or multi-gate teleportation. In the remainder of this work, EPR cost refers specifically to EPR-pair count under the controlled assumption of one EPR pair per non-local canonical two-qubit operation. C. Execution-Time Model

We first consider unconstrained communication concurrency. Each operation starts as soon as all of its predecessors have completed. Denoting its start and finish times by s(v) and f (v), respectively, s(v) =

max

f (u),

(6)

f (v) = s(v) + dπ (v),

(7)

u∈Pred(v)

where Nq is the number of logical qubits and each QPU hosts Nq /2 qubits throughout execution. A two-qubit operation acting on qi and qj is local when π(qi ) = π(qj ) and nonlocal when π(qi ) ̸= π(qj ). All single-qubit operations and local two-qubit operations are assigned the normalized duration Tlocal = 1. Let TEPR denote the additional latency associated with generating the entanglement required for a non-local operation. Its cost relative to local computation is characterized by ρEPR =

TEPR . Tlocal

(3)

Communication concurrency is represented by Ncomm , defined as the maximum number of non-local operations that may be active simultaneously. Each non-local operation occupies one communication slot for its full non-local-operation

(4)

where Pred(v) denotes the set of predecessors of circuit operation v, and s(v) = 0 for source nodes. The resulting distributed execution time is the circuit runtime, Tdist (π) = max f (v). v∈V

(8)

Finite communication concurrency extends this model by allowing a non-local operation to start only when both its circuit dependencies and a communication slot are available. Let r(v) = max f (u) (9) u∈Pred(v)

denote the dependency-ready time of operation v, with r(v) = 0 for source nodes. Local operations start at s(v) = r(v). For

a non-local operation, if ak denotes the availability time of its assigned communication slot, the start time becomes s(v) = max{r(v), ak }.

(10)

The finish time and runtime remain defined by (7) and (8), respectively. This formulation separates aggregate EPR consumption from its temporal consequences. Two mappings with the same CEPR may therefore produce different runtimes if their nonlocal operations occur at different positions in the dependency graph, admit different degrees of overlap, or experience different communication contention. IV. E XPERIMENTAL M ETHODOLOGY A. Benchmark Circuits and Candidate Mappings We evaluate three benchmark families with distinct interaction and dependency structures: the Quantum Fourier Transform (QFT), the Quantum Approximate Optimization Algorithm (QAOA), and the Cuccaro–Draper–Kutin–Moulton (CDKM) ripple-carry adder. QFT exhibits dense and increasingly global two-qubit interactions, QAOA contains graph-defined interactions repeated across algorithmic layers, whereas CDKM exhibits a strongly sequential carrypropagation structure. For each family, circuits with Nq ∈ {4, 6, 8, 10, 12} logical qubits are considered. The QAOA instances use p = 2 with seed 10, while CDKM uses the full ripple-carry configuration. The circuits are generated using the target-independent interface of MQT Bench [9] to avoid assumptions about a particular processor topology or native gate set. Each benchmark is transformed into a common canonical representation before distributed mapping. Final measurements and barriers are removed, and the remaining circuit is transpiled with optimization level 0 into the logical basis Bcan = {u, cp},

(11)

where u denotes a generic single-qubit operation and cp a controlled-phase two-qubit operation. This basis serves only as a common logical abstraction and is not intended to represent the native gate set of a specific hardware platform. Optimization is disabled both during benchmark generation and canonical transpilation. The objective is not to obtain a gate-count-optimal implementation, but to preserve a deterministic circuit representation across all candidate mappings. Hence, mappings of the same benchmark are evaluated against an identical logical workload, so differences in communication cost and execution time arise from the distributed mapping and execution model rather than from circuit recompilation. Table I summarizes the resulting circuits, where Ng , N1q , and N2q denote the total, single-qubit, and two-qubit gate counts, respectively, and D denotes circuit depth. For each canonical circuit, we exhaustively enumerate balanced static mappings onto two identical QPUs according to the model in Section III-A. Because exchanging the labels of the two QPUs produces an equivalent partition, q0 is fixed

TABLE I S TRUCTURAL PROPERTIES OF THE CANONICAL BENCHMARK CIRCUITS

Benchmark

Nq

Ng

N1q

N2q

D

QFT-4 QFT-6 QFT-8 QFT-10 QFT-12

4 6 8 10 12

28 48 72 100 132

16 24 32 40 48

12 24 40 60 84

13 17 21 25 29

QAOA-4 QAOA-6 QAOA-8 QAOA-10 QAOA-12

4 6 8 10 12

24 60 108 186 252

20 46 80 134 180

4 14 28 52 72

11 17 37 49 59

CDKM-4 CDKM-6 CDKM-8 CDKM-10 CDKM-12

4 6 8 10 12

69 135 201 267 333

52 102 152 202 252

17 33 49 65 81

47 91 135 179 223

to QPU 0 to remove this symmetry. The resulting number of unique mappings is     Nq − 1 1 Nq Nmap (Nq ) = = . (12) Nq /2 − 1 2 Nq /2 For Nq ∈ {4, 6, 8, 10, 12}, this gives 3, 10, 35, 126, and 462 mappings per benchmark family, respectively. Across the three families, the study therefore evaluates 1908 candidate mappings. For every candidate, the canonical circuit remains unchanged while the logical-qubit grouping determines which two-qubit operations become non-local. Exhaustive enumeration ensures that subsequent EPR-cost and runtime comparisons cover the complete balanced two-QPU mapping space rather than the output of a particular partitioning heuristic. B. Scheduling and Validation For each canonical circuit, the dependency DAG defined in Section III-C is constructed once and reused across all candidate mappings. Each mapping π changes only the local or non-local classification of two-qubit operations and, consequently, their mapping-dependent durations; the underlying dependency structure remains unchanged. Under unconstrained communication concurrency, the annotated DAG is evaluated using a deterministic earliest-start scheduler. Each operation begins as soon as all of its predecessors have completed, allowing dependency-independent operations to overlap. For finite Ncomm , the scheduler is extended to an earliest-feasible-start list scheduler, in which a non-local operation may begin only when both its dependencies are satisfied and a communication slot is available. This finite-capacity scheduler provides a controlled model of communication contention and is not intended to solve the globally optimal resource-constrained scheduling problem. The implementation was validated against analytically tractable test circuits and the benchmark suite. DAG depths were checked against the corresponding Qiskit circuit depths,

generated schedules were verified to satisfy all precedence constraints, and finite-capacity schedules exhibited the expected monotonic behavior with increasing communication concurrency. C. Evaluation Metrics To assess the reliability of EPR cost as a runtime proxy, we consider complementary measures that capture ambiguity among equal-cost mappings, global ordering, pairwise ordering violations, and the optimization consequence of minimizing EPR consumption. First, we investigate whether equal EPR costs can hide different runtimes. For mappings sharing the same EPR cost, the relative runtime spread is defined as Sequal =

Tmax − Tmin , Tmin

(13)

where Tmin and Tmax are the minimum and maximum runtimes within the equal-cost group. A nonzero Sequal therefore captures runtime variation that is invisible to EPR count alone. Next, we examine whether EPR cost preserves the overall runtime ordering of candidate mappings. For this, Spearman’s rank correlation coefficient ρs is computed between CEPR (π) and Tdist (π) over all mappings of the same circuit. Values approaching 1 indicate strong agreement between the EPRcost and runtime orderings. The coefficient is undefined when either quantity is constant across all candidate mappings. Then, we analyze whether lower EPR cost can correspond to higher runtime. A strict pairwise rank reversal occurs between mappings πi and πj when (Ci − Cj )(Ti − Tj ) < 0,

(14)

where Ci = CEPR (πi ) and Ti = Tdist (πi ). The rank-reversal fraction Frev is the fraction of strictly comparable mapping pairs satisfying (14), excluding ties in either EPR cost or runtime. Finally, we examine whether minimizing EPR cost recovers a runtime-optimal mapping. Let E = arg min CEPR (π), π∈Π(C)

T ∗ = min Tdist (π), π∈Π(C)

(15)

where E is the set of minimum-EPR mappings and T ∗ is the globally minimum execution time. If TEmin and TEmax denote the best and worst runtimes within E, the corresponding regrets are TEmin − T ∗ , T∗ max ∗ T −T worst REPR = E ∗ . T best REPR =

(16) (17)

best Thus, the regret values distinguish three cases. If REPR = worst REPR = 0, every minimum-EPR mapping is also runtimebest worst optimal. If REPR = 0 but REPR > 0, at least one minimumEPR mapping is runtime-optimal, but EPR cost alone cannot identify which minimum-cost mapping to choose. Finally, if best REPR > 0, no minimum-EPR mapping achieves the globally minimum execution time.

V. R ESULTS We first characterize the relationship between EPR cost and distributed execution time at the baseline operating point ρEPR = 5 under unconstrained communication concurrency. We then vary EPR-generation latency and communication concurrency to determine how the reliability of EPR cost changes across communication operating regimes. A. Baseline Relationship Between EPR Cost and Runtime The baseline experiment evaluates all 1908 balanced twoQPU mappings of the 15 benchmark instances. We first examine whether mappings with identical EPR cost can nevertheless exhibit different distributed execution times. 1) Equal EPR Cost, Unequal Runtime: Fig. 1 shows the relative runtime spread of every EPR-cost group containing at least two candidate mappings. Across the complete baseline dataset, 84 such multi-candidate equal-EPR groups are observed. Of these, 81 exhibit more than one execution time, corresponding to an ambiguity rate of 96.43%. Equal-EPR runtime ambiguity occurs in 13 of the 15 benchmark instances, showing that identical aggregate EPR consumption generally does not uniquely determine distributed execution time. The magnitude of this ambiguity also varies substantially across circuit families and instances. The largest observed spread occurs for QAOA-8: five mappings with CEPR = 12 produce execution times ranging from 62 to 92, giving Sequal = 48.39%. Large spreads are also observed for QAOA10 and QFT-12, where the most pronounced equal-cost groups reach 44.79% and 43.33%, respectively. Table II summarizes the five largest equal-EPR runtime spreads observed in the baseline experiment. These results demonstrate that equal EPR count alone is insufficient to distinguish the execution times of mappings that incur the same communication cost. TABLE II L ARGEST EQUAL -EPR RUNTIME SPREADS AT ρEPR = 5

Instance QAOA-8 QAOA-10 QFT-12 QAOA-8 QFT-12

CEPR Group size Tmin Tmax 12 30 42 16 54

5 36 180 9 32

62 96 90 72 99

92 139 129 102 139

Sequal 48.39% 44.79% 43.33% 41.67% 40.40%

2) Global Ordering Between EPR Cost and Runtime: We next examine whether EPR cost preserves the overall runtime ordering of candidate mappings. Fig. 2 reports Spearman’s rank correlation coefficient ρs between CEPR and Tdist for each benchmark instance. The results reveal markedly different ordering behavior across the three circuit families. For QFT, the ordering agreement becomes weak beyond the smallest instance. While QFT-4 gives ρs = 1, the coefficient falls to 0 for QFT-6 and remains between 0.128 and 0.176 for the 8–12-qubit instances. Thus, for the larger QFT circuits, ordering candidate mappings by EPR cost provides little agreement with their runtime ordering.

QFT CDKM QAOA

Relative runtime spread

50%

40%

30%

20%

10%

0

2

-1

-1 CD KM

-8

CD KM

CD KM

-4

-6 CD KM

2

CD KM

0

AO A1 Q

AO A1

Q

AO A8 Q

AO A6 Q

AO A4

2

Q

Q

FT -1

0 FT -1 Q

FT -8 Q

FT -6 Q

Q

FT -4

0%

Benchmark instance Fig. 1. Relative runtime spread among mappings sharing the same EPR cost at ρEPR = 5. Each marker represents one EPR-cost group containing at least two mappings. A nonzero value indicates that mappings with identical EPR consumption produce different distributed execution times.

Spearman rank correlation, ρs

QAOA exhibits an intermediate behavior. The two smallest instances show strong agreement, with ρs = 1 for QAOA4 and ρs = 0.965 for QAOA-6. For the larger instances, however, the correlation decreases to 0.594, 0.550, and 0.615 for 8, 10, and 12 qubits, respectively. EPR cost therefore retains a positive association with runtime ordering for these instances, but does not reproduce that ordering closely. In contrast, CDKM shows increasingly strong agreement as the circuit size grows. The correlation increases from ρs = 0.500 at four qubits to 0.815 at six qubits, and then reaches

QFT

CDKM

QAOA

6

8

10

1.0 0.8 0.6 0.4 0.2 0.0 4

12

Number of logical qubits, Nq Fig. 2. Spearman rank correlation between EPR cost and distributed execution time at ρEPR = 5. Values closer to 1 indicate stronger agreement between the EPR-cost and runtime orderings of candidate mappings.

0.943, 0.966, and 0.976 for the 8-, 10-, and 12-qubit instances, respectively. For the larger CDKM circuits, EPR cost therefore provides a close approximation to the runtime ordering of the candidate mappings. Overall, the baseline results show that the global ordering agreement between EPR cost and execution time is strongly dependent on the benchmark family and circuit size. EPR count can closely preserve runtime ordering in some instances, particularly the larger CDKM circuits, while providing only weak ordering information for others, most notably the larger QFT circuits. 3) Strict Rank Reversals: We next examine whether the ordering induced by EPR cost can be strictly incorrect for individual mapping pairs. Fig. 3 reports the strict rank-reversal fraction Frev , defined over candidate pairs that are not tied in either EPR cost or execution time. The QFT instances exhibit the largest reversal fractions. No reversal is observed for QFT-4, but Frev reaches 50.00% for QFT-6 and remains high for the larger instances, with values of 38.81%, 41.63%, and 42.67% for 8, 10, and 12 qubits, respectively. Thus, for a substantial fraction of strictly comparable QFT mapping pairs, the lower-EPR mapping is not the faster one. QAOA exhibits fewer reversals than QFT but still shows a pronounced departure from EPR-based ordering for the larger instances. No strict reversals occur for QAOA-4 or QAOA-6, whereas the reversal fraction increases to 22.53%, 26.14%, and 23.54% for QAOA-8, QAOA-10, and QAOA-12, respectively. CDKM again displays a substantially stronger correspondence between EPR cost and execution time. Its reversal fraction is 0 for CDKM-4, 8.33% for CDKM-6, and decreases to 3.41%, 2.57%, and 2.28% for the 8-, 10-, and 12-qubit

instances. Consequently, strict ordering violations become relatively rare for the larger CDKM circuits. These results strengthen the conclusion obtained from the global rank-correlation analysis. Weak correlation is not caused only by ties or small changes in ordering: for QFT and the larger QAOA instances, lower EPR cost can directly correspond to longer execution time. However, the frequency of such reversals remains strongly dependent on the benchmark family.

Strict rank-reversal fraction, Frev

QFT

CDKM

QAOA

50%

CDKM shows the strongest agreement between EPR minimization and runtime minimization. CDKM-4 has zero bestcase regret and a modest worst-case regret of 5.2%, while all larger CDKM instances have zero best- and worst-case regret. Hence, for CDKM-6 through CDKM-12, every minimum-EPR mapping is also runtime-optimal under the baseline model. Overall, the optimization consequence of using EPR cost is therefore workload dependent. In some instances, minimizing EPR cost is sufficient to recover the runtime optimum; in others, ties among minimum-EPR mappings leave substantial runtime ambiguity, while in still others the minimum-EPR set itself excludes the runtime-optimal mapping. TABLE III B EST- AND WORST- CASE RUNTIME REGRET AMONG MINIMUM -EPR best , Rworst ) IN MAPPINGS AT ρEPR = 5. E ACH ENTRY REPORTS (REPR EPR PERCENT.

40% 30%

Nq Family

20%

4

6

8

10

12

QFT (0, 0) (0, 20.0) (0, 16.4) (0, 38.2) (0, 33.7) QAOA (0, 0) (0, 0) (0, 48.4) (6.4, 17.0) (1.7, 8.7) CDKM (0, 5.2) (0, 0) (0, 0) (0, 0) (0, 0)

10% 0%

B. Effect of EPR-Generation Latency 4

6

8

10

12

Number of logical qubits, Nq Fig. 3. Strict rank-reversal fraction between EPR cost and distributed execution time at ρEPR = 5. A reversal occurs when the mapping with lower EPR cost has the longer execution time. Ties in either quantity are excluded.

4) Runtime Consequences of EPR-Cost Minimization: Finally, we examine whether minimizing EPR cost recovers a runtime-optimal mapping. Table III reports the best- and worst-case runtime regrets within the set of minimum-EPR mappings. The two quantities distinguish whether the runtime optimum is contained in the minimum-EPR set and, when multiple minimum-cost mappings exist, how much their execution times may differ. For QFT, the best-case regret is zero for every instance, indicating that the minimum-EPR set always contains at least one runtime-optimal mapping. However, the worst-case regret becomes substantial for the larger instances, reaching 20.0%, 16.4%, 38.2%, and 33.7% for QFT-6 through QFT-12, respectively. Thus, although EPR minimization can recover the runtime optimum for these instances, EPR cost alone cannot reliably distinguish among tied minimum-cost mappings. QAOA exhibits both forms of mismatch. QAOA-4 and QAOA-6 have zero best- and worst-case regret, whereas QAOA-8 retains zero best-case regret but exhibits the largest worst-case regret in the baseline study, 48.4%. More importantly, QAOA-10 and QAOA-12 have positive best-case regrets of 6.4% and 1.7%, respectively. For these two instances, no minimum-EPR mapping achieves the globally minimum execution time.

We next examine how EPR-generation latency affects the discrepancy between EPR cost and distributed execution time. Keeping the benchmark circuits, candidate mappings, and unconstrained communication model fixed, we vary the normalized EPR-generation latency over ρEPR ∈ {0, 0.25, 0.5, 1, 2, 5, 10, 20}. At each operating point, all 1908 candidate mappings are reevaluated. The case ρEPR = 0 serves as a zero-communication-penalty reference, while increasing ρEPR progressively raises the runtime contribution of each non-local operation. To isolate the effect of latency from EPR count, we focus on mappings with identical EPR cost and measure their relative runtime spread. This directly captures how increasing EPR-generation latency amplifies runtime differences that are invisible to EPR count. Fig. 4 reports, for each benchmark instance, the maximum relative runtime spread Sequal among equal-EPR mapping groups. At ρEPR = 0, the spread is zero for every instance because local and non-local operations have identical durations. Once communication incurs a nonzero latency penalty, however, mappings with the same EPR count can exhibit different execution times, and this discrepancy generally grows as the EPR-generation latency penalty increases. The effect is strongest for QFT and QAOA. For QFT12, the maximum equal-EPR spread increases from 7.0% at ρEPR = 0.25 to 43.3% at the baseline operating point ρEPR = 5, reaching 51.8% at ρEPR = 20. QFT-10 follows a similar trend, increasing from 6.4% to 45.3% over the sampled positive-latency range. The largest growth occurs for QAOA-8, whose maximum spread rises from 3.9% at ρEPR = 0.25 to 48.4% at ρEPR = 5

Maximum relative spread, max Sequal

Nq = 4

Nq = 6

Nq = 8

(a) QFT

Nq = 10

Nq = 12

(b) QAOA

(c) CDKM

100%

100%

100%

80%

80%

80%

60%

60%

60%

40%

40%

40%

20%

20%

20%

0%

0% 0

5

10

15

20

0% 0

EPR-latency ratio, ρEPR

5

10

15

20

0

EPR-latency ratio, ρEPR

5

10

15

20

EPR-latency ratio, ρEPR

Fig. 4. Maximum relative runtime spread Sequal among mappings with equal EPR cost as a function of normalized EPR-generation latency. Subfigures (a)–(c) correspond to QFT, QAOA, and CDKM, respectively; curves denote circuit size Nq .

Spearman rank correlation, ρs

Nq = 4

Nq = 6

Nq = 8

(a) QFT

Nq = 10

Nq = 12

(b) QAOA

(c) CDKM

1.0

1.0

1.0

0.8

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0.0

0.0

0.0

1

2

4

Concurrency, Ncomm

6

1

2

4

Concurrency, Ncomm

6

1

2

4

6

Concurrency, Ncomm

Fig. 5. Spearman rank correlation ρs between EPR cost and distributed execution time as a function of communication concurrency Ncomm at ρEPR = 5. Subfigures (a)–(c) correspond to QFT, QAOA, and CDKM, respectively; curves denote circuit size Nq .

and 87.6% at ρEPR = 20. QAOA-10 and QAOA-12 also show substantial growth, reaching maximum spreads of 56.7% and 60.2%, respectively, at the largest sampled latency. CDKM exhibits the same qualitative trend but with considerably smaller magnitudes; its largest observed spread is 19.3%, for CDKM-10 at ρEPR = 20. These results show that EPR-generation latency can amplify runtime differences that are completely invisible to EPR count. Importantly, the magnitude of this amplification is workload dependent: equal-EPR mappings remain comparatively similar in runtime for CDKM, whereas QFT and especially QAOA can

diverge substantially as the EPR-generation latency penalty increases. C. Effect of Communication Concurrency We finally examine how communication concurrency affects the reliability of EPR cost as a runtime proxy. Keeping ρEPR = 5 fixed, we limit the number of simultaneous nonlocal operations to Ncomm ∈ {1, 2, 4, 6}. Since changing communication concurrency primarily affects the amount of overlap available between non-local operations, we use the Spearman rank correlation ρs to measure how well EPR cost preserves the global runtime ordering of candidate mappings.

Fig. 5 shows that the effect of communication concurrency is strongly workload dependent. The largest change occurs for QFT. Under highly serialized communication, EPR cost provides a comparatively strong ordering of candidate runtimes; for example, QFT-12 has ρs ≈ 0.90 at Ncomm = 1. As additional communication concurrency becomes available, the correlation deteriorates substantially, reaching approximately 0.13 at Ncomm = 6. QFT-6 exhibits an even more pronounced change, with its correlation falling to zero for the higherconcurrency settings. QAOA shows the same general tendency for its larger instances, although the degradation is less severe. QAOA-8, QAOA-10, and QAOA-12 all exhibit lower rank correlation as communication concurrency increases, whereas the smaller QAOA instances remain strongly correlated. In contrast, CDKM is comparatively insensitive to additional concurrency: apart from CDKM-4, the correlations remain high and nearly unchanged across the tested concurrency settings. These results indicate that stronger communication serialization can make EPR count a better predictor of execution time. When non-local operations are forced to execute more sequentially, makespan becomes more strongly related to their total number. As communication concurrency increases, nonlocal operations can overlap, making runtime increasingly dependent on their temporal placement, dependencies, and critical-path structure. D. Implications for Communication-Aware DQC Compilation The combined results indicate that EPR count should not be treated as a universally architecture-independent optimization objective. Its reliability depends jointly on circuit dependency structure, EPR-generation latency, and the amount of communication concurrency available during execution. Consequently, the suitability of an EPR-based partitioning objective should be evaluated together with the execution architecture for which the circuit is being compiled. For workloads and operating regimes in which EPR count closely preserves runtime ordering, EPR minimization provides a simple and effective communication-aware objective. In regimes with substantial runtime ambiguity or frequent ordering violations, however, compilation should incorporate temporal information such as the placement of non-local operations in the dependency graph, critical-path effects, and the communication resources available for overlapping nonlocal operations. These observations are particularly relevant to emerging modular quantum processors and quantum data-center architectures, where interconnect latency and the number of simultaneously available communication channels are expected to evolve alongside processor scale. Changes in these architectural capabilities can alter which circuit mappings are preferable even when their EPR costs remain unchanged. The methodology developed here can therefore be used to assess whether EPR-based objectives remain adequate as distributed quantum architectures and compilation strategies evolve.

VI. C ONCLUSION This work examined when EPR-pair count provides a reliable surrogate for distributed quantum execution time. Rather than proposing a new partitioning algorithm, we evaluated the relationship between EPR cost and runtime directly by exhaustively considering balanced two-QPU mappings of QFT, QAOA, and CDKM benchmark circuits. The results show that minimizing aggregate EPR consumption and minimizing execution time are related but distinct objectives. Mappings with identical EPR cost can exhibit substantially different runtimes, lower-EPR mappings can execute more slowly than higher-EPR alternatives, and in some instances the minimumEPR set does not contain the runtime-optimal mapping. The results further show that the reliability of EPR count is not an intrinsic property of the cost metric alone, but depends jointly on the workload and the communication architecture. Under the evaluated model, EPR count can provide a useful communication-cost objective in some regimes, while other regimes require explicit consideration of communication timing and execution dependencies. This distinction is particularly relevant to communication-aware compilation for modular and networked quantum processors, where evolving interconnect latency and concurrency can change the relationship between entanglement consumption and execution time. Future work can extend this characterization to larger multiQPU systems, more detailed entanglement-generation models, and compilation mechanisms such as multi-gate teleportation. ACKNOWLEDGMENTS Fatih E. Bilgen’s work was supported by the TUBITAK BIDEB 2213-A Scholarship. R EFERENCES [1] M. Caleffi, M. Amoretti, D. Ferrari, D. Cuomo, J. Illiano, A. Manzalini, and A. S. Cacciapuoti, “Distributed quantum computing: A survey,” Computer Networks, vol. 254, p. 110672, Dec. 2024. [2] E. Kaur, S. Pouryousef, H. Shapourian, J. Zhao, M. Kilzer, R. Kompella, and R. Nejabati, “Optimized quantum circuit partitioning across multiple quantum processors,” IEEE Transactions on Quantum Engineering, vol. 6, pp. 1–17, 2025. [3] F. Burt, K.-C. Chen, and K. K. Leung, “Entanglement-efficient distribution of quantum circuits over large-scale quantum networks,” in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 01, Aug. 2025, pp. 1111–1122. [4] D. Cuomo, M. Caleffi, K. Krsulich, F. Tramonto, G. Agliardi, E. Prati, and A. S. Cacciapuoti, “Optimized compiler for distributed quantum computing,” ACM Transactions on Quantum Computing, vol. 4, no. 2, pp. 15:1–15:29, Feb. 2023. [5] D. Ferrari, S. Carretta, and M. Amoretti, “A modular quantum compilation framework for distributed quantum computing,” IEEE Transactions on Quantum Engineering, vol. 4, pp. 1–13, 2023. [6] S. Pouryousef, R. Nejabati, D. Towsley, R. Kompella, and E. Kaur, “Network-aware scheduling for remote gate execution in quantum data centers,” Apr. 2025, arXiv:2504.20176. [7] S. Pouryousef, E. Kaur, H. Shapourian, D. Towsley, R. Kompella, and R. Nejabati, “Benchmarking quantum data center architectures: A performance and scalability perspective,” Jan. 2026, arXiv:2601.01353. [8] C.-T. Kuo, F. Burt, S. Y.-C. Chen, K. K. Leung, and K.-C. Chen, “Architecture-aware reinforcement learning for communication-efficient distributed quantum circuit compilation,” Aug. 2026, arXiv:2608.06892. [9] N. Quetschlich, L. Burgholzer, and R. Wille, “MQT Bench: Benchmarking software and design automation tools for quantum computing,” Quantum, vol. 7, p. 1062, July 2023.

Related documents

• EPR Count for Runtime Prediction in Distributed Quantum Computing#1145018
• Observational Indistinguishability and Integrity Blind Regions in Hybrid Quantum-Classical Workflows#1123537
• Observational Indistinguishability and Integrity Blind Regions in Hybrid Quantum-Classical Workflows#919245
• Distinct Feedback-Strength Requirements for Quantum-State Ensemble Preparation under Channel-Equivalent Monitoring#1105779
• A quantum thermal machine surpassing the classical thermodynamic limit on precision#1132350