Minimizing the Number of Drone-Based Repeaters in Deploying Quantum Networks

Deploying quantum networks involves the placement of quantum repeaters, which generate entangled qubits for quantum computers to perform quantum teleportation. Besides placing repeaters on ground devices, there have been efforts towards the use of satellites or drones as repeaters. This paper considers the scenario of using drones due to their cost-efficiency and support for flexible network formation. While several issues in this scenario, such as enhancing network connectivity, have been studied, this paper addresses a new problem: how to minimize the number of drones placed in the air to cover all quantum computers on the ground and make the entire quantum network connected. Given that this problem is NP-hard, we propose a suboptimal but polynomial-time approach for it. Our approach consists of two stages. Stage 1 aims to minimize the number of drones needed to cover the ground computers, and Stage 2 aims to minimize the number of drones needed for connecting the drones returned by Stage 1. Both stages use algorithms of no more than quadratic time complexity. We conduct experiments to determine the best algorithm for the setting of quantum networks from several high-performing existing algorithms and design optimization techniques for existing algorithms. Our experiments confirm that our approach reduces the number of drones placed effectively.