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

IEEE Conference on Computer Communications (INFOCOM)

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

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

Published May 18, 2026• 0 citations
Publisher

Abstract

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

DOI
10.1109/infocom59046.2026.11571546

Related papers

Online Transit Entanglement Routing in Quantum Networks: Architecture Design and Optimization

Wan-Ting Ho, Shing-Yan Fang, Wei-Chia Hsieh +3 more

Quantum networks (QNs) gradually gain significant attention due to their higher security compared with classical networks. Conventional approaches in QN routing often aggregate multiple requests into a batch before determining their routing paths. However, this approach may overlook the limited lifetime of qubits, resulting in critical decoherence. In this paper, we present a new online entanglement routing architecture with an online optimization problem and propose a novel [1, O(log |V|)]-competitive algorithm supporting online requests with admission control, aiming to maximize the number of admitted requests. Finally, extensive simulation results show that our algorithm can outperform the existing approaches by up to 98%.

Globecom•Dec 8, 2024•0 citations

SFTRAP: Satisfying Fidelity Threshold Routing and Adaptive Purification for Throughput Maximum in Quantum Network

Zhi Wang, Tao Gong, Yingpu Nian +6 more

The core function of quantum networks is to establish high-fidelity quantum entanglement for long-distance communication. However, the main challenge is to efficiently allocate resources under limited conditions, maximize throughput, satisfy end-to-end (E2E) fidelity requirements, and prevent quantum decoherence caused by inefficient routing algorithms. Current research focuses on optimizing either throughput or fidelity, with a lack of approaches that optimize both simultaneously; furthermore, existing algorithms suffer from high computational complexity. To tackle these challenges, this study proposes a Satisfying Fidelity Threshold Routing and Adaptive Purification Strategy (SFTRAP). SFTRAP maximizes throughput for each request by selecting multiple paths and dynamically choosing links for entanglement purification based on the current state of link resources, thus minimizing throughput loss while satisfying fidelity threshold. The strategy also adaptively adjusts the number of purification rounds according to the fidelity threshold, thereby optimizing the time required for deep purification and enhancing algorithmic efficiency. For multi-request scenarios, SFTRAP employs a priority sorting mechanism that takes into account both path cost and path freedom, which refines request scheduling and path selection to create more efficient request combinations, thus further boosting the overall network throughput. Simulation results indicate that SFTRAP surpasses state-of-the-art methods in terms of both throughput and algorithmic efficiency, highlighting its potential for optimizing resources in quantum networks.

IEEE Transactions on Communications•Jan 1, 2026•17 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.

IEEE Transactions on Network Science and Engineering•Mar 4, 2025•10 citations

Achieving Load-Balanced Entanglement Distribution in Quantum Networks

Zhuoyue Chen, Kechao Cai, Jinbei Zhang +1 more

Entanglement distribution, which relies on entanglement routing and swapping strategies, is a fundamental task in quantum networks. However, existing routing algorithms often overutilize the quantum memory of nodes along shortest paths and neglect imbalanced memory utilization across different nodes, thereby increasing the risk of end-to-end (E2E) entanglement failures for subsequent requests. Moreover, suboptimal swapping strategies can further exacerbate memory imbalance among nodes. In this paper, we study load-balanced entanglement distribution to improve the resilience of quantum networks. We first propose abottleneck node modelthat captures shared quantum memory constraints at each node. Based on this model, we formulate theload-balanced entanglement distributionproblem, which aims to optimize routing decisions and swapping strategies to balance memory utilization. We prove the problem to be NP-hard and develop a decomposition-based approach that separates path finding and quantum memory allocation for sequential request processing. Based on this decomposition, we propose LBER (Load-Balanced Entanglement Routing), a polynomial-time heuristic that distributes entanglement across multiple paths. We further design an adaptive swapping strategy, AdapSwap, to determine the optimal swapping order along each path. Extensive simulations show that our approach significantly improves load balance and increases the request satisfaction ratio by 7.69%∼32.14%.

IEEE Transactions on Communications•Jan 1, 2026•0 citations

Traffic-Aware Routing Algorithm in Quantum Network

Puli Li, Weihai Li

Quantum network can provide end-to-end entanglements through quantum operations, supporting various quantum applications such as quantum key distribution and distributed quantum computing. However, many previous proposals for quantum networks assumed the division of quantum network into time slots and batch processing of network communication tasks, performing poorly in dynamic network scenarios and not fully utilizing network resources. This work focuses on the routing problem in entanglement quantum networks, aiming to provide more efficient end-to-end entanglement establishment for upper-layer applications. We propose an on-demand routing algorithm that dynamically adjusts the optimal path based on the current network conditions. Specifically, we consider the benefits of path width for quantum networks and propose an algorithm for finding the shortest wide path. Using this algorithm, each node establishes its own routing table. Additionally, to dynamically avoid network hotspots, we introduce the concept of traffic to reflect the busyness of nodes. Finally, using a dynamic cost calculation method as the routing metric, we select the optimal path for the current request. To evaluate the performance of the proposed quantum routing algorithm, we conducted simulation experiments on SimQN quantum simulation platform. The results show that our approach improves network throughput by 14 percent compared to existing solutions.

