⚛️ quantum physics

Advanced Scheduling Strategies for Distributed Quantum Computing Jobs

This paper proposes and evaluates a range of advanced scheduling strategies, including heuristics and reinforcement learning, to optimize the allocation of distributed quantum computing jobs across heterogeneous networks while addressing unique constraints like QPU utilization and non-local gate rates.

Original authors: Gongyu Ni, Davide Ferrari, Lester Ho, Michele Amoretti

Published 2026-03-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gongyu Ni, Davide Ferrari, Lester Ho, Michele Amoretti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, high-tech construction site. But instead of cranes and trucks, your workers are Quantum Processors (QPUs), and the materials they are building with are quantum states (like entangled particles).

In the old days, you had one giant crane. Now, you have a whole fleet of smaller cranes scattered across a city, connected by roads. Your goal is to build a massive skyscraper (a complex quantum calculation) by having all these cranes work together. This is Distributed Quantum Computing (DQC).

The problem? It's a logistical nightmare.

The Roads are Weird: The roads connecting your cranes aren't all the same. Some are smooth highways (high-quality links), and some are bumpy dirt tracks (low-quality links).
The Materials are Fragile: The "bricks" you use (entangled particles) are like soap bubbles. If you don't use them quickly, they pop (decoherence).
The Traffic is Chaotic: Jobs (construction tasks) arrive randomly. Some are small repairs; others are building entire wings of the skyscraper.

This paper is about finding the best traffic cop to manage this chaotic construction site so the skyscraper gets built as fast as possible without wasting resources.

The Core Challenge: The "Makespan"

The main goal is to minimize the Makespan. Think of this as the time from when the first truck arrives at the site until the very last brick is laid and the building is finished. You want this time to be as short as possible.

The Traffic Cop Strategies (Scheduling Algorithms)

The authors tested several different "traffic cop" strategies to see which one manages the fleet best. Here is how they work, using our construction analogy:

1. The "First-Come, First-Served" Cop (FIFO)

How it works: This cop is very rigid. He lines up the trucks in the exact order they arrived. If the first truck needs 5 cranes, he waits until 5 cranes are free, even if the second truck only needs 1 and could start immediately.
Result: It's simple, but often inefficient. The cranes sit idle while waiting for the big truck, wasting time.

2. The "Resource Maximizer" Cop (Resource-Prioritize)

How it works: This cop looks at the line and asks, "How can I get the most cranes working at the exact same time?" He groups jobs together to fill up the entire fleet, even if it means waiting a moment to find the perfect combination.
Result: Great for keeping the cranes busy (high utilization), but sometimes the waiting time to find the perfect group slows down the overall finish time.

3. The "Easy Job" Cop (EPR Scheduler)

How it works: In quantum land, some jobs need "Entangled Pairs" (EPRs)—think of these as special, fragile communication cables between cranes. Some jobs need 1 cable; others need 100. This cop prioritizes the jobs that need the fewest cables.
Why? Because jobs with fewer cables are usually faster to finish. By clearing the easy jobs first, the cop frees up space for the big, difficult jobs later.
Result: This often leads to the fairest experience for all jobs and very fast completion for the small tasks.

4. The "Smart Route" Cop (EPR + Node Selection)

How it works: This is the "Easy Job" cop, but he's also a GPS expert. He knows that some roads (links) are bumpy and slow. If a job needs a cable, he doesn't just assign any crane; he assigns the crane connected by the smoothest highway.
Result: This is the champion of the paper. By combining "do the easy jobs first" with "use the best roads," they finished the skyscraper faster than anyone else.

5. The "Dynamic" Cop (ASAP)

How it works: This cop doesn't wait for a group to form. As soon as one crane becomes free, he immediately assigns the next available job to it. He is constantly moving, never letting a crane sit idle.
Result: Very fast, but sometimes he assigns a complex job to a slow road because he was in a hurry to get it started.

