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

A Fast Heuristic Entanglement Distribution Algorithm for Quantum Repeater Chains

Wenkang Cen, Jinbei Zhang, Kechao Cai, Shi‐Hai Sun, John C. S. Lui

Published Oct 17, 2024• 4 citations
Publisher

Abstract

Entanglement distribution via probabilistic entanglement swapping across a quantum repeater chain connecting two quantum nodes is a challenging problem. The difficulty lies in the exponential number of possible swapping structures within the repeater chain, necessitating efficient search algorithms, especially as the chain length increases. In this paper, we first explore the algorithmic design to facilitate the search for the optimal swapping structure along a repeater chain, aiming to maximize the entanglement distribution rate. Second, we examine the computational complexities of various algorithms and find that prior approaches exhibit excessively high complexities. Thus, we propose an efficient dynamic programming-based algorithm, FastHED, that leverages heuristics to expedite the search for the optimal swapping structure. Our theoretical analysis reveals that the upper bound of the proposed algorithm’s computational complexity is$O(n(\log n)^{3})$(more precisely,$O(n(\log n)^{2} \log \log n)$when$n\le 2^{29}$), a significant improvement over the existing algorithm with a complexity of$O(n^{2} \log n)$, where n denotes the repeater chain’s length. Additionally, we design a best-first framework to evaluate the performance of different algorithms. Numerical results show that our algorithm achieves a higher average entanglement distribution rate than existing algorithms.

DOI
10.1109/tnet.2024.3475378

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

Bayesian Optimization for Repeater Protocols

Lorenzo La Corte, Kenneth Goodenough, Ananda G. Maity +2 more

Efficiently distributing secret keys over long distances remains a critical challenge in the development of quantum networks. "First-generation" quantum repeater chains distribute entanglement by executing protocols composed of probabilistic entanglement generation, swapping and distillation operations. However, finding the protocol that maximizes the secret-key rate is difficult for two reasons. First, calculating the secret-key rate for a given protocol is non-trivial due to experimental imperfections and the probabilistic nature of the operations. Second, the protocol space rapidly grows with the number of nodes, and lacks any clear structure for efficient exploration. To address the first challenge, we build upon the efficient machinery developed by Li et al. [1] and we extend it, enabling numerical calculation of the secret-key rate for heterogeneous repeater chains with an arbitrary number of nodes. For navigating the large, unstructured space of repeater protocols, we implement a Bayesian optimization algorithm, which we find consistently returns the optimal result. Whenever comparisons are feasible, we validate its accuracy against results obtained through brute-force methods. Further, we use our framework to extract insight on how to maximize the efficiency of repeater protocols across varying node configurations and hardware conditions. Our results highlight the effectiveness of Bayesian optimization in exploring the potential of near-term quantum repeater chains.

arXiv:2502.02208•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 31, 2025•2 citations

Optimal Entanglement Swapping in Quantum Repeaters

Evgeny V Shchukin, Peter van Loock

We formulate the problem of finding the optimal entanglement swapping scheme in a quantum repeater chain as a Markov decision process and present its solution for different repeaters' sizes. Based on this, we are able to demonstrate that the commonly used "doubling" scheme for performing probabilistic entanglement swapping of probabilistically distributed entangled qubit pairs in quantum repeaters does not always produce the best possible raw rate. Focusing on this figure of merit, without considering additional probabilistic elements for error suppression such as entanglement distillation on higher "nesting levels," our approach reveals that a power-of-two number of segments has no privileged position in quantum repeater theory; the best scheme can be constructed for any number of segments. Moreover, classical communication can be included into our scheme, and we show how this influences the raw waiting time for different numbers of segments, confirming again the optimality of "nondoubling" in some relevant parameter regimes. Thus, our approach provides the minimal possible waiting time of quantum repeaters in a fairly general physical setting.

arXiv:2109.00793•Physical Review Letters•Apr 13, 2022•63 citations

Entanglement Swapping Scheduling for Quantum Repeater Chains under Decoherence during Classical Communications

Jorge Benito Díaz, Andrés Agustí, Jabier Faba +3 more

First-generation quantum repeaters are essential in distributing entanglement over long distances since they could mitigate losses in optical fiber. Repeaters split the total distance into shorter, easier to generate links. Then, entanglement swapping establishes long range entanglement by performing local measurements at the repeaters and heralding their results. In this work, we develop an analytical model that estimates the impact of decoherence during heralding for a given protocol. Furthermore, we identify a competition between two phenomena: as repeater count increases, so does entanglement generation, but the additive impact of memory decoherence on final entanglement rate increases too. Therefore, we find that an optimal number of repeaters exists. These findings could lead the design of future quantum networks, both in the inter-repeater distance and swapping timings.

