Optimal routing in quantum-repeater networks requires finding the best path that connects a pair of end nodes. Most previous work on routing in quantum networks assumes utility functions that are isotonic, meaning that the ordering of two paths does not change when extending both with the same edge. However, we show that utility functions that take into account both the rate and quality of the entanglement generation (e.g., the secret-key rate) are often non-isotonic. This makes pathfinding difficult as classical algorithms such as Dijkstra's become unsuitable, with the state of the art for quantum networks being an exhaustive search over all possible paths. In this work we present improved algorithms. First, we present two best-first-search algorithms that use destination-aware merit functions for faster convergence. One of these provably finds the best path, while the other uses heuristics to achieve an effectively sublinear scaling of the query count in the network size while in practice always finding a close-to-optimal path. Second, we present metaheuristic algorithms (simulated annealing and a genetic algorithm) that enable tuning a tradeoff between path quality and computational overhead. While we focus on swap-ASAP quantum repeaters for concreteness, our algorithms are readily generalized to different repeater schemes and models.
Optimal routing in quantum-repeater networks requires finding the best path that connects a pair of end nodes. Most previous work on routing in quantum networks assumes utility functions that are isotonic, meaning that the ordering of two paths does not change when extending both with the same edge. However, we show that utility functions that take into account both the rate and quality of the entanglement generation (e.g., the secret-key rate) are often non-isotonic. This makes pathfinding difficult as classical algorithms such as Dijkstra's become unsuitable, with the state of the art for quantum networks being an exhaustive search over all possible paths. In this work we present improved algorithms. First, we present two best-first-search algorithms that use destination-aware merit functions for faster convergence. One of these provably finds the best path, while the other uses heuristics to achieve an effectively sublinear scaling of the query count in the network size while in practice always finding a close-to-optimal path. Second, we present metaheuristic algorithms (simulated annealing and a genetic algorithm) that enable tuning a tradeoff between path quality and computational overhead. While we focus on swap-ASAP quantum repeaters for concreteness, our algorithms are readily generalized to different repeater schemes and models.
Optimal routing in quantum-repeater networks requires finding the best path that connects a pair of end nodes. Most previous work on routing in quantum networks assumes utility functions that are isotonic, meaning that the ordering of two paths does not change when extending both with the same edge. However, we show that utility functions that take into account both the rate and quality of the entanglement generation (e.g., the secret-key rate) are often non-isotonic. This makes pathfinding difficult as classical algorithms such as Dijkstra's become unsuitable, with the state of the art for quantum networks being an exhaustive search over all possible paths. In this work we present improved algorithms. First, we present two best-first-search algorithms that use destination-aware merit functions for faster convergence. One of these provably finds the best path, while the other uses heuristics to achieve an effectively sublinear scaling of the query count in the network size while in practice always finding a close-to-optimal path. Second, we present metaheuristic algorithms (simulated annealing and a genetic algorithm) that enable tuning a tradeoff between path quality and computational overhead. While we focus on swap-ASAP quantum repeaters for concreteness, our algorithms are readily generalized to different repeater schemes and models.
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.
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.
With the emergence of the Quantum Internet, the need for advanced quantum networking techniques has significantly risen. Various models of quantum repeaters have been presented, each delineating a unique strategy to ensure quantum communication over long distances. We focus on repeaters that employ entanglement generation and swapping. This revolves around establishing remote end-to-end entanglement through repeaters, a concept we denote as the “quantum-native” repeaters (also called “first-generation” repeaters in some literature). The challenges in routing with quantum-native repeaters arise from probabilistic entanglement generation and restricted coherence time. Current approaches use synchronized time slots to search for entanglement-swapping paths, resulting in inefficiencies. Here, we propose a new set of asynchronous routing protocols for quantum networks by incorporating the idea of maintaining a dynamic topology in a distributed manner, which has been extensively studied in classical routing for lossy networks, such as using a destination-oriented directed acyclic graph or a spanning tree. The protocols update the entanglement-link topology asynchronously, identify optimal entanglement-swapping paths, and preserve unused direct-link entanglements. Our results indicate that asynchronous protocols achieve a larger upper bound with an appropriate setting and significantly higher entanglement rate than existing synchronous approaches, and the rate increases with coherence time, suggesting that it will have a much more profound impact on quantum networks as technology advances.
The quantum internet enables distribution of quantum states across distant nodes, supporting secure communication, distributed computing, and quantum sensing. Unlike classical networks, it is constrained by the no cloning theorem, probabilistic entanglement generation, decoherence, and hardware drift, making classical abstractions inadequate. Scalable quantum networking therefore requires new architectures, protocols, and optimisation methods that explicitly account for these limitations.
This thesis studies the architecture, routing, and operation of quantum networks under realistic constraints, focusing on bipartite entanglement distribution over quantum repeater networks. Key metrics include end to end fidelity, throughput, scalability, and fairness. At the network layer, routing strategies are developed beyond assumptions of homogeneous nodes and full network knowledge. Routing under heterogeneous repeater efficiencies shows how partial knowledge of node quality improves fidelity and reduces path blocking. A grey box routing approach is then introduced, where path selection relies only on topology and end to end estimates, achieving robustness and fairness without detailed link information.
At the link layer, calibration and hardware drift are addressed through a calibration aware model separating activation and calibration phases. For linear repeater chains, an optimal calibration schedule is derived to balance operation time and calibration overhead. This is extended to general topologies with shared links, where a greedy orchestration heuristic is proposed.
Finally, the thesis connects network protocols with hardware via an instruction set architecture for programmable quantum repeater nodes based on NV centers, enabling coherent programmability and linking physical operations to higher layer protocols.