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:2303.12864

Entanglement Routing Based on Fidelity Curves

Bruno Coelho Coutinho, Monteiro, Raul, Luís Bugalho, Francisco A. Monteiro

Published Mar 22, 2023• 7 citations
arXivHTMLPDF

Abstract

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)

DOI
10.48550/arxiv.2303.12864

Related papers

Shortest Path Finding in Quantum Networks With Quasi-Linear Complexity

Sara Santos, Francisco A. Monteiro, Bruno Coelho Coutinho +1 more

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.

IEEE Access•Jan 1, 2023•21 citations

Computing an Optimal Entanglement Path With Throughput and Fidelity Considerations

Guoliang Xue, Nageswara S. V. Rao, Don Towsley +7 more

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.

IEEE Transactions on Networking•Jan 1, 2026•0 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

Entanglement Distribution in a Quantum Network: A Multicommodity Flow-Based Approach

Kaushik Chakraborty, David Elkouss, Bruno Rijsman +1 more

We consider the problem of optimizing the achievable EPR-pair distribution rate between multiple source-destination pairs in a quantum Internet, where the repeaters may perform a probabilistic Bell-state measurement and we may impose a minimum end-to-end fidelity as a requirement. We construct an efficient linear programming (LP) formulation that computes the maximum total achievable entanglement distribution rate, satisfying the end-to-end fidelity constraint in polynomial time (in the number of nodes in the network). Our LP formulation gives the optimal rate for a class of entanglement generation protocols where the repeaters have very short-lived quantum memories. We also propose an efficient algorithm that takes the output of the LP solver as an input and runs in polynomial time (in the number of nodes) to produce the set of paths to be used to achieve the entanglement distribution rate. Moreover, we point out a practical entanglement generation protocol that can achieve those rates.

arXiv:2005.14304•IEEE Transactions on Quantum Engineering•Jan 1, 2020•135 citations

Distributed Entanglement Routing Scheme With Fidelity Guarantee in Quantum Networks

Jiesheng Tan, Zhonghui Li, Jian Li +2 more

Entanglement routing selects a path to establish entanglement connections between two arbitrary nodes in quan-tum networks, which plays an important role in quantum com-munication. In quantum networks, quantum decoherence and limited network performance make it challenging to distribute entangled pairs. Many entanglement routing schemes have been proposed to solve this issue but most of them are in a centralized and synchronized manner. However, they may be infeasible in large-scale quantum networks. Therefore, in this paper, we propose a distributed and asynchronous entanglement routing scheme called DFER in which quantum nodes manage requests autonomously. The major challenge is quantum nodes have little knowledge about entangled pairs, which hinders the ability to establish fidelity guaranteed entanglement connections. To ad dress this challenge, we develop DLFR algorithm which estimates the fidelity of end-to-end entanglement connections based on link-level fidelity and calculates link-level fidelity requirement based on the characteristic of purification. Among nodes which meet link-level fidelity requirement, we design DFPS path se lection algorithm to select next hop with the highest expected throughput to distribute entangled pairs. Numerous simulation results demonstrate that DFER can efficiently distribute fidelity guaranteed entangled pairs with high throughput.

IEEE Transactions on Network Science and Engineering•Nov 18, 2025•2 citations

Fidelity-Aware Inter-Zone Based Routing for Throughput Maximization in Quantum Networks

Pankaj Kumar, Binayak Kar

Quantum networks enable advanced applications by connecting quantum nodes through entangled qubit pairs, with entanglement routing being essential for their operation. However, maintaining high-quality entanglement across large-scale networks is challenging due to decoherence, probabilistic generation, limited memory coherence, and fidelity loss. To mitigate these issues, we adopt a zone-based architecture that logically groups nodes into manageable zones, improving scalability, efficiency, and localized entanglement distribution. We propose the Inter-Zone-Based Routing (Inter-ZBR) design, a fidelity-aware framework aimed at enabling high-fidelity entanglement distribution across the network. This Inter-ZBR framework includes three components: (i) QNetwork-Zone Formation (QNZF) algorithm, which divides large-scale networks into well-connected zones to optimize routing decisions and reduce network complexity for entanglement generation; (ii) Inter-Zone Path Selection (IZPS) algorithm, which determines the set of potential shortest paths for each Source-Destination (SD) pair; (iii) The Inter-Zone based Fidelity-Aware Entanglement Routing (IZFAER) algorithm selects optimal routing paths by evaluating entanglement generation rates to maximize network throughput, while incorporating purification techniques to ensure end-to-end fidelity in the network. Simulation results demonstrate that the Inter-ZBR framework improves network throughput by 7.45% to 11.91%, increases end-to-end fidelity by 3.52% to 4.75%, and reduces quantum memory consumption by 9.27% to 21.40%, compared to traditional entanglement routing methods.

