Dynamic Entanglement Packet Scheduling for Quantum Networks

Source: arXiv:2605.28795 · Published 2026-05-27 · By Quang-Phong Tran, Claudio Cicconetti, Marco Conti, Andrea Passarella

TL;DR

This paper addresses the critical challenge of efficiently scheduling entanglement distribution in scalable quantum networks with multiple user applications. Prior approaches rely on static, periodic schedules computed offline via algorithms like Earliest Deadline First (EDF), which do not adapt to the intrinsic stochasticity of quantum entanglement generation and asynchronous request arrivals. The authors propose a novel dynamic, online EDF-like scheduler that reacts in real-time to request arrivals and entanglement packet generation outcomes—making decisions to admit, defer, retry, or drop packet generation attempts (PGAs) based on current network conditions and deadlines. Through detailed simulations on a realistic large-scale network topology (the GARR Italian research network), the dynamic scheduler achieves substantially improved performance compared to the static baseline, including higher completion ratios, lower makespan, and better throughput, especially under high load and when requests target higher reliability (ppacket). Moreover, the dynamic scheduler gracefully degrades under overload by deferring or dropping infeasible requests, while the static approach abruptly fails admission control under contention. This work highlights the advantages of runtime adaptability in scheduling quantum entanglement distribution to better handle stochastic link-layer behaviors and asynchronous multi-user demand.

Key findings

• The dynamic scheduler achieves near 100% completion ratio across all target reliability levels ppacket tested (0.1 to 0.9), while the static scheduler's completion ratio declines at low ppacket due to unhandled failures (Fig. 4).
• The static scheduler admission rate drops sharply beyond 250 concurrent applications at ppacket ≥ 0.6, while the dynamic scheduler admits more requests via online deferral and dropping mechanisms (Fig. 3).
• Makespan remains stable for the dynamic scheduler regardless of ppacket, but increases for the static scheduler at low ppacket due to retry failures (Fig. 4).
• Under increasing load (50 to 300 apps) with dynamic arrivals and ppacket=0.3, the dynamic scheduler maintains high completion ratio (≥84%) and throughput plateaus due to bottleneck link saturation (Fig. 5).
• Per-link waiting time increases sharply for the static scheduler as ppacket and budget duration grow, while the dynamic scheduler manages link waiting times more effectively via deferrals and early completions.
• Longer path lengths correlate with lower completion ratios and higher drop rates in the dynamic scheduler, reflecting increased contention on concurrently reserved links for multi-hop entanglement (Fig. 5).
• The overhead of the dynamic scheduler is O(log ne + log nr + |πa|) per event, with bounded retries and deferrals preventing starvation (Algorithm 1).
• The model to map target reliability ppacket to PGA duration Ba based on binomial success approximations enables a principled time budget allocation for probabilistic entanglement generation.

Threat model

n/a — The paper does not consider adversarial threats or security assumptions but focuses on scheduling optimization under stochastic quantum link-layer conditions.

Methodology — deep read

The paper assumes a quantum network modeled as an undirected graph G=(V,E) with nodes representing quantum devices connected by quantum links capable of direct entanglement generation. Each link can attempt multiple independent entanglement generation trials per slot with success probability pgen, and entanglement swapping between links occurs with independent Bell State Measurement success probability pbsm. The authors focus on end-to-end (E2E) entanglement distribution requests from applications, each defined by source/destination pairs, number of entanglement packets (Ia) needed in a session, packet sizes (qa E2E pairs), and periodic arrival times with deadlines (Ta periods). They adopt the recent packet-generation attempt (PGA) abstraction, where each PGA allocates a time budget Ba composed of discrete slots (duration τ) during which entanglement generation attempts occur. The minimum number of slots n' to achieve a target success probability ppacket that the PGA produces at least qa E2E pairs is computed by binomial cumulative distribution inversion (eq. 3-5).

They consider a centralized controller with global knowledge that computes schedules for PGAs. The baseline static scheduler computes a repetitive offline schedule for a hyper-period (least common multiple of application periods) using EDF, guaranteeing contention-free feasible schedules on the conflict graph of applications sharing links. However, this offline schedule is not responsive to asynchronous arrivals or stochastic outcomes.

The proposed dynamic scheduler operates online with event queues tracking new PGAs arrivals, completions, failures, and deferrals. It uses an EDF-like priority on earliest deadline PGAs and handles runtime decisions: schedules PGAs immediately if resources and deadlines permit; defers PGAs if resources are busy but deadlines remain feasible; retries failed PGAs if sufficient time remains before the deadline; otherwise, drops PGAs. It exploits early completion feedback to free resources and permit opportunistic scheduling of deferred PGAs.

Simulations use the 48-node 62-link GARR network topology with applications requesting 100 PGAs of size 2 E2E pairs each, period 1s, slot duration 0.1ms, per-link entanglement generation pgen=0.001 and Bell state measurement success pbsm=0.6. Paths are shortest paths. Experiments vary ppacket from 0.1 to 0.9 and number of concurrent applications from 50 to 300. They use paired runs to compare static and dynamic schedulers on the same admitted sets.

Metrics recorded include admission rate (feasibility of schedules), completion ratio (fraction of PGAs completed), makespan (time from first arrival to last completion), throughput (PGAs completed per time unit), per-link utilization, and waiting time.

Each simulation is averaged over 200 runs with 95% confidence intervals. The dynamic scheduler's runtime complexity per event is dominated by log factors for priority queue updates and linear in path length for link availability checks. The scheduler prevents starvation by dropping PGAs that cannot meet deadlines, bounding event rates.

