Towards Optimal Orders for Entanglement Swapping in Path Graphs: A Greedy Approach
Van Sy Mai, Abderrahim Amlou, Amar Abane, Abdella Battou · 2025
Read Towards Optimal Orders for Entanglement Swapping in Path Graphs: A Greedy Approach by Van Sy Mai, Abderrahim Amlou, Amar Abane, Abdella Battou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14040.txt.
Introduction
Quantum networks will relay entanglement along chains of repeaters, and the order in which links are swapped decides how fast end-to-end pairs arrive. Van Sy Mai and co-authors tackle that ordering problem in this 2025 paper, for paths where nodes and links differ in quality. The number of possible orders explodes as paths grow, and scoring one order is itself costly.
Their first tool is a fast approximation for the outcome of a swap, cheap enough to solve small paths exactly. For large paths, a greedy rule picks the next swap by a local score: the expected pairs a swap would yield, updated as choices accumulate. Simulations on a general quantum network tool show the approach is both fast and effective.
Catalog record
| CREATOR | Van Sy Mai, Abderrahim Amlou, Amar Abane, Abdella Battou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-14040
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards Optimal Orders for Entanglement Swapping in Path Graphs: A Greedy Approach Thanks: Certain commercial entities, equipment, or materials may be identified in this document in order to describe an experimental procedure or concept adequately. Such identification is not intended to imply recommendation or endorsement by the National Institute of Standards and Technology, nor is it intended to imply that the entities, materials, or equipment are necessarily the best available for the purpose. Van Sy Mai, Abderrahim Amlou, Amar Abane, Abdella Battou Abstract 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. I Introduction Entanglement swapping is a fundamental operation in quantum networks that extends entanglement over long distances by linking shorter entangled segments through intermediate nodes (i.e., repeaters) [ 3 , 8 ] . The efficiency of this process depends heavily on the swapping policy, which determines the rules in making swapping decisions along a path [ 7 , 6 ] . Swapping approaches can be distinguished by the knowledge required to make a swapping decision at a node [ 1 ] . With unheralded swapping, nodes locally perform swapping without awaiting the outcomes of other nodes [ 13 ] . In this policy, nodes carry out swapping operations independently and in parallel once adjacent quantum links are available. Although simple, unheralded swapping often results in lower success probabilities and inefficient resource utilization due to the lack of coordination among nodes. In contrast, heralded swapping instructs nodes in a path to make swapping decisions based on the outcomes of other nodes, giving rise to a swapping order for the path in each end-to-end (E2E) entanglement distribution. This improves the E2E entanglement rate and fidelity, at the expense of increasing the amount of classical signaling [ 11 ] . Heralded swapping policies can be categorized as either static or dynamic. Static policies predefine the swapping order before execution [ 18 ] , ensuring predictable operation but providing limited optimization to maximize throughput, especially in heterogeneous networks where link capacities and entanglement success rates vary. Dynamic policies, in contrast, determine swapping decisions (thus, swapping order) on a path basis and in real time based on the availability of entanglement (e.g., along a path) [ 12 ] . By dynamically adapting to network conditions, such policies can lead to optimal swapping decisions but introduce additional signaling overhead, latency, and coordination complexity. A key challenge in optimizing entanglement swapping arises from the heterogeneity of quantum networks, where quantum channels can have different capacities and lengths, leading to different entanglement generation success probabilities and rates [ 14 ] . Unlike many prior works that assume unit-capacity quantum channels and uniform success probabilities for entanglement generation and swapping, we tackle the heterogeneity issue for path graphs, where nodes can have different swapping probabilities and quantum channels among them have non-uniform capacities and entanglement generation success probabilities. Additionally, we assume that swapping within a node can be performed between any pair of locally held qubits, allowing for more flexible swapping strategies. In this work, we focus on static swapping policies and propose heuristics for efficiently evaluating and comparing different swapping orders. Specifically, to address the computational challenges associated with computing the expected throughput of a path with high link capacities, we introduce an approximation technique that significantly reduces complexity while maintaining high accuracy. Then to avoid searching in an exponentially vast array of possible swapping orders, we develop a greedy selection algorithm that assigns a swapping score to each node, prioritizing swaps based on expected entanglement throughput. Our approach is designed to scale efficiently to paths with multiple hops and large capacities, making it particularly suitable for heterogeneous quantum networks. We also present an application of our approach in optimizing not just swapping orders but also memory allocation for each link in a path. Through extensive simulations, we demonstrate that our heuristic achieves significantly higher (and often the highest) entanglement generation rates than conventional static policies while maintaining efficient resource utilization. The rest of this paper is organized as follows. Related work is described in Section II . The problem formulation is given in Section III , followed by our main results in Section IV . Section V presents numerical results to illustrate the usefulness of our approach. Finally, conclusions are given in Section VI . Notation : \mathbb{E}[X] denotes the expected its value of a random variable X . \mathcal{B} and \mathcal{N} denote Binomial and Normal distributions, respectively. We represent vectors using bold letters. II Related Work Swapping can be classified into two main categories: memory-less and memory-based (or synchronous and asynchronous protocols, respectively). In memory-less swapping, entanglements along a path must be generated simultaneously, requiring strict synchronization across routers. This approach yields high fidelity but suffers from low generation rates due to the need to restart the entire process upon any failure. In contrast, memory-based swapping allows qubits to be stored and swapped asynchronously, making the process more resilient to failures, thereby increasing the overall throughput and efficiency [ 6 ] . Several policies exist in this category: \bullet Sequential: Nodes perform swapping in a linear order, e.g., left to right. While simple, this method incurs high wait times and classical signaling due to its sequential nature [ 15 ] . \bullet Doubling: Nodes swap following a binary tree structure. This approach achieves logarithmic steps, optimizing the generation rate for homogeneous chains [ 4 , 21 ] . \bullet Parallel: All nodes perform swapping simultaneously in a single step, but the process restarts if any entanglement or swapping fails, leading to lower generation rates [ 7 ] . \bullet Ad-hoc: Swapping is based on the local or quasi-local state of the path, leading to dynamic order execution. Fully-local policies, such as random swap-as-soon-as-possible (swap-asap), where nodes execute swapping based only on locally available entanglements, are commonly used [ 9 , 13 ] . The work in [ 11 ] proposes quasi-local policies, such as Strongest