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

作     者：Sripotchanart, Romtham Si, Weisheng Calheiros, Rodrigo N. Cao, Qing Qiu, Tie 

作者机构：Western Sydney Univ Sch Comp Data & Math Sci Sydney NSW 2150 Australia Univ Tennessee Dept EECS Knoxville TN 37996 USA Tianjin Univ Sch Comp Sci & Technol Tianjin 300350 Peoples R China 

出 版 物：《COMPUTER NETWORKS》 (Comput. Networks)

年 卷 期：2024年第254卷

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Royal Thai Government 

主　　题：Quantum networks Quantum repeater placement Linear programming Node-disjoint paths 

摘      要：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(n(2)), 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.