6. The "AI Learner" Cop (PPO Scheduler)

How it works: This cop is an Artificial Intelligence. Instead of following a strict rulebook, he plays a video game where the goal is to finish the building fast. He tries different strategies, gets "points" (rewards) for finishing quickly, and learns from his mistakes.
Result: He is very flexible and smart. When he learns to pick the best roads (Node Selection), he performs almost as well as the "Smart Route" Cop.

The Big Takeaways

The researchers ran thousands of simulations (like running the construction site in a video game) to see who won.

The Winner: The "Smart Route" Cop (EPR with Node Selection) and the AI Learner (PPO with Node Selection) were the fastest. They proved that knowing which road to take is just as important as knowing which job to do first.
The Runner-Up: The "Dynamic" Cop (ASAP) was second best. It showed that keeping the workers busy the moment they are free is crucial.
The Lesson: In the quantum world, you can't just treat all connections as equal. If you have a mix of fast and slow connections, your scheduling strategy must take that into account.

Why This Matters

As we move toward a future where quantum computers are networked together (like a "Quantum Internet"), we won't just have one super-computer; we will have many smaller ones working together. This paper provides the rulebook for how to manage that traffic so we don't get stuck in a quantum traffic jam, ensuring we can solve complex problems (like curing diseases or designing new materials) as quickly as possible.

1. Problem Statement

Distributed Quantum Computing (DQC) aims to scale quantum computational power by interconnecting multiple Quantum Processing Units (QPUs) via a quantum network. While this offers exponential scaling potential compared to classical distributed computing, it introduces unique execution management challenges:

Quantum-Specific Constraints: Unlike classical systems, DQC relies on the generation and distribution of EPR pairs (entangled states) for non-local operations. This introduces a trade-off between entanglement generation rate and fidelity, as well as strict time limits due to decoherence.
Scheduling Complexity: The problem of scheduling DQC jobs (sub-circuits requiring multiple QPUs) is NP-hard. Traditional scheduling objectives (minimizing makespan and maximizing resource utilization) must be balanced against quantum-specific metrics like non-local gate rates and the latency associated with queued jobs.
Heterogeneity: Quantum networks often feature heterogeneous links (varying in fidelity and generation speed), requiring schedulers to make intelligent node selection decisions that classical schedulers (like FIFO) do not account for.

2. Methodology

The authors developed an integrated simulation framework using the Qoala Simulator to model the DQC workflow, from circuit compilation to execution management.

A. DQC Workflow & Network Model

Workflow: A monolithic quantum circuit is decomposed into sub-circuits (jobs) by a compiler. An Execution Manager then schedules these jobs onto a fully connected network of QPUs.
Network Model: The simulation uses a fully connected topology with heterogeneous links. Link quality is modeled using parameters such as entanglement generation cycle time, success probability, and fidelity.
Job Arrival: Jobs arrive in time slots following a truncated Poisson distribution. The simulation tracks execution times, latencies, and resource usage.

B. Performance Metrics

The study evaluates schedulers using six key metrics:

Makespan: Total time to complete a batch of jobs.
QPU Utilization: Proportion of QPU resources occupied.
Non-Local Gate Rate: A measure of the overlap in execution times for non-local gates (entanglement usage).
System Execution-Latency Performance (SELP): Geometric mean of the ratio of execution time to total latency (waiting + execution).
Fairness: Measures the variance in latency among jobs (aiming for equal treatment).

C. Proposed Scheduling Strategies

The paper proposes and benchmarks several strategies:

