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 Transactions on Networking

Computing an Optimal Entanglement Path With Throughput and Fidelity Considerations

Guoliang Xue, Nageswara S. V. Rao, Don Towsley, Gayane Vardoyan, Zunzheng Zhang, Xuanli Lin, Muneer Alshowkan, Joseph M. Lukens, Nicholas A. Peters, Saikat Guha

Published Jan 1, 2026• 0 citations
Publisher

Abstract

Entanglement distribution is a core function of quantum networks essential for operations including teleportation, distributed quantum sensing, and multisite computation. Entanglement throughput and fidelity are two critical performance measures that depend on the quantum transmission along the links and swapping operations at the repeaters along the path. We study the problem of computing an end-to-end entanglement path that satisfies both fidelity and throughput requirements, leveraging qubit buffers at the nodes and considering the sequential swapping order. We show that the general problem of simultaneously satisfying both metrics is NP-hard, and develop an algorithm to maximize throughput subject to a given fidelity threshold. We introduce the concepts of entanglement probability distribution and path domination and exploit them in the design of our algorithm. Extensive numerical results show that our algorithm can find optimal solutions in networks with thousands of nodes in less than a second. We also describe practical and possible implementation aspects of this algorithm in terms of devices and architecture support.

DOI
10.1109/ton.2026.3728139

Related papers

Towards Optimal Orders for Entanglement Swapping in Path Graphs: A Greedy Approach

Van Sy Mai, Abderrahim Amlou, Amar Abane +1 more

This paper considers the problem of finding an optimal order for entanglement swapping in a heterogeneous path of quantum repeaters so as to maximize the path throughput defined as the delivery rate of end-to-end entanglements. The primary difficulty in addressing this problem lies in the vast array of possible swapping orders for large paths and the complexity of the expected throughput, which depends on the attributes of each node and edge along the path, as well as the order of swapping. To cope with these issues, we first propose simple approximations in estimating the swapping outcome between two entanglement distributions that can run in constant time, thereby providing an efficient approach for evaluating and comparing different swapping orders, allowing us to solve the problem exactly for small paths. Second, as the number of possible orders grows exponentially with the number of repeaters in the path, we develop an efficient heuristic based on the greedy selection of nodes to sequentially perform swaps according to their swapping scores, defined as the expected number of entanglements resulting from their swaps. The scores are local but dynamic in the sense that they depend not just on the entanglement distributions available on the path but also on prior swapping decisions. Finally, we illustrate the efficiency and effectiveness of our proposed model and approach through extensive experimentation conducted using a general quantum network simulator.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•3 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)

arXiv:2303.12864•Mar 22, 2023•7 citations

Cost-Aware High-Fidelity Entanglement Distribution and Purification in the Quantum Internet

Huayue Gu, Zhouyu Li, Xiaojian Wang +3 more

Operating a quantum network incurs high capital and operational expenditures, which are expected to be compensated by the high value of enabled quantum applications. However, existing mechanisms mainly focus on maximizing the entanglement distribution rate and neglect the cost incurred on users. This paper aims to address how to utilize quantum network resources in a cost-efficient manner while sustaining high-quantity and high-quality entanglement distribution. We first consider how to establish a steady stream of entanglements between remote nodes with the minimum cost. Utilizing a recent flow-based abstraction and a novel graph representation, we design an optimal algorithm for min-cost remote entanglement distribution. Next, we consider distributing entanglements with the highest fidelity subject to a cost bound and prove its NP-hardness. To explore the cost-fidelity trade-off due to swapping and purification, we propose an approximation scheme for maximizing fidelity while satisfying an arbitrary cost bound. Our algorithms provide rigorous tools for supporting high-performance quantum network applications with financial consideration and offer strong theoretical guarantees. Extensive simulation results validate the advantageous performance in cost efficiency and/or fidelity compared to existing solutions and heuristics.

IEEE Transactions on Networking•Sep 8, 2025•2 citations

Optimal Fidelity-Aware Entanglement Distribution in Linear Quantum Networks

Iordanis Koutsopoulos

