Maximizing Entanglement Routing Rate in Quantum Networks: Approximation Algorithms

There will be a fast-paced shift from conventional network systems to novel quantum networks that are supported by the quantum entanglement and teleportation, key technologies of the quantum era, to enable secured data transmissions in the next-generation of the Internet. Despite this prospect, migration to quantum networks cannot happen all at once, especially when it comes to quantum routing. In this paper, we focus on the maximizing entanglement routing rate (MERR) problem, which aims to determine entangled routing paths for the maximum number of demands in the quantum network while meeting the network's fidelity. To tackle this problem, we first formulate the MERR problem using an integer linear programming (ILP) model. We then leverage the method of linear programming relaxation to devise two efficient algorithms, including the half-based rounding algorithm (HBRA) and the randomized rounding algorithm (RRA) with a provable approximation ratio for the objective function. Furthermore, to address the challenge of the combinatorial optimization problem in big scale networks, we also propose the path-length-based approach (PLBA) to solve the MERR problem. Finally, we evaluate the performance of our algorithms and show up the success of maximizing the entanglement routing rate.