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.
AI Summary
The paper studies routing from a fixed snapshot of entangled pairs: which resources and sequence of swapping and distillation maximize end-to-end fidelity between two users? Links carry heterogeneous Werner states, operations use ideal swapping and BBPSSW distillation, and the objective is fidelity conditioned on successful completion rather than delivery probability or throughput.
An exhaustive solver enumerates compatible binary operation trees over edge-disjoint resources. Its worst-case runtime is $m^{\Theta(m)}$ for $m$ physical pairs; this bounds the enumeration scheme, not the intrinsic complexity of optimization. Small-instance enumeration demonstrates that globally fixing purify-then-swap or swap-then-purify can miss the optimum. The proposed FOLD heuristic starts from a high-fidelity path and incorporates local detours only when distillation improves both inputs and end-to-end fidelity. Each successful merge consumes an independent cycle. For fixed candidate-path budget, its runtime is $O(r(n^2+m)+nm\log n)$, where $r=m-n+c$.
Benchmarks use small exactly solvable graphs and 261 Internet-derived topologies. On the roughly quarter of sampled topology pairs where any tested strategy improves on single-path routing, FOLD has the highest mean fidelity among the polynomial baselines. It is about four orders of magnitude faster than enumeration at circuit rank five, but has no approximation guarantee and underperforms recursive reduction on reducible graphs.
Distributional-fidelity simulations examine uncertainty; a single six-node example illustrates coordinated requests. Limitations include omitted delivery probabilities, decoherence during execution, and adaptive recovery. Multi-request findings remain a proof of concept.
Some signs of AI-generated textOverclaimsStrong assumptions
Error found: The abstract leaves unstated that FOLD's fidelity objective and principal performance comparisons are conditional on schedule success and therefore do not establish an advantage in delivery probability or unconditional performance.
The conclusion that uncertainty rather than routing effort limits delivered fidelity is supported for the tested independent-edge Gamma model and mean-fidelity routing policy, not for routing under uncertainty generally.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
54 pages, 10 figures, including supplementary information
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.
The paper studies routing from a fixed snapshot of entangled pairs: which resources and sequence of swapping and distillation maximize end-to-end fidelity between two users? Links carry heterogeneous Werner states, operations use ideal swapping and BBPSSW distillation, and the objective is fidelity conditioned on successful completion rather than delivery probability or throughput.
An exhaustive solver enumerates compatible binary operation trees over edge-disjoint resources. Its worst-case runtime is mΘ(m) for m physical pairs; this bounds the enumeration scheme, not the intrinsic complexity of optimization. Small-instance enumeration demonstrates that globally fixing purify-then-swap or swap-then-purify can miss the optimum. The proposed FOLD heuristic starts from a high-fidelity path and incorporates local detours only when distillation improves both inputs and end-to-end fidelity. Each successful merge consumes an independent cycle. For fixed candidate-path budget, its runtime is O(r(n2+m)+nmlogn), where r=m−n+c.
Benchmarks use small exactly solvable graphs and 261 Internet-derived topologies. On the roughly quarter of sampled topology pairs where any tested strategy improves on single-path routing, FOLD has the highest mean fidelity among the polynomial baselines. It is about four orders of magnitude faster than enumeration at circuit rank five, but has no approximation guarantee and underperforms recursive reduction on reducible graphs.
Distributional-fidelity simulations examine uncertainty; a single six-node example illustrates coordinated requests. Limitations include omitted delivery probabilities, decoherence during execution, and adaptive recovery. Multi-request findings remain a proof of concept.
Many quantum-network applications require end-to-end Bell pairs whose fidelity exceeds a request-specific threshold, but existing entanglement routing algorithms either optimize only throughput without regard for fidelity or enforce fidelity guarantees using centralized controllers with global link-state knowledge. We present Q-GUARD, an online entanglement routing algorithm that enforces per-request fidelity thresholds within a distributed protocol model in which nodes exchange link-state information only with their k-hop neighbors. After link outcomes are realized in each slot, Q-GUARD builds per-link purification cost tables from realized Bell pairs, allocates per-hop fidelity targets using a Werner-state equal-split rule, and selects between candidate path segments using a segment-local expected-goodput (EXG) metric that jointly accounts for swap success, purification overhead, and resource availability. We also introduce Q-GUARD-WS, an extension that exploits per-link hardware quality estimates to allocate purification effort non-uniformly across hops. On synthetic 100-node topologies with heterogeneous link fidelity and stochastic BBPSSW purification, Q-GUARD raises the qualified success rate from under 20\% to over 85\% on 4-hop paths and nearly doubles the qualified service radius in Euclidean distance relative to throughput-only and naive-purification baselines, while Q-GUARD-WS provides additional throughput gains under high hardware heterogeneity.
How to efficiently distribute entanglement over large-scale quantum networks is still an open problem that greatly depends on the technology considered. In this work, we consider quantum networks where each link is characterized by a trade-off between the entanglement generation rate and fidelity. For such networks, we look at the two following problems: the one of finding the best path to connect any two given nodes, and the problem of finding the best starting node in order to connect three nodes in the network multipartite entanglement routing. Two entanglement distribution models are considered: one where entangled qubits are distributed one at a time, and a flow model where a large number of entangled qubits are distributed simultaneously. The paper proposes of a quite general methodology that uses continuous fidelity curves (i.e., entanglement generation fidelity vs. rate) as the main routing metric. Combined with multi-objective path-finding algorithms, the fidelity curves describing each link allow finding a set of paths that maximize both the end-to-end fidelity and the entanglement generation rate. For the link models and networks considered, it is proven that the algorithm always converges to the optimal solution. It is also shown through simulation that the execution time grows polynomially with the number of network nodes (growing with a power between 1 and 1.4, depending on the network)
A path in a quantum network is a chain of repeaters that distributes entanglement between two users. Selecting a path requires balancing the rate and quality (e.g., fidelity) of the delivered entanglement, but these quantities, unlike standard routing metrics, compose non-additively. The problem is compounded by link-level configuration choices (e.g., distillation rounds or emitter brightness tuning), each trading rate against fidelity, so that a path's performance depends jointly on its route and its per-link settings. We cast this joint path selection and configuration problem as a shortest path computation on a layered graph whose layers track discretized end-to-end fidelity. A single run returns the full rate fidelity Pareto frontier, from which the path maximizing any nondecreasing utility function of rate and fidelity can be selected. We prove that for certain utility functions (including the secret key rate of BB84), the method is a fully polynomial time approximation scheme, returning a near-optimal path within a specified tolerance. We further characterize exactly when cheaper scalarization-based routing suffices: it is optimal for utility functions with convex fidelity profiles, but can be arbitrarily suboptimal otherwise (e.g., for step-like, sigmoidal utilities), whereas the layered method remains reliable in all cases.
The quantum internet enables secure communication, distributed quantum computing, and remote sensing by distributing entanglement among distant nodes [1], [2]. However, establishing end-to-end entanglement across regional networks remains challenging because quantum links experience photon loss, entanglement generation is probabilistic, quantum memories have limited coherence times, and repeater resources are constrained [2], [3]. Conventional shortest-path routing does not jointly account for these quantum-specific limitations. This paper proposes a Fidelity- and Coherence-Aware Dynamic Entanglement Routing (FCADR) framework for regional quantum internet networks. The network is modelled as a graph containing end nodes, quantum repeaters, quantum memories, and lossy entanglement links. FCADR selects routes by jointly considering estimated end-to-end fidelity, entanglement-generation and swapping success probabilities, available quantum-memory capacity, and expected distribution delay. A discrete-event simulation framework is designed to compare FCADR with shortest-path routing, link-success-based routing, and fidelity-aware routing under varying channel loss, coherence time, traffic load, and node or link failures. Performance is evaluated using end-to-end fidelity, request-success rate, distribution delay, memory utilization, and network resilience. The framework aims to improve routing decisions by incorporating quantum-state quality and resource availability into dynamic path selection.
Entanglement routing establishes entangled pairs between distant nodes of a quantum network by purifying and swapping pairs generated on elementary links. Existing methods typically restrict the decision space along two axes: the operation order, often fixed to purify-then-swap (PtS), and the purification schedule of each link, often restricted to pumping. Focusing on linear repeater chains with finite link capacities, we relax both restrictions and study the maximization of the expected end-to-end throughput subject to a fidelity threshold under two quantum-noise models. We develop a unified capacity-aware optimization framework comprising an exact mixed-integer linear program (MILP) under PtS, instantiated with either pumping or general tree purification schedules, and an exact dynamic program (DP) over arbitrary operation orders. Under symmetric Pauli noise, we prove that pumping converges to a fidelity strictly below unity, imposing a capacity-independent feasibility bound and a maximum chain length on every pumping-based PtS method, whereas general tree schedules yield a capacity-dependent bound. We further prove that post-swap purification never increases the throughput, so a free operation order can only increase feasibility. Numerical evaluations confirm the bounds: tree schedules serve over 90\% of the requests that pumping cannot at moderate fidelity thresholds; within the pumping class, a free operation order recovers much of this advantage; but once links use tree schedules, the tree-based MILP and the order-exact DP serve identical request sets throughout. Operation order and purification schedule are thus substitutes, with the purification schedule the dominant factor governing feasibility under symmetric Pauli noise.
A fully-quantum network implies the creation of quantum entanglement between a given source node and some other destination node, with a number of quantum repeaters in between. This paper tackles the problem of quantum entanglement distribution by solving the routing problem over an infrastructure based on quantum repeaters and with a finite number of pairs of entangled qubits available in each link. The network model considers that link purification is available such that a nested purification protocol can be applied at each link to generate entangled qubits with higher fidelity than the original ones. A low-complexity multi-objective routing algorithm to find the shortest path between any two given nodes is proposed and assessed for random networks, using a fairly general path extension mechanism that can fit a large family of particular technological requirements. Different types of quantum protocols require different levels of fidelity for the entangled qubit pairs. For that reason, the proposed algorithm identifies the shortest path between two nodes that assures an end-to-end fidelity above a specified threshold. The minimum requirements for the end-to-end entanglement fidelity depend on the whole extension of the paths, and cannot be looked at as a local property of each link. Moreover, one needs to keep track not only of the shortest path, but also of longer paths holding more entangled qubits than the shorter paths in order to satisfy the fidelity criterion. Thus, standard single parameter shortest-path algorithms do not necessarily converge to the optimal solution. The problem of finding the best path in a network subject to multiple criteria (known as multi-objective routing) is, in general, an NP-hard problem due to the rapid growth of the number of stored paths. This work proposes a metric that identifies and discards paths that are objectively worse than others. By doing so, the time complexity of the proposed algorithm scales near-to-linearly with respect to the number of nodes in the network, showing that the shortest-path problem in quantum networks can be solved with a complexity very close to the one of the classical counterparts. That is analytically proved for the case where all the links of a path have the same fidelity (homogeneous model). The algorithm is also adapted to a particular type of path extension, where different links along a path can be purified to different degrees, asserting its flexibility and near-to-linearity even when heterogeneous fidelities along the sections of a path are considered.