A Fast Heuristic Entanglement Distribution Algorithm for Quantum Repeater Chains

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n(\log n)^{3})$ </tex-math></inline-formula> (more precisely, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n(\log n)^{2} \log \log n)$ </tex-math></inline-formula> when<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n\le 2^{29}$ </tex-math></inline-formula>), a significant improvement over the existing algorithm with a complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n^{2} \log n)$ </tex-math></inline-formula>, 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.