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 Workshops (INFOCOM WKSHPS)

Order Matters: On the Impact of Swapping Order on an Entanglement Path in a Quantum Network

Alena Chang, Guoliang Xue

Published May 2, 2022• 23 citations
Publisher

Abstract

In this paper, we study the properties of path metrics of an entanglement path for a given entanglement swapping order of the path. We show how to efficiently compute the path metrics of an entanglement path for any given swapping order. We show that different entanglement swapping orders for the same path can lead to different expected throughputs. A key finding is that the binary operator corresponding to entanglement swapping along a path is not associative. We further show that the problem of computing an s-t path with maximum expected throughput under any entanglement swapping order does not have the subpath optimality property, which is a key property most path finding algorithms such as Dijkstra’s algorithm rely on. We use extensive simulations to validate our theoretical findings.

DOI
10.1109/infocomwkshps54753.2022.9798254

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

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

Efficient Routing Design Based on Entanglement Flow Loss Effect in Quantum Networks

Zhaoying Wang, Jian Li, Zhonghui Li +4 more

The fundamental technology for the construction of large-scale quantum networks lies in the efficient distribution of remote entanglement among quantum nodes. Entanglement routing tackles the challenge of path selection between two distant end nodes and realizes entanglement distribution through multi-hop entanglement swapping. Given the inherent probability of swapping, entanglement distribution flow always presents inevitable losses. The existing routing works adopt a parallel swapping mode, which only considers the final end-to-end distribution loss effect. This lag of failure detection and complete independence between swapping reduce distribution efficiency. We observe that the sequential swapping mode can improve this defect, but it is not thorough. Thus, in this paper, we explore the entanglement flow loss effect in the sequential entanglement swapping (Loss-SES) process in order to perceive failures earlier and save network resources. Subsequently, we introduce a novel metric to quantify path performance, namely the expected entanglement throughput (EET). Building upon EET, we propose the entanglement routing algorithm MaxEET adapted to the Loss-SES process to maximize EET. For efficient deployment, in the single-request scenario, we determine the optimal routing initiation direction by introducing a bidirectional routing mechanism. In the multi-request scenario, we design a greedy and contention-free iterative routing algorithm to exhaust resources. Based on extensive simulations, the results show the superiority of our proposed Loss-SES mode compared to other modes in terms of throughput, fairness, and utilization.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Jul 1, 2024•5 citations

Statistical Modeling and Latency Optimization for Entanglement Routing in Quantum Networks

Jiyao Liu, Yu Wang

While entanglement swapping enables long-distance quantum connections, it may frequently fail and introduce significant latency. Analyzing the latency of end-to-end (E2E) entanglement distribution is a critical yet not well understood problem. In this paper, we address the latency minimization problem in quantum networks at both the path and network levels. We model the stochastic behavior of entanglement swappings and provide a more accurate statistical representation of E2E latency. By proving the optimal substructure of E2E latency, we propose a Dynamic Programming (DP) algorithm to determine the optimal swapping order for path-level latency minimization. Then leveraging such path-level solution, we further formulate and solve a path-selection based optimization for network-wide latency routing problem as well. To further reduce latency, we also explore the benefits of redundant entanglement resources and propose a greedy algorithm to allocate these resources effectively. Through extensive simulations, we demonstrate the accuracy of our statistical modeling and analysis, the benefits of additional resources in reducing latency, and the superior performance of our proposed solutions over existing approaches at both the path and network levels.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•3 citations

Optimized Generation of Entanglement by Real-Time Ordering of Swapping Operations

Ranjani G. Sundaram, Himanshu Gupta

Long-distance quantum communication in quantum networks faces significant challenges due to the constraints imposed by the no-cloning theorem. Most existing quantum communication protocols rely on the a priori distribution of entanglement pairs (EPs), a process known to incur considerable latency due to its stochastic nature. In this work, we consider the problem of minimizing the latency of establishing an EP across a pair of nodes in a quantum network. While prior research has primarily focused on minimizing the expected generation latency by selecting static entanglement routes and/or swapping trees in advance, our approach considers a real-time adaptive strategy-wherein the order of entanglement-swapping operations (hence, the swapping tree used) is progressively determined at runtime based on the runtime success/failure of the stochastic events. In this context, we present a greedy algorithm that iteratively determines the best route and/or entanglement-swapping operation to perform at each stage based on the current network. We evaluate our schemes on randomly generated networks and observe a reduction in latency of up to 40% from the optimal offline approach.

