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

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.