Entanglement in the trees: Optimal entanglement distribution in binary tree quantum network topologies

Quantum entanglement is the most important resource in quantum networks, with no classical equivalent, and therefore, efficient entanglement distribution plays a key role in quantum communications and technologies. Optimal distribution of entanglement in a general network is a known hard problem. In this paper we analyze entanglement distribution via entanglement swapping in tree topologies showing how the problem can be reduced to chordal graph coloring. Our proposed solutions are mathematically sound for any tree network, providing polynomial-time optimal scheduling for entanglement distribution. The binary tree topology requires only one Bell State Measurement device per node, i.e. minimal hardware configuration, so, providing an optimal polynomial-time entanglement distribution algorithm for this topology establishes a fundamental building block that can be extended to more general tree topologies with diverse hardware setups. Through numerical simulation, we present a comprehensive analysis of the requests distribution per timeslot, optimal number of timeslots, variance, and running time, in terms of tree size, request distance bias, and parametrized balance in the tree topology construction. A complete optimality and complexity analysis is also provided.