International Conference on Computer and Communication Systems (ICCCS)•Apr 19, 2024•0 citations

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

Tu N. Nguyen, Dung H. P. Nguyen, Dang H. Pham +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 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.11821•International Conference on Communications•May 16, 2022•9 citations
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%.
Quantum networks (QNs) gradually gain significant attention due to their higher security compared with classical networks. Conventional approaches in QN routing often aggregate multiple requests into a batch before determining their routing paths. However, this approach may overlook the limited lifetime of qubits, resulting in critical decoherence. In this paper, we present a new online entanglement routing architecture with an online optimization problem and propose a novel [1, O(log |V|)]-competitive algorithm supporting online requests with admission control, aiming to maximize the number of admitted requests. Finally, extensive simulation results show that our algorithm can outperform the existing approaches by up to 98%.
The core function of quantum networks is to establish high-fidelity quantum entanglement for long-distance communication. However, the main challenge is to efficiently allocate resources under limited conditions, maximize throughput, satisfy end-to-end (E2E) fidelity requirements, and prevent quantum decoherence caused by inefficient routing algorithms. Current research focuses on optimizing either throughput or fidelity, with a lack of approaches that optimize both simultaneously; furthermore, existing algorithms suffer from high computational complexity. To tackle these challenges, this study proposes a Satisfying Fidelity Threshold Routing and Adaptive Purification Strategy (SFTRAP). SFTRAP maximizes throughput for each request by selecting multiple paths and dynamically choosing links for entanglement purification based on the current state of link resources, thus minimizing throughput loss while satisfying fidelity threshold. The strategy also adaptively adjusts the number of purification rounds according to the fidelity threshold, thereby optimizing the time required for deep purification and enhancing algorithmic efficiency. For multi-request scenarios, SFTRAP employs a priority sorting mechanism that takes into account both path cost and path freedom, which refines request scheduling and path selection to create more efficient request combinations, thus further boosting the overall network throughput. Simulation results indicate that SFTRAP surpasses state-of-the-art methods in terms of both throughput and algorithmic efficiency, highlighting its potential for optimizing resources in quantum networks.
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 distribution, which relies on entanglement routing and swapping strategies, is a fundamental task in quantum networks. However, existing routing algorithms often overutilize the quantum memory of nodes along shortest paths and neglect imbalanced memory utilization across different nodes, thereby increasing the risk of end-to-end (E2E) entanglement failures for subsequent requests. Moreover, suboptimal swapping strategies can further exacerbate memory imbalance among nodes. In this paper, we study load-balanced entanglement distribution to improve the resilience of quantum networks. We first propose abottleneck node modelthat captures shared quantum memory constraints at each node. Based on this model, we formulate theload-balanced entanglement distributionproblem, which aims to optimize routing decisions and swapping strategies to balance memory utilization. We prove the problem to be NP-hard and develop a decomposition-based approach that separates path finding and quantum memory allocation for sequential request processing. Based on this decomposition, we propose LBER (Load-Balanced Entanglement Routing), a polynomial-time heuristic that distributes entanglement across multiple paths. We further design an adaptive swapping strategy, AdapSwap, to determine the optimal swapping order along each path. Extensive simulations show that our approach significantly improves load balance and increases the request satisfaction ratio by 7.69%∼32.14%.
Quantum network can provide end-to-end entanglements through quantum operations, supporting various quantum applications such as quantum key distribution and distributed quantum computing. However, many previous proposals for quantum networks assumed the division of quantum network into time slots and batch processing of network communication tasks, performing poorly in dynamic network scenarios and not fully utilizing network resources. This work focuses on the routing problem in entanglement quantum networks, aiming to provide more efficient end-to-end entanglement establishment for upper-layer applications. We propose an on-demand routing algorithm that dynamically adjusts the optimal path based on the current network conditions. Specifically, we consider the benefits of path width for quantum networks and propose an algorithm for finding the shortest wide path. Using this algorithm, each node establishes its own routing table. Additionally, to dynamically avoid network hotspots, we introduce the concept of traffic to reflect the busyness of nodes. Finally, using a dynamic cost calculation method as the routing metric, we select the optimal path for the current request. To evaluate the performance of the proposed quantum routing algorithm, we conducted simulation experiments on SimQN quantum simulation platform. The results show that our approach improves network throughput by 14 percent compared to existing solutions.
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.