Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2207.11821 · International Conference on Communications

LP Relaxation-Based Approximation Algorithms for Maximizing Entangled Quantum Routing Rate

Tu N. Nguyen, Dung H. P. Nguyen, Dang H. Pham, Bing-Hong Liu, Hoa Ngoc Nguyen

Published May 16, 2022• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/icc45855.2022.9838825

Related papers

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.

IEEE Transactions on Network Science and Engineering•Mar 4, 2025•10 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.

•Aug 17, 2026•0 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.

quant-pharXiv:2603.01197•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 3, 2026•1 citation

Trading Demand Saturation for Efficiency in Near-Optimal Quantum Entanglement Routing

Wan-Ting Ho, Cheng-Yang Cheng, Jian-Jhih Kuo

Efficient entanglement routing is a fundamental challenge in quantum networks due to limited memory and channel resources. Existing routing approaches often ignore per-request demand limits and continue allocating resources to requests that are already saturated, artificially inflating their throughput and limiting the ability to serve other requests. This paper formulates the Quantum Routing Problem (QRP) that jointly accounts for memory, channel, and demand limits, and aims to determine how many entangled paths should be established for each request to maximize the overall network throughput. A novel approximation algorithm based on primal-dual and separation oracle techniques is proposed, with a provable performance guarantee. Extensive simulations show that the proposed approach outperforms existing approaches by up to 29%.

IEEE Conference on Computer Communications (INFOCOM)•May 18, 2026•0 citations

Adaptive Entanglement Generation for Quantum Routing

Tasdiqul Islam, Arifuzzaman, Md, Engin Arslan

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%.

arXiv:2505.08958•May 13, 2025•1 citation

A Heuristic for Entanglement Routing in Quantum Networks

Wei-Hsun Huang, Dung H. P. Nguyen, Ting-Xiu Kuo +3 more

Due to the fact that quantum networks can provide higher security in communications, many related issues have been presented and addressed recently. One of the most important issues is to study the routing in quantum networks with multiple source-destination pairs while maximizing the total end-to-end entanglement rate. In previous studies, the shortest paths are typically selected as the entanglement paths for a source-destination pair to increase the total end-to-end entanglement rate. However, this approach is only efficient once the network resources are sufficient. Moreover, source-destination pairs only require a specific entanglement rate rather than the shortest paths. Therefore, in this paper, we suppose that each source-destination pair requires an upper bound of the entanglement rate. Under this assumption, a novel problem is proposed to construct entanglement paths for a set of multiple source-destination pairs such that the total end-to-end entanglement rate is maximized. We then propose a greedy algorithm to solve the problem. Finally, the simulation is conducted to evaluate the performance of the proposed algorithm.

International Conference on Applied System Innovation•Apr 21, 2023•0 citations
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 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.
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.
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.
Efficient entanglement routing is a fundamental challenge in quantum networks due to limited memory and channel resources. Existing routing approaches often ignore per-request demand limits and continue allocating resources to requests that are already saturated, artificially inflating their throughput and limiting the ability to serve other requests. This paper formulates the Quantum Routing Problem (QRP) that jointly accounts for memory, channel, and demand limits, and aims to determine how many entangled paths should be established for each request to maximize the overall network throughput. A novel approximation algorithm based on primal-dual and separation oracle techniques is proposed, with a provable performance guarantee. Extensive simulations show that the proposed approach outperforms existing approaches by up to 29%.
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%.
Due to the fact that quantum networks can provide higher security in communications, many related issues have been presented and addressed recently. One of the most important issues is to study the routing in quantum networks with multiple source-destination pairs while maximizing the total end-to-end entanglement rate. In previous studies, the shortest paths are typically selected as the entanglement paths for a source-destination pair to increase the total end-to-end entanglement rate. However, this approach is only efficient once the network resources are sufficient. Moreover, source-destination pairs only require a specific entanglement rate rather than the shortest paths. Therefore, in this paper, we suppose that each source-destination pair requires an upper bound of the entanglement rate. Under this assumption, a novel problem is proposed to construct entanglement paths for a set of multiple source-destination pairs such that the total end-to-end entanglement rate is maximized. We then propose a greedy algorithm to solve the problem. Finally, the simulation is conducted to evaluate the performance of the proposed algorithm.