We study the problem of entanglement distribution in terms of maximizing a utility function that captures the total fidelity of end-to-end entanglements in a two-link linear quantum network with a source, a repeater, and a destination. The nodes have several quantum memories, and the problem is how to coordinate entanglement purification in each of the links, and entanglement swapping across links so as to achieve the goal above. We show that entanglement swapping (i.e, deciding on the pair of qubits from each link to perform swapping on) is equivalent to finding a max-weight matching on a bipartite graph. Further, entanglement purification (i.e, deciding which pairs of qubits in a link will undergo purification) is equivalent to finding a max-weight matching on a non-bipartite graph. We propose two polynomial algorithms, the Purify-then-Swap (PtS) and the Swap-then-Purify (StP) ones, where the decisions about purification and swapping are taken with different order. Numerical results show that PtS performs better than StP, and that the omission of purification in StP gives substantial benefits.

arXiv:2407.09171•IEEE Military Communications Conference (MILCOM)•Oct 28, 2024•4 citations

Fidelity-Guaranteed Entanglement Routing in Quantum Networks

Jian Li, Mingjun Wang, Kaiping Xue +4 more

Entanglement routing establishes remote entanglement connection between two arbitrary nodes, which is one of the most important functions in quantum networks. The existing routing mechanisms mainly improve the robustness and throughput facing the failure of entanglement generations, which, however, rarely include the considerations on the most important metric to evaluate the quality of connection, entanglement fidelity. To solve this problem, we propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (S-D) pairs in quantum networks. In our proposal, we first consider the single S-D pair scenario and design an iterative routing algorithm, Q-PATH, to find the optimal purification decisions along the routing path with minimum entangled pair cost. Further, a low-complexity routing algorithm using an extended Dijkstra algorithm, Q-LEAP, is designed to reduce the computational complexity by using a simple but effective purification decision method. Finally, we consider the common scenario with multiple S-D pairs and design a greedy-based algorithm considering resource allocation and re-routing process for multiple routing requests. Simulation results show that the proposed algorithms not only can provide fidelity-guaranteed routing solutions, but also has superior performance in terms of throughput, fidelity of end-to-end entanglement connection, and resource utilization ratio, compared with the existing routing scheme.

arXiv:2111.07764•IEEE Transactions on Communications•Aug 19, 2022•154 citations

Multi-Pair Fidelity-Aware Rate Allocation in a Quantum Network: Approximation Schemes

Zunzheng Zhang, Xuanli Lin, Zhaofeng Zhang +2 more

Entanglement distribution in quantum networks must jointly account for limited link capacities, probabilistic entanglement swapping, and heterogeneous link fidelities. In this paper, we study multi-pair fidelity-aware rate allocation in quantum networks. We formulate three rate-allocation problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. Prior work has studied a special case of the rate sum problem, where all links have identical fidelity. This special case admits a polynomial-time algorithm. We prove that all three problems are NP-hard. We then study optimization versions of these problems which maximize the minimum end-to-end fidelity subject to throughput or fairness requirements. We present fully polynomial-time approximation schemes (FPTAS) for solving these optimization problems. Experiments on randomly generated networks demonstrate the computational effectiveness of the proposed schemes.