quant-pharXiv:2610.07991•Oct 7, 2026•0 citations

A Heuristic Remote Entanglement Distribution Algorithm on Memory-Limited Quantum Paths

Lutong Chen, Kaiping Xue, Jian Li +5 more

Remote entanglement distribution plays a crucial role in large-scale quantum networks, and the key enabler for entanglement distribution is quantum routers (or repeaters) that can extend the entanglement transmission distance. However, the performance of quantum routers is far from perfect yet. Amongst the causes, the limited quantum memories in quantum routers largely affect the rate and efficiency of entanglement distribution. To overcome this challenge, this paper presents a new modeling for the maximization of entanglement distribution rate (EDR) on a memory-limited path, which is then transformed into entanglement generation and swapping sub-problems. We propose a greedy algorithm for short-distance entanglement generation so that the quantum memories can be efficiently used. As for the entanglement swapping sub-problem, we model it using an Entanglement Graph (EG), whose solution is yet found to be at least NP-complete. In light of it, we propose a heuristic algorithm by dividing the original EG into several sub-problems, each of which can be solved using dynamic programming (DP) in polynomial time. By conducting simulations, the results show that our proposed scheme can achieve a high EDR, and the developed algorithm has a polynomial-time upper bound and reasonable average runtime complexity.

IEEE Transactions on Communications•Sep 12, 2022•34 citations

Optimizing repeater schemes for the quantum internet

Kenneth Goodenough, David Elkouss, Stephanie Wehner