IEEE Journal on Selected Areas in Communications•Jan 1, 2026•0 citations
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)
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.
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.
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.
We consider the problem of optimizing the achievable EPR-pair distribution rate between multiple source-destination pairs in a quantum Internet, where the repeaters may perform a probabilistic Bell-state measurement and we may impose a minimum end-to-end fidelity as a requirement. We construct an efficient linear programming (LP) formulation that computes the maximum total achievable entanglement distribution rate, satisfying the end-to-end fidelity constraint in polynomial time (in the number of nodes in the network). Our LP formulation gives the optimal rate for a class of entanglement generation protocols where the repeaters have very short-lived quantum memories. We also propose an efficient algorithm that takes the output of the LP solver as an input and runs in polynomial time (in the number of nodes) to produce the set of paths to be used to achieve the entanglement distribution rate. Moreover, we point out a practical entanglement generation protocol that can achieve those rates.
Entanglement routing selects a path to establish entanglement connections between two arbitrary nodes in quan-tum networks, which plays an important role in quantum com-munication. In quantum networks, quantum decoherence and limited network performance make it challenging to distribute entangled pairs. Many entanglement routing schemes have been proposed to solve this issue but most of them are in a centralized and synchronized manner. However, they may be infeasible in large-scale quantum networks. Therefore, in this paper, we propose a distributed and asynchronous entanglement routing scheme called DFER in which quantum nodes manage requests autonomously. The major challenge is quantum nodes have little knowledge about entangled pairs, which hinders the ability to establish fidelity guaranteed entanglement connections. To ad dress this challenge, we develop DLFR algorithm which estimates the fidelity of end-to-end entanglement connections based on link-level fidelity and calculates link-level fidelity requirement based on the characteristic of purification. Among nodes which meet link-level fidelity requirement, we design DFPS path se lection algorithm to select next hop with the highest expected throughput to distribute entangled pairs. Numerous simulation results demonstrate that DFER can efficiently distribute fidelity guaranteed entangled pairs with high throughput.
Quantum networks enable advanced applications by connecting quantum nodes through entangled qubit pairs, with entanglement routing being essential for their operation. However, maintaining high-quality entanglement across large-scale networks is challenging due to decoherence, probabilistic generation, limited memory coherence, and fidelity loss. To mitigate these issues, we adopt a zone-based architecture that logically groups nodes into manageable zones, improving scalability, efficiency, and localized entanglement distribution. We propose the Inter-Zone-Based Routing (Inter-ZBR) design, a fidelity-aware framework aimed at enabling high-fidelity entanglement distribution across the network. This Inter-ZBR framework includes three components: (i) QNetwork-Zone Formation (QNZF) algorithm, which divides large-scale networks into well-connected zones to optimize routing decisions and reduce network complexity for entanglement generation; (ii) Inter-Zone Path Selection (IZPS) algorithm, which determines the set of potential shortest paths for each Source-Destination (SD) pair; (iii) The Inter-Zone based Fidelity-Aware Entanglement Routing (IZFAER) algorithm selects optimal routing paths by evaluating entanglement generation rates to maximize network throughput, while incorporating purification techniques to ensure end-to-end fidelity in the network. Simulation results demonstrate that the Inter-ZBR framework improves network throughput by 7.45% to 11.91%, increases end-to-end fidelity by 3.52% to 4.75%, and reduces quantum memory consumption by 9.27% to 21.40%, compared to traditional entanglement routing methods.