One-shot Routing in Quantum Networks
Abstract
Distributed quantum computation requires many entangled pairs to be available simultaneously, so routing must optimize fidelity from a fixed, short-lived set of network resources rather than the rate of pairs accumulated over time. We formulate this one-shot routing problem for heterogeneous Werner-state links and jointly optimize path selection and the schedule of entanglement swapping and distillation. We show that the common purify-then-swap ordering is not optimal network-wide and that exact schedule enumeration requires mΘ(m) time. We introduce Fidelity-Optimizing Local Detours (FOLD), a heuristic that starts from the highest-fidelity path and merges a detour only when distillation improves on both routes and raises end-to-end fidelity. FOLD runs in polynomial time, recovers almost all of the optimal fidelity on tractable instances, and is four orders of magnitude faster than exact optimization at circuit rank $5$. On the Internet topologies where any strategy improves on shortest-path routing, FOLD achieves the highest mean end-to-end fidelity among the polynomial baselines. We further extend the formulation to links whose fidelities are known only as distributions, where uncertainty, rather than the effort spent routing, limits the fidelity delivered. Through an example of requests competing for the same links, we show that coordination becomes a condition for feasibility, and that a shared path budget controls the fidelity trade-off between them.
Related
- Quantum utility routing in continuous-variable QKD networks with trusted and untrusted relays
- A Bi-Objective Routing Framework for Hybrid Terrestrial-Satellite Quantum Networks
- Priority-Aware Routing for Quantum Networks:Integrating Coherence-Time Constraints into Scheduling
- Efficient routing and spectrum allocation in arbitrary flex-grid entanglement networks
- Efficient routing and spectrum allocation in arbitrary flex-grid entanglement networks
BibTeX
@misc{lavi2026oneshot,
title = {{One-shot Routing in Quantum Networks}},
author = {Nadav Lavi and Nir Gutman and Ido Kaminer and Ariel Orda},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29752},
eprint = {2609.29752},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29752},
}
RIS
TY - UNPB
TI - One-shot Routing in Quantum Networks
AU - Nadav Lavi
AU - Nir Gutman
AU - Ido Kaminer
AU - Ariel Orda
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29752
UR - https://arxiv.org/abs/2609.29752
AB - Distributed quantum computation requires many entangled pairs to be available simultaneously, so routing must optimize fidelity from a fixed, short-lived set of network resources rather than the rate of pairs accumulated over time. We formulate this one-shot routing problem for heterogeneous Werner-state links and jointly optimize path selection and the schedule of entanglement swapping and distillation. We show that the common purify-then-swap ordering is not optimal network-wide and that exact schedule enumeration requires m^Θ(m) time. We introduce Fidelity-Optimizing Local Detours (FOLD), a heuristic that starts from the highest-fidelity path and merges a detour only when distillation improves on both routes and raises end-to-end fidelity. FOLD runs in polynomial time, recovers almost all of the optimal fidelity on tractable instances, and is four orders of magnitude faster than exact optimization at circuit rank $5$. On the Internet topologies where any strategy improves on shortest-path routing, FOLD achieves the highest mean end-to-end fidelity among the polynomial baselines. We further extend the formulation to links whose fidelities are known only as distributions, where uncertainty, rather than the effort spent routing, limits the fidelity delivered. Through an example of requests competing for the same links, we show that coordination becomes a condition for feasibility, and that a shared path budget controls the fidelity trade-off between them.
ER -