The rate at which quantum communication tasks can be performed using direct transmission is fundamentally hindered by the channel loss. Quantum repeaters allow one, in principle, to overcome these limitations, but their introduction necessarily adds an additional layer of complexity to the distribution of entanglement. This additional complexity---along with the stochastic nature of processes such as entanglement generation, Bell swaps, and entanglement distillation---makes finding good quantum repeater schemes nontrivial. We develop an algorithm that can efficiently perform a heuristic optimization over a subset of quantum repeater schemes for general repeater platforms. We find a strong improvement in the generation rate in comparison to an optimization over a simpler class of repeater schemes based on BDCZ (Briegel, D\"ur, Cirac, Zoller) repeater schemes. We use the algorithm to study three different experimental quantum repeater implementations on their ability to distribute entanglement, which we dub information processing implementations, multiplexed elementary pair generation implementations, and combinations of the two. We perform this heuristic optimization of repeater schemes for each of these implementations for a wide range of parameters and different experimental settings. This allows us to make estimates on what are the most critical parameters to improve for entanglement generation, how many repeaters to use, and which implementations perform best in their ability to generate entanglement.

arXiv:2006.12221•Physical Review A•Mar 18, 2021•50 citations
Entanglement distribution via probabilistic entanglement swapping across a quantum repeater chain connecting two quantum nodes is a challenging problem. The difficulty lies in the exponential number of possible swapping structures within the repeater chain, necessitating efficient search algorithms, especially as the chain length increases. In this paper, we first explore the algorithmic design to facilitate the search for the optimal swapping structure along a repeater chain, aiming to maximize the entanglement distribution rate. Second, we examine the computational complexities of various algorithms and find that prior approaches exhibit excessively high complexities. Thus, we propose an efficient dynamic programming-based algorithm, FastHED, that leverages heuristics to expedite the search for the optimal swapping structure. Our theoretical analysis reveals that the upper bound of the proposed algorithm’s computational complexity isO(n(log⁡n)3)O(n(\log n)^{3})O(n(logn)3)(more precisely,O(n(log⁡n)2log⁡log⁡n)O(n(\log n)^{2} \log \log n)O(n(logn)2loglogn)whenn≤229n\le 2^{29}n≤229), a significant improvement over the existing algorithm with a complexity ofO(n2log⁡n)O(n^{2} \log n)O(n2logn), where n denotes the repeater chain’s length. Additionally, we design a best-first framework to evaluate the performance of different algorithms. Numerical results show that our algorithm achieves a higher average entanglement distribution rate than existing algorithms.
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.
Efficiently distributing secret keys over long distances remains a critical challenge in the development of quantum networks. "First-generation" quantum repeater chains distribute entanglement by executing protocols composed of probabilistic entanglement generation, swapping and distillation operations. However, finding the protocol that maximizes the secret-key rate is difficult for two reasons. First, calculating the secret-key rate for a given protocol is non-trivial due to experimental imperfections and the probabilistic nature of the operations. Second, the protocol space rapidly grows with the number of nodes, and lacks any clear structure for efficient exploration. To address the first challenge, we build upon the efficient machinery developed by Li et al. [1] and we extend it, enabling numerical calculation of the secret-key rate for heterogeneous repeater chains with an arbitrary number of nodes. For navigating the large, unstructured space of repeater protocols, we implement a Bayesian optimization algorithm, which we find consistently returns the optimal result. Whenever comparisons are feasible, we validate its accuracy against results obtained through brute-force methods. Further, we use our framework to extract insight on how to maximize the efficiency of repeater protocols across varying node configurations and hardware conditions. Our results highlight the effectiveness of Bayesian optimization in exploring the potential of near-term quantum repeater chains.
We formulate the problem of finding the optimal entanglement swapping scheme in a quantum repeater chain as a Markov decision process and present its solution for different repeaters' sizes. Based on this, we are able to demonstrate that the commonly used "doubling" scheme for performing probabilistic entanglement swapping of probabilistically distributed entangled qubit pairs in quantum repeaters does not always produce the best possible raw rate. Focusing on this figure of merit, without considering additional probabilistic elements for error suppression such as entanglement distillation on higher "nesting levels," our approach reveals that a power-of-two number of segments has no privileged position in quantum repeater theory; the best scheme can be constructed for any number of segments. Moreover, classical communication can be included into our scheme, and we show how this influences the raw waiting time for different numbers of segments, confirming again the optimality of "nondoubling" in some relevant parameter regimes. Thus, our approach provides the minimal possible waiting time of quantum repeaters in a fairly general physical setting.
First-generation quantum repeaters are essential in distributing entanglement over long distances since they could mitigate losses in optical fiber. Repeaters split the total distance into shorter, easier to generate links. Then, entanglement swapping establishes long range entanglement by performing local measurements at the repeaters and heralding their results. In this work, we develop an analytical model that estimates the impact of decoherence during heralding for a given protocol. Furthermore, we identify a competition between two phenomena: as repeater count increases, so does entanglement generation, but the additive impact of memory decoherence on final entanglement rate increases too. Therefore, we find that an optimal number of repeaters exists. These findings could lead the design of future quantum networks, both in the inter-repeater distance and swapping timings.
Remote entanglement distribution plays a crucial role in large-scale quantum networks, and the key enabler for entanglement distribution is quantum routers (or repeaters) that can extend the entanglement transmission distance. However, the performance of quantum routers is far from perfect yet. Amongst the causes, the limited quantum memories in quantum routers largely affect the rate and efficiency of entanglement distribution. To overcome this challenge, this paper presents a new modeling for the maximization of entanglement distribution rate (EDR) on a memory-limited path, which is then transformed into entanglement generation and swapping sub-problems. We propose a greedy algorithm for short-distance entanglement generation so that the quantum memories can be efficiently used. As for the entanglement swapping sub-problem, we model it using an Entanglement Graph (EG), whose solution is yet found to be at least NP-complete. In light of it, we propose a heuristic algorithm by dividing the original EG into several sub-problems, each of which can be solved using dynamic programming (DP) in polynomial time. By conducting simulations, the results show that our proposed scheme can achieve a high EDR, and the developed algorithm has a polynomial-time upper bound and reasonable average runtime complexity.
The rate at which quantum communication tasks can be performed using direct transmission is fundamentally hindered by the channel loss. Quantum repeaters allow one, in principle, to overcome these limitations, but their introduction necessarily adds an additional layer of complexity to the distribution of entanglement. This additional complexity---along with the stochastic nature of processes such as entanglement generation, Bell swaps, and entanglement distillation---makes finding good quantum repeater schemes nontrivial. We develop an algorithm that can efficiently perform a heuristic optimization over a subset of quantum repeater schemes for general repeater platforms. We find a strong improvement in the generation rate in comparison to an optimization over a simpler class of repeater schemes based on BDCZ (Briegel, D\"ur, Cirac, Zoller) repeater schemes. We use the algorithm to study three different experimental quantum repeater implementations on their ability to distribute entanglement, which we dub information processing implementations, multiplexed elementary pair generation implementations, and combinations of the two. We perform this heuristic optimization of repeater schemes for each of these implementations for a wide range of parameters and different experimental settings. This allows us to make estimates on what are the most critical parameters to improve for entanglement generation, how many repeaters to use, and which implementations perform best in their ability to generate entanglement.