A toy example illustrates runtime rescheduling, deferral, retries, and early completion benefits. The evaluation demonstrates how the dynamic approach better adapts to quantum stochasticity and asynchronous requests, improving performance and resource utilization compared to the static baseline.

No code release or frozen weights are mentioned. The simulator is Python-based. Some physical-layer details and memory imperfections are abstracted away for tractability.

Technical innovations

• An online EDF-like scheduler that dynamically admits, defers, retries, or drops entanglement packet generation attempts (PGAs) based on runtime link availability and deadline feasibility, improving adaptivity over static offline schedules.
• A novel probabilistic model mapping target PGA success reliability (ppacket) to minimum time budget allocation (Ba) using binomial cumulative probabilities of multi-slot E2E entanglement generation trials.
• Integration of early completion feedback to immediately free reserved resources upon PGA success, enabling opportunistic scheduling of deferred PGAs and improving throughput under stochastic quantum link outcomes.
• A complexity-bounded algorithm (Algorithm 1) combining event-driven priority queues and real-time link resource reservation for scalable scheduling within large quantum network topologies with multi-hop paths and contention.

Datasets

• GARR network topology — 48 nodes, 62 links — public Italian research network topology used in prior quantum network scheduling research

Baselines vs proposed

• Static EDF scheduler: completion ratio ≈ 85% at ppacket=0.1 vs dynamic scheduler: near 100% completion ratio across ppacket range (Fig. 4).
• Static scheduler admission rate drops to near 0% at 250 applications and ppacket ≥ 0.6 vs dynamic scheduler admission rate not explicitly quantified but implied better via online deferral (Fig. 3).
• Static scheduler makespan increases with decreasing ppacket (due to failures) vs dynamic scheduler keeps makespan nearly constant across ppacket (Fig. 4).
• Per-link waiting time at bottleneck links grows significantly for static scheduler with growing ppacket but remains lower under dynamic scheduler (Fig. 4).
• Dynamic scheduler throughput increases with load and ppacket until saturating due to bottleneck nodes at ~200 applications (Fig. 5).

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2605.28795.

Fig 1: A quantum network with a central controller that coordinates 5 nodes.

Fig 2: A toy example comparing the static (top) and dynamic (bottom) schedulers, where 3 applications a request one entanglement packet (∀a ∈A, Ia = 1)

Fig 3: The static scheduler admission rate of feasible schedules vs. ppacket.

Fig 4: Comparison between the static and dynamic schedulers: the left figure shows the completion ratio (top) and makespan (bottom) in logarithmic scale

Fig 5: Performance on the load and the path length of the dynamic scheduler: the left figure shows the completion ratio and throughput according to an

Fig 6 (page 7).

Fig 7 (page 7).

Limitations

• Simplifying assumptions exclude minimum fidelity requirements, classical signal latencies, and detailed physical-layer timing effects in entanglement success probability estimation.
• Quantum memory imperfections are abstracted: generated E2E entangled pairs are assumed to remain coherent until end of PGA, but no carryover or degradation across PGAs is modeled.
• Routing is fixed as shortest path per application; joint routing and scheduling under contention is not addressed and left for future work.
• The impact of heterogeneous application request characteristics and link variability is not evaluated; all applications are homogeneous in packet size, deadline, and arrival.
• No adversarial threats or security analysis are considered since this is a scheduling/optimization focused work.
• Simulation-based evaluation; no experimental validation on quantum hardware or testbeds yet.

Open questions / follow-ons

• How would heterogeneous application demands (varying packet sizes, deadlines, reliability targets) impact the performance and complexity of the dynamic scheduler?
• Can joint routing and scheduling approaches be integrated to jointly optimize path selection to avoid contention bottlenecks in multi-hop quantum networks?
• What are the effects of more realistic quantum memory imperfections, decoherence, and classical signaling latencies on scheduler performance?
• How could fairness mechanisms be designed to mitigate biases against longer-path applications and provide quality-of-service guarantees?

Why it matters for bot defense

While this paper addresses quantum network entanglement scheduling rather than traditional bot defense or CAPTCHA design, it provides valuable insights into managing resource contention, stochastic success, and asynchronous request arrivals in highly constrained, probabilistic distributed systems. Bot-defense engineers can draw parallels for designing adaptive scheduling and admission control policies that respond dynamically to uncertain and bursty workloads rather than relying on static, offline resource allocations. The dynamic scheduler’s ability to defer, retry, and drop requests based on current system state echoes online rate-limiting and prioritization strategies that can improve responsiveness and throughput under load. Additionally, the methodical modeling of probabilistic success and deadline feasibility constraints offers a rigorous approach to balancing reliability targets with finite resource budgets—analogous to balancing user challenge cost vs bot detection efficacy in CAPTCHA systems. Although quantum network specifics differ, the core scheduler design principles exemplify how to build flexible, event-driven resource management to gracefully degrade under saturation, which is pertinent for any critical online service where workloads and success rates vary unpredictably.

Cite

@article{arxiv2605_28795,
  title={ Dynamic Entanglement Packet Scheduling for Quantum Networks },
  author={ Quang-Phong Tran and Claudio Cicconetti and Marco Conti and Andrea Passarella },
  journal={arXiv preprint arXiv:2605.28795},
  year={ 2026 },
  url={https://arxiv.org/abs/2605.28795}
}

Read the full paper

• arXiv:2605.28795 (abstract)
• arXiv:2605.28795 (PDF)