Resource-Prioritize: A heuristic that maximizes QPU utilization at every step by selecting subsets of jobs that use the most nodes with the shortest estimated execution time.
EPR Scheduler: Prioritizes jobs requiring fewer EPR pairs to reduce entanglement generation bottlenecks.
EPR with Node Selection: Combines the EPR priority with an algorithm that assigns jobs to the highest-quality links available, optimizing for link heterogeneity.
ASAP (As Soon As Possible): A dynamic scheduler that releases nodes immediately upon job completion and assigns pending jobs to free nodes, rather than waiting for a synchronized time slot.
PPO (Proximal Policy Optimization): A Reinforcement Learning (RL) approach.
- State: Matrix of job features (required QPUs, EPR pairs, execution time).
- Action: Probabilistic selection of jobs to execute in parallel.
- Reward: A composite function penalizing latency and incentivizing the scheduling of low-EPR jobs (and high-quality link usage in the node-selection variant).
Benchmarks: FIFO (First-In-First-Out) and LIST (List Scheduling) algorithms are used as baselines.

3. Key Contributions

Integrated Framework: Development of a comprehensive simulation environment for DQC job scheduling that incorporates quantum network physics (EPR generation, fidelity, decoherence).
Novel Scheduling Algorithms: Introduction of the EPR with Node Selection and PPO-based schedulers, which explicitly account for link heterogeneity and quantum resource constraints.
RL for Quantum Scheduling: Demonstration of using Proximal Policy Optimization to learn scheduling policies that balance makespan, latency, and resource constraints without hard-coded heuristics.
Comprehensive Evaluation: A systematic comparison of eight different scheduling strategies across varying network loads, job types (GHZ, QAOA, VQE, etc.), and link qualities.

4. Results

The simulations were run over 1,000 time slots with varying network loads ( $\lambda=4$ and $\lambda=8$ ) and job selection biases.

Makespan (Total Completion Time):
- Best Performers: EPR (Node Selection) and PPO (Node Selection) achieved the lowest makespan. By prioritizing jobs with fewer EPR requirements and assigning them to high-quality links, they minimized entanglement generation delays.
- Second Best: The ASAP scheduler performed well due to its dynamic allocation of free nodes, reducing idle time.
- Worst Performers: FIFO and basic EPR (without node selection) had higher makespans due to inefficient resource grouping and lack of link awareness.
QPU Utilization:
- ASAP and Resource-Prioritize achieved the highest utilization. ASAP maximizes usage by filling gaps immediately, while Resource-Prioritize explicitly targets maximum node saturation.
- EPR variants showed lower utilization because they often terminated parallelization early to prioritize low-EPR jobs, leaving nodes idle.
System Execution-Latency Performance (SELP) & Fairness:
- Best Performers: EPR and EPR (Node Selection) achieved the highest SELP and fairness. By prioritizing short-execution jobs and avoiding low-quality links, they ensured more consistent and faster execution for individual jobs.
- PPO variants showed strong performance but slightly trailed the EPR heuristics in fairness, likely due to the stochastic nature of the RL policy.
Non-Local Gate Rate:
- Strategies that maximize parallelization (Resource-Priority, ASAP) generally showed higher gate rates (more overlap), which is desirable for throughput but can increase contention.
- EPR-based strategies showed lower rates, indicating less contention for entanglement resources.

5. Significance and Conclusion

This paper establishes that quantum-aware scheduling is critical for the viability of Distributed Quantum Computing.

Link Heterogeneity Matters: Ignoring link quality leads to suboptimal performance. Schedulers that integrate node selection based on link fidelity (EPR + Node Selection) significantly outperform those that do not.
Trade-offs Exist: There is a fundamental trade-off between Makespan (favored by ASAP and PPO with node selection) and Fairness/Latency (favored by EPR heuristics). System designers must choose a scheduler based on whether their priority is throughput or individual job latency.
RL Potential: The PPO-based approach demonstrates that Reinforcement Learning can effectively learn complex scheduling policies in quantum networks, offering flexibility that static heuristics lack. While currently slightly behind the best heuristics in specific metrics, the RL approach provides a foundation for adaptive scheduling in dynamic, real-world quantum networks.

The work provides a blueprint for the "Execution Manager" layer in future quantum operating systems, highlighting that efficient DQC requires co-optimization of circuit compilation, network topology, and job scheduling.