There will be a fast-paced shift from conventional network systems to novel quantum networks that are supported by the quantum entanglement and teleportation, key technologies of the quantum era, to enable secured data transmissions in the next-generation of the Internet. Despite this prospect, migration to quantum networks cannot be done at once, especially on the aspect of quantum routing. In this paper, we study the maximizing entangled routing rate (MERR) problem. In particular, given a set of demands, we try to determine entangled routing paths for the maximum number of demands in the quantum network while meeting the network's fidelity. We first formulate the MERR problem using an integer linear programming (ILP) model to capture the traffic patent for all demands in the network. We then leverage the theory of relaxation of ILP to devise two efficient algorithms including HBRA and RRA with provable approximation ratios for the objective function. To deal with the challenge of the combinatorial optimization problem in big scale networks, we also propose the path-length-based approach (PLBA) to solve the MERR problem. Using both simulations and an open quantum network simulator platform to conduct experiments with real-world topologies and traffic matrices, we evaluate the performance of our algorithms and show up the success of maximizing entangled routing rate.There will be a fast-paced shift from conventional network systems to novel quantum networks that are supported by the quantum entanglement and teleportation, key technologies of the quantum era, to enable secured data transmissions in the next-generation of the Internet. Despite this prospect, migration to quantum networks cannot be done at once, especially on the aspect of quantum routing. In this paper, we study the maximizing entangled routing rate (MERR) problem. In particular, given a set of demands, we try to determine entangled routing paths for the maximum number of demands in the quantum network while meeting the network's fidelity. We first formulate the MERR problem using an integer linear programming (ILP) model to capture the traffic patent for all demands in the network. We then leverage the theory of relaxation of ILP to devise two efficient algorithms including HBRA and RRA with provable approximation ratios for the objective function. To deal with the challenge of the combinatorial optimization problem in big scale networks, we also propose the path-length-based approach (PLBA) to solve the MERR problem. Using both simulations and an open quantum network simulator platform to conduct experiments with real-world topologies and traffic matrices, we evaluate the performance of our algorithms and show up the success of maximizing entangled routing rate.

arXiv:2207.11821Jul 19, 20220 citations

Maximizing Entanglement Routing Rate in Quantum Networks: Approximation Algorithms

Dung H. P. Nguyen, Ethan Hunt, Dillon J. Horton +2 more

There will be a fast-paced shift from conventional network systems to novel quantum networks that are supported by the quantum entanglement and teleportation, key technologies of the quantum era, to enable secured data transmissions in the next-generation of the Internet. Despite this prospect, migration to quantum networks cannot happen all at once, especially when it comes to quantum routing. In this paper, we focus on the maximizing entanglement routing rate (MERR) problem, which aims to determine entangled routing paths for the maximum number of demands in the quantum network while meeting the network's fidelity. To tackle this problem, we first formulate the MERR problem using an integer linear programming (ILP) model. We then leverage the method of linear programming relaxation to devise two efficient algorithms, including the half-based rounding algorithm (HBRA) and the randomized rounding algorithm (RRA) with a provable approximation ratio for the objective function. Furthermore, to address the challenge of the combinatorial optimization problem in big scale networks, we also propose the path-length-based approach (PLBA) to solve the MERR problem. Finally, we evaluate the performance of our algorithms and show up the success of maximizing the entanglement routing rate.There will be a fast-paced shift from conventional network systems to novel quantum networks that are supported by the quantum entanglement and teleportation, key technologies of the quantum era, to enable secured data transmissions in the next-generation of the Internet. Despite this prospect, migration to quantum networks cannot happen all at once, especially when it comes to quantum routing. In this paper, we focus on the maximizing entanglement routing rate (MERR) problem, which aims to determine entangled routing paths for the maximum number of demands in the quantum network while meeting the network's fidelity. To tackle this problem, we first formulate the MERR problem using an integer linear programming (ILP) model. We then leverage the method of linear programming relaxation to devise two efficient algorithms, including the half-based rounding algorithm (HBRA) and the randomized rounding algorithm (RRA) with a provable approximation ratio for the objective function. Furthermore, to address the challenge of the combinatorial optimization problem in big scale networks, we also propose the path-length-based approach (PLBA) to solve the MERR problem. Finally, we evaluate the performance of our algorithms and show up the success of maximizing the entanglement routing rate.

