Hybrid terrestrial-satellite quantum networks combine terrestrial fiber infrastructure with free-space links to enable long-distance entanglement distribution. Entanglement can be routed over different combinations of terrestrial and satellite links, resulting in paths with different entanglement generation rates (EGRs) and fidelities. Existing routing algorithms, however, typically reduce routing to a single-objective problem by optimizing either EGR or fidelity, or by optimizing one while constraining the other, and thus do not explicitly capture the trade-off between the two. In this paper, we present a bi-objective routing framework for hybrid quantum networks that jointly optimizes end-to-end EGR and fidelity. We formulate routing as a Pareto optimization problem and show that it possesses a special mathematical structure: the bottleneck nature of end-to-end EGR and the multiplicative nature of end-to-end fidelity allow the problem to be transformed into a MAXMIN-MINSUM bi-criterion path problem. This transformation enables the exact polynomial-time computation of a minimal complete Pareto set using Martins' bicriterion routing algorithm. Our results demonstrate that hybrid networks expose substantially richer Pareto frontiers than terrestrial-only networks and that the proposed framework outperforms representative single-objective routing policies by allowing applications to select paths based on their EGR and fidelity requirements.
Hybrid terrestrial-satellite quantum networks combine terrestrial fiber infrastructure with free-space links to enable long-distance entanglement distribution. Entanglement can be routed over different combinations of terrestrial and satellite links, resulting in paths with different entanglement generation rates (EGRs) and fidelities. Existing routing algorithms, however, typically reduce routing to a single-objective problem by optimizing either EGR or fidelity, or by optimizing one while constraining the other, and thus do not explicitly capture the trade-off between the two. In this paper, we present a bi-objective routing framework for hybrid quantum networks that jointly optimizes end-to-end EGR and fidelity. We formulate routing as a Pareto optimization problem and show that it possesses a special mathematical structure: the bottleneck nature of end-to-end EGR and the multiplicative nature of end-to-end fidelity allow the problem to be transformed into a MAXMIN-MINSUM bi-criterion path problem. This transformation enables the exact polynomial-time computation of a minimal complete Pareto set using Martins' bicriterion routing algorithm. Our results demonstrate that hybrid networks expose substantially richer Pareto frontiers than terrestrial-only networks and that the proposed framework outperforms representative single-objective routing policies by allowing applications to select paths based on their EGR and fidelity requirements.
In the era of 6G and beyond, space-aerial-terrestrial quantum networks (SATQNs) are poised to advance the development of a global-scale quantum Internet. These networks leverage free space optical satellite and aerial quantum networks to complement optical fiber-based terrestrial quantum networks to enable the distribution of high-fidelity quantum entanglement over long distances. However, establishing multi-hop end-to-end quantum entanglement remains highly challenging, not only due to time-varying link conditions and structural heterogeneity inherent in SATQNs, but also because noise in quantum channels and imperfections in quantum operations can degrade the quality of entanglement. To address this challenge, we formulate an optimization problem that maximizes SATQN throughput by jointly optimizing routing path selection and entanglement generation rates (PS-EGR) while ensuring high entanglement fidelity. The resulting problem is a mixed-integer linear programming (MILP) formulation, which is NP-hard. We propose a Benders’ decomposition (BD)-based approach to solve this problem efficiently. Specifically, the MILP is decomposed into a master problem for binary routing path selection and a subproblem for continuous entanglement generation rate optimization. Numerical results validate the effectiveness of the proposed PS-EGR scheme, offering critical insights into the optimization and deployment of SATQNs.
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)
Quantum Information networks (QIN) aim to interconnect quantum systems via quantum repeaters through end-to-end entanglement of qubits. The integration of both satellites and ground segments is essential to provide global connectivity, even over large distances. In this paper, we study the problem of entanglement routing in large-scale quantum networks -i.e., with a large number of nodes, with a hybrid space-ground architecture. We decompose the routing problem into two subcomponents: request scheduling and path selection, and structure our approach around two phases: a proactive and a reactive step. We design and implement an entanglement routing strategy in an emulated European quantum network, first in a custom Python-based simulator for performance forecasting, and then into the NetSquid quantum network simulator. Our work thus provides a tool allowing for a comparison between terrestrial and satellite segments in terms of successful end-to-end entanglement in a large-scale network and shows that both segments are required for optimal service. Our results indicate that, within the emulated European topology, terrestrial networks can support end-toend entanglement for approximately 35% of user pairs -the remaining pairs are too distant and suffer from prohibitive losses. In contrast, the satellite-based network achieves connectivity for up to 91% of user pairs, although some pairs remain unreachable due to a lack of simultaneous satellite visibility. However, while satellites can outperform terrestrial networks in total photon distribution, they may not be suitable for lowlatency requests if out of visibility, making ground networks essential. This highlights the complementary roles of space and terrestrial segments in quantum networking.
Satellite-based quantum networks leverage the advantageous properties of optical signals from satellites to ground stations, to enable the distribution of high-fidelity quantum entanglements over vast distances, thus circumventing the limitations of traditional terrestrial-based systems. However, the satellite-based entanglement distribution coupled with terrestrial quantum swapping in the space-terrestrial integrated network becomes very complex when considering the joint optimization with satellite assignment, resource allocation, and path selections. To tackle this issue, we introduce a hybrid quantum-classical Dantzig-Wolfe decomposition technique by leveraging the strengths of both quantum and classical computing, to solve the joint optimization problem. Through a series of experiments, the paper demonstrates the efficiency and robustness of the proposed methods in addressing large-scale network optimization and balancing qubit usage. The insights generated by this work offer valuable guidance for the design and implementation of satellite-based entanglement distribution for quantum networks, thereby laying the groundwork for the realization of a secure quantum communication infrastructure on a global scale.
The advancement of satellite-based quantum networks shows promise in transforming global communication infrastructure by establishing a secure and reliable quantum Internet. These networks use optical signals from satellites to ground stations to distribute high-fidelity quantum entanglements over long distances, overcoming the limitations of traditional terrestrial systems. However, the complexity of satellite-based entanglement distribution and terrestrial quantum swapping in the integrated network requires joint optimization with satellite assignment, resource allocation, and path selection. To address this challenge, we introduce a hybrid quantum-classical algorithm to solve the optimization problem by leveraging the strengths of both quantum and classical computing. The original problem is decomposed into a master problem and several subproblems using Dantzig-Wolfe decomposition and linearization techniques. Through experiments, this study demonstrates the effectiveness and reliability of the proposed methods in optimizing large-scale networks and managing qubit usage compared to the classical optimization techniques. The findings provide valuable insights for designing and implementing satellite-based entanglement distribution in quantum networks, paving the way for a secure global quantum communication infrastructure.
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.