Optimal routing is a fundamental challenge in quantum networking, with several approaches proposed to identify the most efficient path for end-to-end (e2e) entanglement generation between pairs of nodes. In this paper, we show that prior entanglements - entanglements generated in a previous network cycle but not yet utilized - are an important consideration in optimal path selection due to the dynamic nature of quantum networks. Specifically, we investigate whether a longer path with pre-existing entanglements can outperform a shorter path that starts from scratch. We account for key quantum constraints, including noisy entanglement generation and swapping, fidelity decay, probabilistic operations, and link discarding upon swap failure. Simulations reveal that longer paths with prior entanglements can establish e2e entanglement faster than shorter paths under certain conditions. We further introduce the notion of entanglement diversity, where multiple paths can be used to improve performance - either by selecting the first successful path to minimize time or using both paths to enhance fidelity through distillation. These findings highlight the importance of incorporating prior entanglements into path selection strategies for optimizing quantum communication networks.
Optimal routing is a fundamental challenge in quantum networking, with several approaches proposed to identify the most efficient path for end-to-end (e2e) entanglement generation between pairs of nodes. In this paper, we show that prior entanglements - entanglements generated in a previous network cycle but not yet utilized - are an important consideration in optimal path selection due to the dynamic nature of quantum networks. Specifically, we investigate whether a longer path with pre-existing entanglements can outperform a shorter path that starts from scratch. We account for key quantum constraints, including noisy entanglement generation and swapping, fidelity decay, probabilistic operations, and link discarding upon swap failure. Simulations reveal that longer paths with prior entanglements can establish e2e entanglement faster than shorter paths under certain conditions. We further introduce the notion of entanglement diversity, where multiple paths can be used to improve performance - either by selecting the first successful path to minimize time or using both paths to enhance fidelity through distillation. These findings highlight the importance of incorporating prior entanglements into path selection strategies for optimizing quantum communication networks.
Quantum network communication is challenging, as the No-Cloning theorem in quantum regime makes many classical techniques inapplicable. For long-distance communication, the only viable approach is teleportation of quantum states, which requires a prior distribution of entangled pairs (EPs) of qubits. Establishment of EPs across remote nodes can incur significant latency due to the low probability of success of the underlying physical processes. To reduce EP generation latency, prior works have looked at selection of efficient entanglement-routing paths and simultaneous use of multiple such paths for EP generation.In this paper, we propose and investigate a complementary technique to reduce EP generation latency—to pre-distribute EPs over certain (pre-determined) pairs of network nodes; these pre-distributed EPs can then be used to generate EPs for the requested pairs, when needed, with lower generation latency. For such a pre-distribution approach to be most effective, we need to address an optimization problem of selection of node-pairs where the EPs should be pre-distributed to minimize the generation latency of expected EP requests, under a given cost constraint. In this paper, we appropriately formulate the above optimization problem and design two efficient algorithms, one of which is a greedy approach based on an approximation algorithm for a special case. Via extensive evaluations over the NetSquid simulator [1], we demonstrate the effectiveness of our approach and developed techniques; we show that our developed algorithms outperform a naive approach by up to an order of magnitude.
Long-distance quantum communication in quantum networks faces significant challenges due to the constraints imposed by the no-cloning theorem. Most existing quantum communication protocols rely on the a priori distribution of entanglement pairs (EPs), a process known to incur considerable latency due to its stochastic nature. In this work, we consider the problem of minimizing the latency of establishing an EP across a pair of nodes in a quantum network. While prior research has primarily focused on minimizing the expected generation latency by selecting static entanglement routes and/or swapping trees in advance, our approach considers a real-time adaptive strategy-wherein the order of entanglement-swapping operations (hence, the swapping tree used) is progressively determined at runtime based on the runtime success/failure of the stochastic events. In this context, we present a greedy algorithm that iteratively determines the best route and/or entanglement-swapping operation to perform at each stage based on the current network. We evaluate our schemes on randomly generated networks and observe a reduction in latency of up to 40% from the optimal offline approach.
While entanglement swapping enables long-distance quantum connections, it may frequently fail and introduce significant latency. Analyzing the latency of end-to-end (E2E) entanglement distribution is a critical yet not well understood problem. In this paper, we address the latency minimization problem in quantum networks at both the path and network levels. We model the stochastic behavior of entanglement swappings and provide a more accurate statistical representation of E2E latency. By proving the optimal substructure of E2E latency, we propose a Dynamic Programming (DP) algorithm to determine the optimal swapping order for path-level latency minimization. Then leveraging such path-level solution, we further formulate and solve a path-selection based optimization for network-wide latency routing problem as well. To further reduce latency, we also explore the benefits of redundant entanglement resources and propose a greedy algorithm to allocate these resources effectively. Through extensive simulations, we demonstrate the accuracy of our statistical modeling and analysis, the benefits of additional resources in reducing latency, and the superior performance of our proposed solutions over existing approaches at both the path and network levels.
Quantum network communication is challenging, as the no-cloning theorem in the quantum regime makes many classical techniques inapplicable; in particular, the direct transmission of qubit states over long distances is infeasible due to unrecoverable errors. For the long-distance communication of unknown quantum states, the only viable communication approach (assuming local operations and classical communications) is the teleportation of quantum states, which requires a prior distribution of the entangled pairs (EPs) of qubits. The establishment of EPs across remote nodes can incur significant latency due to the low probability of success of the underlying physical processes. The focus of our work is to develop efficient techniques that minimize EP generation latency. Prior works have focused on selecting entanglementpaths; in contrast, we selectentanglement swapping trees—a more accurate representation of the entanglement generation structure. We develop a dynamic programming algorithm to select an optimal swapping tree for a single pair of nodes, under the given capacity and fidelity constraints. For the general setting, we develop an efficient iterative algorithm to compute a set of swapping trees. We present simulation results, which show that our solutions outperform the prior approaches by an order of magnitude and are viable for long-distance entanglement generation.
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.
Entanglement generation in long-distance quantum networks is a difficult process due to resource limitations and the probabilistic nature of entanglement swapping. To maximize success probability, existing quantum routing algorithms employ computationally expensive solutions (e.g., linear programming) to determine which links to entangle and use for end-to-end entanglement generation. Such optimization methods, however, cannot meet the delay requirements of real-world quantum networks, necessitating swift yet efficient real-time optimization models. In this paper, we propose reinforcement learning (RL)-based models to determine which links to entangle and proactively swap to meet connection requests. We show that the proposed RL-based approach is 20x faster compared to linear programming. Moreover, we show that one can take advantage of the longevity of entanglements to (i) cache entangled links for future use and (ii) proactively swap entanglement on high-demand path segments, thereby increasing the likelihood of request success. Through comprehensive simulations, we demonstrate that caching unused entanglements leads to a 10-15% improvement in the performance of state-of-the-art quantum routing algorithms. Complementing caching with proactive entanglement swapping further enhances the request success rate by up to 52.55%.