arXiv:2608.11501•Aug 11, 2026•1 citation
Entanglement distribution is a core function of quantum networks essential for operations including teleportation, distributed quantum sensing, and multisite computation. Entanglement throughput and fidelity are two critical performance measures that depend on the quantum transmission along the links and swapping operations at the repeaters along the path. We study the problem of computing an end-to-end entanglement path that satisfies both fidelity and throughput requirements, leveraging qubit buffers at the nodes and considering the sequential swapping order. We show that the general problem of simultaneously satisfying both metrics is NP-hard, and develop an algorithm to maximize throughput subject to a given fidelity threshold. We introduce the concepts of entanglement probability distribution and path domination and exploit them in the design of our algorithm. Extensive numerical results show that our algorithm can find optimal solutions in networks with thousands of nodes in less than a second. We also describe practical and possible implementation aspects of this algorithm in terms of devices and architecture support.
This paper considers the problem of finding an optimal order for entanglement swapping in a heterogeneous path of quantum repeaters so as to maximize the path throughput defined as the delivery rate of end-to-end entanglements. The primary difficulty in addressing this problem lies in the vast array of possible swapping orders for large paths and the complexity of the expected throughput, which depends on the attributes of each node and edge along the path, as well as the order of swapping. To cope with these issues, we first propose simple approximations in estimating the swapping outcome between two entanglement distributions that can run in constant time, thereby providing an efficient approach for evaluating and comparing different swapping orders, allowing us to solve the problem exactly for small paths. Second, as the number of possible orders grows exponentially with the number of repeaters in the path, we develop an efficient heuristic based on the greedy selection of nodes to sequentially perform swaps according to their swapping scores, defined as the expected number of entanglements resulting from their swaps. The scores are local but dynamic in the sense that they depend not just on the entanglement distributions available on the path but also on prior swapping decisions. Finally, we illustrate the efficiency and effectiveness of our proposed model and approach through extensive experimentation conducted using a general quantum network simulator.
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 111 and 1.41.41.4, depending on the network)
Operating a quantum network incurs high capital and operational expenditures, which are expected to be compensated by the high value of enabled quantum applications. However, existing mechanisms mainly focus on maximizing the entanglement distribution rate and neglect the cost incurred on users. This paper aims to address how to utilize quantum network resources in a cost-efficient manner while sustaining high-quantity and high-quality entanglement distribution. We first consider how to establish a steady stream of entanglements between remote nodes with the minimum cost. Utilizing a recent flow-based abstraction and a novel graph representation, we design an optimal algorithm for min-cost remote entanglement distribution. Next, we consider distributing entanglements with the highest fidelity subject to a cost bound and prove its NP-hardness. To explore the cost-fidelity trade-off due to swapping and purification, we propose an approximation scheme for maximizing fidelity while satisfying an arbitrary cost bound. Our algorithms provide rigorous tools for supporting high-performance quantum network applications with financial consideration and offer strong theoretical guarantees. Extensive simulation results validate the advantageous performance in cost efficiency and/or fidelity compared to existing solutions and heuristics.
We study the problem of entanglement distribution in terms of maximizing a utility function that captures the total fidelity of end-to-end entanglements in a two-link linear quantum network with a source, a repeater, and a destination. The nodes have several quantum memories, and the problem is how to coordinate entanglement purification in each of the links, and entanglement swapping across links so as to achieve the goal above. We show that entanglement swapping (i.e, deciding on the pair of qubits from each link to perform swapping on) is equivalent to finding a max-weight matching on a bipartite graph. Further, entanglement purification (i.e, deciding which pairs of qubits in a link will undergo purification) is equivalent to finding a max-weight matching on a non-bipartite graph. We propose two polynomial algorithms, the Purify-then-Swap (PtS) and the Swap-then-Purify (StP) ones, where the decisions about purification and swapping are taken with different order. Numerical results show that PtS performs better than StP, and that the omission of purification in StP gives substantial benefits.
Entanglement routing establishes remote entanglement connection between two arbitrary nodes, which is one of the most important functions in quantum networks. The existing routing mechanisms mainly improve the robustness and throughput facing the failure of entanglement generations, which, however, rarely include the considerations on the most important metric to evaluate the quality of connection, entanglement fidelity. To solve this problem, we propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (S-D) pairs in quantum networks. In our proposal, we first consider the single S-D pair scenario and design an iterative routing algorithm, Q-PATH, to find the optimal purification decisions along the routing path with minimum entangled pair cost. Further, a low-complexity routing algorithm using an extended Dijkstra algorithm, Q-LEAP, is designed to reduce the computational complexity by using a simple but effective purification decision method. Finally, we consider the common scenario with multiple S-D pairs and design a greedy-based algorithm considering resource allocation and re-routing process for multiple routing requests. Simulation results show that the proposed algorithms not only can provide fidelity-guaranteed routing solutions, but also has superior performance in terms of throughput, fidelity of end-to-end entanglement connection, and resource utilization ratio, compared with the existing routing scheme.
Entanglement distribution in quantum networks must jointly account for limited link capacities, probabilistic entanglement swapping, and heterogeneous link fidelities. In this paper, we study multi-pair fidelity-aware rate allocation in quantum networks. We formulate three rate-allocation problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. Prior work has studied a special case of the rate sum problem, where all links have identical fidelity. This special case admits a polynomial-time algorithm. We prove that all three problems are NP-hard. We then study optimization versions of these problems which maximize the minimum end-to-end fidelity subject to throughput or fairness requirements. We present fully polynomial-time approximation schemes (FPTAS) for solving these optimization problems. Experiments on randomly generated networks demonstrate the computational effectiveness of the proposed schemes.