arXiv:2610.25875 · International Conference on Quantum Communications, Networking, and Computing (QCNC)
Online Scheduling and Distribution of Quantum Circuits over Quantum Networks
Yukun Yang, Himanshu Gupta
Abstract
Emerging quantum networks enable distributed quantum computing (DQC) by interconnecting modest, noisy quantum processors. However, practical deployments face tight memory budgets, probabilistic entanglement generation, and decoherence, all while serving multiple users. In realistic settings -- cloud execution, iterative/interactive workloads and concurrent jobs -- circuits do not arrive in a single batch but as a stream. This creates a fundamentally online problem: the system must react to stochastic arrivals, balance latency and throughput, and remain stable under varying loads without foresight of future jobs. We study Online Scheduling and Distribution of Quantum Circuits (OS-DQC) and formalize the online scheduling problem for quantum networks: circuits arrive over time and must be executed without knowledge of future arrivals. At each event time (arrival or completion), the system decides which waiting circuits to launch and how to place their qubits, while accounting for congestion from in-flight circuits and constraints due to finite memories and decoherence. The objective is to minimize the mean completion time and makespan under these physical and resource constraints.
AI Summary
The paper studies online admission, qubit placement, and execution of quantum circuits arriving at a shared quantum network without knowledge of future jobs. It targets completion time and makespan under finite memory, probabilistic entanglement generation, link contention, and a Bell-pair decoherence deadline. An event-driven framework updates decisions at arrivals and circuit completions. Routing costs increase with unfinished entanglement demand; a prediction oracle combines heuristic qubit placement with joint batching of unfinished and newly requested entangled pairs. Three greedy admission policies are compared: FIFO with feasibility scanning, earliest predicted finish, and smallest marginal increase in the current completion-time tail. Placement is formulated as a quadratic-assignment subproblem, establishing NP-hardness even in a simplified single-circuit setting. No competitive-ratio or queue-stability guarantee is provided. Evaluation uses NetSquid simulations of 10 processors with 10 memories each, random 20–30-qubit circuits, Poisson arrivals, and a 1-second decoherence threshold. Defaults include 100 circuits and 50 gates per qubit. Across sweeps of workload size, arrival intensity, and gate count, earliest-predicted-finish generally gives the lowest online mean completion time; marginal-tail admission performs similarly, while FIFO performs worse. Results are reported qualitatively without numerical improvement factors. An offline batching comparator generally performs best, but assumes all circuits are released at time zero. The paper notes that completion predictions are approximate and oracle cost grows with evaluated candidates. Evaluation uses finite workloads; starvation prevention is suggested but not tested. Baseline placements remain fixed, with teleportation-based reassignment discussed as an extension.
Central claim may not hold: The placement and unified EP-batching algorithms underlying the prediction oracle are unspecified, leaving the claimed capacity- and decoherence-respecting execution and the simulation predictions insufficiently established. The offline GSCH comparison uses simultaneous releases rather than the online workload's Poisson release times, so its reported performance gap cannot isolate the benefit of lookahead or constitute a general lower bound for online mean flow time.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Journal reference
- Proceedings - 2026 International Conference on Quantum Communications, Networking, and Computing (QCNC), pp. 264-270 (2026)
- DOI
- 10.1109/QCNC69040.2026.00045
- Comments
- 8 pages, 5 figures. Full author version revised after acceptance; the QCNC 2026 version was shortened to meet the conference page limit