Greedy Algorithms for Finding Entanglement Swap Paths in Quantum Networks

The entanglement swap primitive facilitates the establishment of shared entanglement between non-adjacent nodes in a quantum network. This shared entanglement can subsequently be used for executing quantum communication protocols. The fundamental problem in quantum networks is to determine a path for entanglement swapping in response to demands for entanglement sharing between pairs of nodes. We investigate variants of this problem in this work.
We propose a framework of Greedy algorithms that can be tweaked towards optimizing on various objective functions. In conjunction with a novel Spatial and Temporal (split across multiple paths) splitting approach to entanglement routing, we use this framework, which we call GST, to investigate the scenario when the demands are specified in terms of a starting time and a deadline. Considering the fragile nature of quantum memory, “bursty" demands are natural, and therefore the setting is important.
We study the algorithm for maximizing the number of satisfied demands and the number of entangled pairs shared. We report empirical results on the performance against these objective functions, and compare with a naive algorithm that involves neither temporal and spatial splitting of the demands, nor the greedy approach to scheduling the demands.