A Heuristic Approach for Scalable Quantum Repeater Deployment Modeling

Long-distance quantum communication presents a significant challenge due to the degrading fidelity of transmitted qubits. Quantum repeaters are proposed to overcome this issue through Bell measurements on entangled qubit pairs. However, despite its necessity to enable wide-area quantum internet, the deployment cost of quantum repeaters can be prohibitively expensive; thus, developing a quantum repeater deployment model that can strike a balance between cost and effectiveness is essential. In this work, we present novel heuristic models to quickly determine a minimum number of quantum repeaters to deploy in large-scale networks to provide end-to-end connectivity between all end hosts. The results show that, compared to the integer linear programming approach, the heuristic methods can find near-optimal solutions while reducing the execution time from days to seconds when evaluated against several synthetic and real-world networks such as SURFnet and ESnet. As reliability is critical for any network, we demonstrate that the heuristic method can estimate deployment models to endure up to two link/node failures.