{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T07:12:27Z","timestamp":1771571547772,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,5,27]]},"abstract":"<jats:p>Quantum networks are essential infrastructure for enabling large-scale and long-distance quantum communications but face significant challenges in routing optimization and resource allocation due to their probabilistic nature and quantum resource limitations. Existing approaches typically tackle these problems in isolation, often by simply applying classical routing algorithms, maximizing the overall profit to allocate resources without considering fairness, or improving fairness in an ad-hoc way without a rigorous model. This paper proposes a general framework to systematically address these challenges. First, we conduct a thorough analysis of quantum network metrics using routing algebra as the mathematical foundation, and design provably optimal routing algorithms to tackle the unique challenges arising from their probabilistic characteristics. Second, we formulate an optimization model that simultaneously considers fairness among concurrent requests while respecting various quantum resource constraints, and design efficient near-optimal heuristics to solve it. The proposed framework provides both theoretical insights and practical solutions for the design and management of future quantum networks.<\/jats:p>","DOI":"10.1145\/3727129","type":"journal-article","created":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T09:43:35Z","timestamp":1749030215000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Quantum Network Optimization: From Optimal Routing to Fair Resource Allocation"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6611-9176","authenticated-orcid":false,"given":"Zhaozhen","family":"Wang","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6487-9526","authenticated-orcid":false,"given":"Xingang","family":"Shi","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China and Zhongguancun Laboratory, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7659-3178","authenticated-orcid":false,"given":"Zhengfeng","family":"Ji","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China and Zhongguancun Laboratory, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-0037-2777","authenticated-orcid":false,"given":"Xia","family":"Yin","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China and Zhongguancun Laboratory, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Quantum cryptography: Public key distribution and coin tossing. Theoretical computer science","author":"Bennett Charles H","year":"2014","unstructured":"Charles H Bennett and Gilles Brassard. 2014. Quantum cryptography: Public key distribution and coin tossing. Theoretical computer science, Vol. 560 (2014), 7--11."},{"key":"e_1_2_1_2_1","volume-title":"Nonlinear Programming","author":"Bertsekas Dimitri","unstructured":"Dimitri Bertsekas. 2016. Nonlinear Programming. Athena Scientific."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2017.2763325"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2024.110672"},{"key":"e_1_2_1_5_1","unstructured":"M Canteri ZX Koong J Bate A Winkler V Krutyanskiy and BP Lanyon. 2024. A photon-interfaced ten qubit quantum network node. (2024). arxiv: 2406.09480"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2018.06.014"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2020.3028172"},{"key":"e_1_2_1_8_1","volume-title":"Distributed routing in a quantum internet. arxiv","author":"Chakraborty Kaushik","year":"1907","unstructured":"Kaushik Chakraborty, Filip Rozpedek, Axel Dahlberg, and Stephanie Wehner. 2019. Distributed routing in a quantum internet. arxiv: 1907.11630"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.05.025"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SMARTCOMP55677.2022.00032"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_12_1","volume-title":"Quantum cryptography based on Bell's theorem. Physical review letters","author":"Ekert Artur K","year":"1991","unstructured":"Artur K Ekert. 1991. Quantum cryptography based on Bell's theorem. Physical review letters, Vol. 67, 6 (1991), 661."},{"key":"e_1_2_1_13_1","volume-title":"Computers and intractability","author":"Garey Michael R","unstructured":"Michael R Garey and David S Johnson. 1979. Computers and intractability. Vol. 174. W. H. Freeman & Co."},{"key":"e_1_2_1_14_1","volume-title":"Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Mathematical programming","author":"Gavish Bezalel","year":"1985","unstructured":"Bezalel Gavish and Hasan Pirkul. 1985. Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Mathematical programming, Vol. 31 (1985), 78--105."},{"key":"e_1_2_1_15_1","unstructured":"Gurobi Optimization LLC. 2025. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.25080\/TCWV9851"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2601796"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386367.3431293"},{"key":"e_1_2_1_19_1","volume-title":"Qibin Sun, and Jun Lu.","author":"Li Zhonghui","year":"2023","unstructured":"Zhonghui Li, Kaiping Xue, Jian Li, Lutong Chen, Ruidong Li, Zhaoying Wang, Nenghai Yu, David SL Wei, Qibin Sun, and Jun Lu. 2023. Entanglement-assisted quantum networks: Mechanics, enabling technologies, challenges, and research directions. IEEE Communications Surveys & Tutorials (2023)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.99.022337"},{"key":"e_1_2_1_21_1","unstructured":"Stuart Mitchell Michael O'Sullivan and Iain Dunning. 2011. Pulp: a linear programming toolkit for python. https:\/\/optimization-online.org\/2011\/09\/3178"},{"key":"e_1_2_1_22_1","volume-title":"An algorithm for the multidimensional multiple-choice knapsack problem. IEICE transactions on fundamentals of electronics, communications and computer sciences","author":"Moser Martin","year":"1997","unstructured":"Martin Moser, Dusan P Jokanovic, and Norio Shiratori. 1997. An algorithm for the multidimensional multiple-choice knapsack problem. IEICE transactions on fundamentals of electronics, communications and computer sciences, Vol. 80, 3 (1997), 582--589."},{"key":"e_1_2_1_23_1","volume-title":"Experimental entanglement swapping: entangling photons that never interacted. Physical review letters","author":"Pan Jian-Wei","year":"1998","unstructured":"Jian-Wei Pan, Dik Bouwmeester, Harald Weinfurter, and Anton Zeilinger. 1998. Experimental entanglement swapping: entangling photons that never interacted. Physical review letters, Vol. 80, 18 (1998), 3891."},{"key":"e_1_2_1_24_1","volume-title":"Nature","volume":"410","author":"Pan Jian-Wei","year":"2001","unstructured":"Jian-Wei Pan, Christoph Simon, \u010caslav Brukner, and Anton Zeilinger. 2001. Entanglement purification for quantum communication. Nature, Vol. 410, 6832 (2001), 1067--1070."},{"key":"e_1_2_1_25_1","volume-title":"Routing entanglement in the quantum internet. npj Quantum Information","author":"Pant Mihir","year":"2019","unstructured":"Mihir Pant, Hari Krovi, Don Towsley, Leandros Tassiulas, Liang Jiang, Prithwish Basu, Dirk Englund, and Saikat Guha. 2019. Routing entanglement in the quantum internet. npj Quantum Information, Vol. 5, 1 (2019), 25."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCA.2005.851140"},{"key":"e_1_2_1_27_1","volume-title":"Carlo Ottaviani, and Leonardo Banchi","author":"Pirandola Stefano","year":"2017","unstructured":"Stefano Pirandola, Riccardo Laurenza, Carlo Ottaviani, and Leonardo Banchi. 2017. Fundamental limits of repeaterless quantum communications. Nature communications, Vol. 8, 1 (2017), 1--15."},{"key":"e_1_2_1_28_1","volume-title":"Nature","volume":"429","author":"Riebe Mark","year":"2004","unstructured":"Mark Riebe, H H\u00e4ffner, CF Roos, W H\u00e4nsel, J Benhelm, GPT Lancaster, TW K\u00f6rber, C Becher, Ferdinand Schmidt-Kaler, DFV James, et al. 2004. Deterministic quantum teleportation with atoms. Nature, Vol. 429, 6993 (2004), 734--737."},{"key":"e_1_2_1_29_1","unstructured":"Eddie Schoute Laura Mancinska Tanvirul Islam Iordanis Kerenidis and Stephanie Wehner. 2016. Shortcuts to quantum network routing. (2016). arxiv: 1610.05238"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3405853"},{"key":"e_1_2_1_31_1","volume-title":"Concurrent Entanglement Routing for Quantum Networks: Model and Designs","author":"Shi Shouqian","year":"2024","unstructured":"Shouqian Shi, Xiaoxue Zhang, and Chen Qian. 2024. Concurrent Entanglement Routing for Quantum Networks: Model and Designs. IEEE\/ACM Transactions on Networking (2024)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3405864"},{"key":"e_1_2_1_33_1","volume-title":"Nature","volume":"299","author":"Wootters William K","year":"1982","unstructured":"William K Wootters and Wojciech H Zurek. 1982. A single quantum cannot be cloned. Nature, Vol. 299, 5886 (1982), 802--803."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.104.062409"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2008.222"},{"key":"e_1_2_1_36_1","volume-title":"Finding the k shortest loopless paths in a network. management Science","author":"Yen Jin Y","year":"1971","unstructured":"Jin Y Yen. 1971. Finding the k shortest loopless paths in a network. management Science, Vol. 17, 11 (1971), 712--716."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM42981.2021.9488850"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM48880.2022.9796814"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727129","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:31:07Z","timestamp":1755898267000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,27]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,27]]}},"alternative-id":["10.1145\/3727129"],"URL":"https:\/\/doi.org\/10.1145\/3727129","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,27]]},"assertion":[{"value":"2025-06-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}