arXiv:2405.07501•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•9 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
In this paper, we study the properties of path metrics of an entanglement path for a given entanglement swapping order of the path. We show how to efficiently compute the path metrics of an entanglement path for any given swapping order. We show that different entanglement swapping orders for the same path can lead to different expected throughputs. A key finding is that the binary operator corresponding to entanglement swapping along a path is not associative. We further show that the problem of computing an s-t path with maximum expected throughput under any entanglement swapping order does not have the subpath optimality property, which is a key property most path finding algorithms such as Dijkstra’s algorithm rely on. We use extensive simulations to validate our theoretical findings.
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.
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.
The fundamental technology for the construction of large-scale quantum networks lies in the efficient distribution of remote entanglement among quantum nodes. Entanglement routing tackles the challenge of path selection between two distant end nodes and realizes entanglement distribution through multi-hop entanglement swapping. Given the inherent probability of swapping, entanglement distribution flow always presents inevitable losses. The existing routing works adopt a parallel swapping mode, which only considers the final end-to-end distribution loss effect. This lag of failure detection and complete independence between swapping reduce distribution efficiency. We observe that the sequential swapping mode can improve this defect, but it is not thorough. Thus, in this paper, we explore the entanglement flow loss effect in the sequential entanglement swapping (Loss-SES) process in order to perceive failures earlier and save network resources. Subsequently, we introduce a novel metric to quantify path performance, namely the expected entanglement throughput (EET). Building upon EET, we propose the entanglement routing algorithm MaxEET adapted to the Loss-SES process to maximize EET. For efficient deployment, in the single-request scenario, we determine the optimal routing initiation direction by introducing a bidirectional routing mechanism. In the multi-request scenario, we design a greedy and contention-free iterative routing algorithm to exhaust resources. Based on extensive simulations, the results show the superiority of our proposed Loss-SES mode compared to other modes in terms of throughput, fairness, and utilization.
While entanglement swapping enables long-distance quantum connections, it may frequently fail and introduce significant latency. Analyzing the latency of end-to-end (E2E) entanglement distribution is a critical yet not well understood problem. In this paper, we address the latency minimization problem in quantum networks at both the path and network levels. We model the stochastic behavior of entanglement swappings and provide a more accurate statistical representation of E2E latency. By proving the optimal substructure of E2E latency, we propose a Dynamic Programming (DP) algorithm to determine the optimal swapping order for path-level latency minimization. Then leveraging such path-level solution, we further formulate and solve a path-selection based optimization for network-wide latency routing problem as well. To further reduce latency, we also explore the benefits of redundant entanglement resources and propose a greedy algorithm to allocate these resources effectively. Through extensive simulations, we demonstrate the accuracy of our statistical modeling and analysis, the benefits of additional resources in reducing latency, and the superior performance of our proposed solutions over existing approaches at both the path and network levels.
Long-distance quantum communication in quantum networks faces significant challenges due to the constraints imposed by the no-cloning theorem. Most existing quantum communication protocols rely on the a priori distribution of entanglement pairs (EPs), a process known to incur considerable latency due to its stochastic nature. In this work, we consider the problem of minimizing the latency of establishing an EP across a pair of nodes in a quantum network. While prior research has primarily focused on minimizing the expected generation latency by selecting static entanglement routes and/or swapping trees in advance, our approach considers a real-time adaptive strategy-wherein the order of entanglement-swapping operations (hence, the swapping tree used) is progressively determined at runtime based on the runtime success/failure of the stochastic events. In this context, we present a greedy algorithm that iteratively determines the best route and/or entanglement-swapping operation to perform at each stage based on the current network. We evaluate our schemes on randomly generated networks and observe a reduction in latency of up to 40% from the optimal offline approach.
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%.