IEEE Transactions on Network Science and EngineeringMar 4, 20259 citations

Learning-Based Entanglement Generation for Quantum Routing

Tasdiqul Islam, Rasman Mubtasim Swargo, Md Arifuzzaman

Entanglement generation in long-distance quantum networks is challenging because resources are limited and entanglement swapping is probabilistic. To maximize the rate of successful requests, existing quantum routing algorithms often rely on computationally expensive methods such as Integer Linear Programming (ILP) to determine which links to entangle and use for end-to-end entanglement generation. However, these approaches fail to meet the latency requirements of real-world quantum networks. In this study, we propose a Reinforcement Learning (RL)-based model that determines which links to entangle in each time slot, replacing the slow ILP-based link-selection phase used in prior algorithms. The proposed Deep Q-learning model is up to 19.2× faster than linear programming in link-selection while maintaining comparable routing performance. The RL link-selection model alone matches ILP in request success rate; combining RL link selection with entanglement caching and proactive swapping raises throughput by up to 52.55% over ILP. Overall, our approach achieves success rates exceeding state-of-the-art solutions while reducing execution time by more than an order of magnitude. Experiments on a synthetic 50-node Waxman topology and the real-world 54-node SURFnet core topology confirm that these gains generalize across network structures, providing a practical path toward scalable quantum routing.Entanglement generation in long-distance quantum networks is challenging because resources are limited and entanglement swapping is probabilistic. To maximize the rate of successful requests, existing quantum routing algorithms often rely on computationally expensive methods such as Integer Linear Programming (ILP) to determine which links to entangle and use for end-to-end entanglement generation. However, these approaches fail to meet the latency requirements of real-world quantum networks. In this study, we propose a Reinforcement Learning (RL)-based model that determines which links to entangle in each time slot, replacing the slow ILP-based link-selection phase used in prior algorithms. The proposed Deep Q-learning model is up to 19.2× faster than linear programming in link-selection while maintaining comparable routing performance. The RL link-selection model alone matches ILP in request success rate; combining RL link selection with entanglement caching and proactive swapping raises throughput by up to 52.55% over ILP. Overall, our approach achieves success rates exceeding state-of-the-art solutions while reducing execution time by more than an order of magnitude. Experiments on a synthetic 50-node Waxman topology and the real-world 54-node SURFnet core topology confirm that these gains generalize across network structures, providing a practical path toward scalable quantum routing.

Aug 17, 20260 citations

On Utility-optimal Entanglement Routing in Quantum Networks

Sounak Kar, Arpan Mukhopadhyay

