A two-step linear programming approach for repeater placement in large-scale quantum networks

Thanks to the applications such as Quantum Key Distribution and Distributed Quantum Computing, the deployment of quantum networks is gaining great momentum. A major component in quantum networks is repeaters, which are essential for reducing the error rate of qubit transmission for long-distance links. However, repeaters are expensive devices, so minimizing the number of repeaters placed in a quantum network while satisfying performance requirements becomes an important problem. Existing solutions typically solve this problem optimally by formulating an Integer Linear Program (ILP). However, the number of variables in their ILPs is O(n2), where n is the number of nodes in a network. This incurs infeasible running time when the network scale is large. To overcome this drawback, this paper proposes to solve the repeater placement problem by two steps, with each step using a linear program of a much smaller scale with O(n) variables. Although this solution is not optimal, it dramatically reduces the time complexity, making it practical for large-scale networks. Moreover, it constructs networks that have higher node connectivity than those by existing solutions, since it deploys slightly more number of repeaters into networks. Our extensive experiments on both synthetic and real-world network topologies verified our claims.