Quantum networks are envisioned to enable reliable distribution and manipulation of quantum information across distances, forming the foundation of a future quantum internet. The fair and efficient allocation of communication resources in such networks has been addressed through the quantum network utility maximization (QNUM) framework, which optimizes network utility under the assumption of predetermined routes for competing user demands. In this work, we relax this assumption and aim to identify optimal routes that correspond to the maximum achievable network utility. Specifically, we formulate the single-path utility-based entanglement routing problem as a Mixed-Integer Convex Program (MICP). The formulation is exact when negativity is chosen as the entanglement measure for utility quantification or the network supports sufficiently high entanglement generation rates across demands. For other entanglement measures considered, the formulation approximates the problem with over 99.99% accuracy on evaluated real-world examples. To improve computational tractability, we propose a randomized rounding-based heuristic and an upper bound via the relaxation of the MICP. Furthermore, based on min-congestion routing, we introduce an alternative randomized heuristic and upper bound. This heuristic is computationally faster, while both the heuristic and the upper bound often outperform their counterparts on considered real-world networks. Our work provides the framework for extending classical flow-based and quality of service-aware routing concepts to quantum networks.Quantum networks are envisioned to enable reliable distribution and manipulation of quantum information across distances, forming the foundation of a future quantum internet. The fair and efficient allocation of communication resources in such networks has been addressed through the quantum network utility maximization (QNUM) framework, which optimizes network utility under the assumption of predetermined routes for competing user demands. In this work, we relax this assumption and aim to identify optimal routes that correspond to the maximum achievable network utility. Specifically, we formulate the single-path utility-based entanglement routing problem as a Mixed-Integer Convex Program (MICP). The formulation is exact when negativity is chosen as the entanglement measure for utility quantification or the network supports sufficiently high entanglement generation rates across demands. For other entanglement measures considered, the formulation approximates the problem with over 99.99% accuracy on evaluated real-world examples. To improve computational tractability, we propose a randomized rounding-based heuristic and an upper bound via the relaxation of the MICP. Furthermore, based on min-congestion routing, we introduce an alternative randomized heuristic and upper bound. This heuristic is computationally faster, while both the heuristic and the upper bound often outperform their counterparts on considered real-world networks. Our work provides the framework for extending classical flow-based and quality of service-aware routing concepts to quantum networks.

quant-pharXiv:2603.01197Mar 3, 20260 citations

On Utility-Optimal Entanglement Routing in Quantum Networks

Sounak Kar, Arpan Mukhopadhyay

Quantum networks are envisioned to enable reliable distribution and manipulation of quantum information across distances, forming the foundation of a future quantum internet. The fair and efficient allocation of communication resources in such networks has been addressed through the quantum network utility maximization (QNUM) framework, which optimizes network utility under the assumption of predetermined routes for competing user demands. In this work, we relax this assumption and aim to identify optimal routes that correspond to the maximum achievable network utility. Specifically, we formulate the single-path utility-based entanglement routing problem as a Mixed-Integer Convex Program (MICP). The formulation is exact when negativity is chosen as the entanglement measure for utility quantification or the network supports sufficiently high entanglement generation rates across demands. For other entanglement measures considered, the formulation approximates the problem with over 99.99 % accuracy on evaluated real-world examples. To improve computational tractability, we propose a randomized rounding-based heuristic and an upper bound via the relaxation of the MICP. Furthermore, based on min-congestion routing, we introduce an alternative randomized heuristic and upper bound. This heuristic is computationally faster, while both the heuristic and the upper bound often outperform their counterparts on considered real-world networks. Our work provides the framework for extending classical flow-based and quality of service-aware routing concepts to quantum networks.Quantum networks are envisioned to enable reliable distribution and manipulation of quantum information across distances, forming the foundation of a future quantum internet. The fair and efficient allocation of communication resources in such networks has been addressed through the quantum network utility maximization (QNUM) framework, which optimizes network utility under the assumption of predetermined routes for competing user demands. In this work, we relax this assumption and aim to identify optimal routes that correspond to the maximum achievable network utility. Specifically, we formulate the single-path utility-based entanglement routing problem as a Mixed-Integer Convex Program (MICP). The formulation is exact when negativity is chosen as the entanglement measure for utility quantification or the network supports sufficiently high entanglement generation rates across demands. For other entanglement measures considered, the formulation approximates the problem with over 99.99 % accuracy on evaluated real-world examples. To improve computational tractability, we propose a randomized rounding-based heuristic and an upper bound via the relaxation of the MICP. Furthermore, based on min-congestion routing, we introduce an alternative randomized heuristic and upper bound. This heuristic is computationally faster, while both the heuristic and the upper bound often outperform their counterparts on considered real-world networks. Our work provides the framework for extending classical flow-based and quality of service-aware routing concepts to quantum networks.

International Conference on Quantum Communications, Networking, and Computing (QCNC)Apr 6, 20260 citations

Entanglement Routing Based on Fidelity Curves

Bruno Coelho Coutinho, Monteiro, Raul, Luís Bugalho +1 more

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)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)

arXiv:2303.12864Mar 22, 20231 citation

1

and

1.4

, depending on the network)