{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T11:26:28Z","timestamp":1784892388601,"version":"3.55.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T00:00:00Z","timestamp":1666310400000},"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":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>\n            We consider the problem of mapping a logical quantum circuit onto a given hardware with limited 2-qubit connectivity. We model this problem as an integer linear program, using a network flow formulation with binary variables that includes the initial allocation of qubits and their routing. We consider several cost functions: an approximation of the fidelity of the circuit, its total depth, and a measure of cross-talk, all of which can be incorporated in the model. Numerical experiments on synthetic data and different hardware topologies indicate that the error rate and depth can be optimized simultaneously without significant loss. We test our algorithm on a large number of quantum volume circuits, optimizing for error rate and depth; our algorithm significantly reduces the number of CNOTs compared to Qiskit\u2019s default transpiler SABRE\u00a0[\n            <jats:xref ref-type=\"bibr\">19<\/jats:xref>\n            ] and produces circuits that, when executed on hardware, exhibit higher fidelity.\n          <\/jats:p>","DOI":"10.1145\/3544563","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T13:25:40Z","timestamp":1655904340000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":48,"title":["Optimal Qubit Assignment and Routing via Integer Programming"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4936-1259","authenticated-orcid":false,"given":"Giacomo","family":"Nannicini","sequence":"first","affiliation":[{"name":"IBM Quantum, IBM T. J.\u00a0Watson Research Center, Yorktown Heights, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1318-1149","authenticated-orcid":false,"given":"Lev S.","family":"Bishop","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM T. J.\u00a0Watson Research Center, Yorktown Heights, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9272-377X","authenticated-orcid":false,"given":"Oktay","family":"G\u00fcnl\u00fck","sequence":"additional","affiliation":[{"name":"Operations Research and Information Engineering, Cornell University, Ithaca, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1234-6386","authenticated-orcid":false,"given":"Petar","family":"Jurcevic","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM T. J.\u00a0Watson Research Center, Yorktown Heights, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"key":"e_1_3_4_2_2","unstructured":"Scott Aaronson and Lijie Chen. 2016. Complexity-theoretic foundations of quantum supremacy experiments. In Proceedings of the 32nd Computational Complexity Conference . 67 pages."},{"issue":"28","key":"e_1_3_4_3_2","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/s10696-015-9213-7","article-title":"Operating room scheduling and rescheduling: A rolling horizon approach","author":"Addis B.","year":"2016","unstructured":"B. Addis, G. Carello, A. Grosso, and E. T\u2018anfani. 2016. Operating room scheduling and rescheduling: A rolling horizon approach. Flex. Serv. Manufact. J.28(1\u20132) (2016), 206\u2013232.","journal-title":"Flex. Serv. Manufact. J."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.2562110"},{"key":"e_1_3_4_5_2","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"Applegate David L.","year":"2006","unstructured":"David L. Applegate, Robert E. Bixby, Va\u0161ek Chvat\u00e1l, and William J. Cook. 2006. The Traveling Salesman Problem: A Computational Study. Princeton University Press."},{"key":"e_1_3_4_6_2","article-title":"Quantum routing with fast reversals","author":"Bapat Aniruddha","year":"2021","unstructured":"Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Samuel King, Eddie Schoute, and Hrishee Shastri. 2021. Quantum routing with fast reversals. arXiv:2103.03264. Retrieved from https:\/\/arxiv.org\/abs\/2103.03264.","journal-title":"arXiv:2103.03264"},{"key":"e_1_3_4_7_2","article-title":"Nearly optimal time-independent reversal of a spin chain","author":"Bapat Aniruddha","year":"2020","unstructured":"Aniruddha Bapat, Eddie Schoute, Alexey V. Gorshkov, and Andrew M. Childs. 2020. Nearly optimal time-independent reversal of a spin chain. arXiv:2003.02843. Retrieved from https:\/\/arxiv.org\/abs\/2003.02843.","journal-title":"arXiv:2003.02843"},{"issue":"267","key":"e_1_3_4_8_2","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/j.ejor.2017.12.004","article-title":"A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach","author":"Bertazzi L.","year":"2018","unstructured":"L. Bertazzi and F. Maggioni. 2018. A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach. Eur. J. Operat. Res.267(2) (2018), 555\u2013569.","journal-title":"Eur. J. Operat. Res."},{"key":"e_1_3_4_9_2","article-title":"Depth-optimal quantum circuit placement for arbitrary topologies","author":"Bhattacharjee Debjyoti","year":"2017","unstructured":"Debjyoti Bhattacharjee and Anupam Chattopadhyay. 2017. Depth-optimal quantum circuit placement for arbitrary topologies. arXiv:1703.08540. Retrieved from https:\/\/arxiv.org\/abs\/1703.08540.","journal-title":"arXiv:1703.08540"},{"key":"e_1_3_4_10_2","article-title":"Clifford circuit optimization with templates and symbolic Pauli gates","author":"Bravyi Sergey","year":"2021","unstructured":"Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov. 2021. Clifford circuit optimization with templates and symbolic Pauli gates. arXiv:2105.02291. Retrieved from https:\/\/arxiv.org\/abs\/2105.02291.","journal-title":"arXiv:2105.02291"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.38.5.884"},{"key":"e_1_3_4_12_2","series-title":"Proceedings of the 14th Conference on the Theory of Quantum Computation, Communication and Cryptography,","first-page":"1","volume":"135","author":"Childs Andrew M.","year":"2019","unstructured":"Andrew M. Childs, Eddie Schoute, and Cem M. Unsal. 2019. Circuit transformations for quantum architectures. In Proceedings of the 14th Conference on the Theory of Quantum Computation, Communication and Cryptography,Leibniz International Proceedings in Informatics, Vol. 135. 1\u201324."},{"key":"e_1_3_4_13_2","unstructured":"IBM ILOG Cplex. 2019. V12.10: User\u2019s Manual for CPLEX. Retrieved from https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio."},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.100.032328"},{"issue":"67","key":"e_1_3_4_15_2","first-page":"1","article-title":"Control of energy storage with market impact: Lagrangian approach and horizons","year":"2019","unstructured":"James Cruise, Lisa Flatley, Richard Gibbens, and Stan Zachary. 2019. Control of energy storage with market impact: Lagrangian approach and horizons. Operat. Res.67(1) (2019), 1\u20139.","journal-title":"Operat. Res."},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1111\/deci.12481"},{"key":"e_1_3_4_17_2","unstructured":"LLC Gurobi Optimization. 2021. Gurobi Optimizer Reference Manual. Retrieved from http:\/\/www.gurobi.com."},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.60.1888"},{"key":"e_1_3_4_19_2","doi-asserted-by":"crossref","DOI":"10.1088\/2058-9565\/abe519","article-title":"Demonstration of quantum volume 64 on a superconducting quantum computing system","author":"Jurcevic Petar","year":"2021","unstructured":"Petar Jurcevic, Ali Javadi-Abhari, Lev S. Bishop, Isaac Lauer, Daniela Borgorin, Markus Brink, Lauren Capelluto, Oktay Gunluk, Toshinari Itoko, Naoki Kanazawa, et\u00a0al. 2021. Demonstration of quantum volume 64 on a superconducting quantum computing system. Quant. Sci. Technol. 6, 2 (2021), 025020.","journal-title":"Quant. Sci. Technol."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304023"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.917562"},{"issue":"2","key":"e_1_3_4_22_2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.5267\/j.uscm.2014.4.003","article-title":"Rolling horizon-based heuristic to solve a multi-level general lot sizing and scheduling problem with multiple machines in job shop manufacturing system","author":"Mohammadi M.","year":"2014","unstructured":"M. Mohammadi and Poursabzi. 2014. Rolling horizon-based heuristic to solve a multi-level general lot sizing and scheduling problem with multiple machines in job shop manufacturing system. Uncert. Supply Chain Manage.2(3) (2014), 167\u2013178.","journal-title":"Uncert. Supply Chain Manage."},{"key":"e_1_3_4_23_2","article-title":"A polynomial size model with implicit swap gate counting for exact qubit reordering","author":"Mulderij Jesse","year":"2020","unstructured":"Jesse Mulderij, Karen I. Aardal, Irina Chiscop, and Frank Phillipson. 2020. A polynomial size model with implicit swap gate counting for exact qubit reordering. arXiv:2009.08748. Retrieved from https:\/\/arxiv.org\/abs\/2009.08745.","journal-title":"arXiv:2009.08748"},{"key":"e_1_3_4_24_2","first-page":"1001","volume-title":"Proceedings of the 25th International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Murali Prakash","year":"2020","unstructured":"Prakash Murali, David C. McKay, Margaret Martonosi, and Ali Javadi-Abhari. 2020. Software mitigation of crosstalk on noisy intermediate-scale quantum computers. In Proceedings of the 25th International Conference on Architectural Support for Programming Languages and Operating Systems. 1001\u20131016."},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.01.037"},{"key":"e_1_3_4_26_2","article-title":"Nuwa: A quantum circuit transpiler based on a finite-horizon heuristic for placement and routing","author":"Ren Shengru","year":"2021","unstructured":"Shengru Ren, KaWai Chen, Navid Ghadermarzy, Brandon Nguyen, Yanhao Huang, and Pooya Ronagh. 2021. Nuwa: A quantum circuit transpiler based on a finite-horizon heuristic for placement and routing. arXiv:2110.00592. Retrieved from https:\/\/arxiv.org\/abs\/2110.00592.","journal-title":"arXiv:2110.00592"},{"key":"e_1_3_4_27_2","unstructured":"Eddie Schoute Cem Unsal and Andrew Childs. 2019. Arct: Architecture-respecting Circuit Transformations. Retrieved from https:\/\/gitlab.umiacs.umd.edu\/amchilds\/arct."},{"key":"e_1_3_4_28_2","first-page":"113","volume-title":"Proceedings of the International Symposium on Code Generation and Optimization","author":"Siraichi Marcos Yukio","year":"2018","unstructured":"Marcos Yukio Siraichi, Vin\u00edcius Fernandes dos Santos, Sylvain Collange, and Fernando Magno Quint\u00e3o Pereira. 2018. Qubit allocation. In Proceedings of the International Symposium on Code Generation and Optimization. 113\u2013125."},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8e92"},{"issue":"5","key":"e_1_3_4_30_2","first-page":"1","article-title":"Mathematical formulation of quantum circuit design problems in networks of quantum computers","volume":"19","author":"Houte R. van","year":"2020","unstructured":"R. van Houte, J Mulderij, T. Attema, I. Chiscop, and F. Phillipson. 2020. Mathematical formulation of quantum circuit design problems in networks of quantum computers. Quant. Inf. Process. 19, 5 (2020), 1\u201322.","journal-title":"Quant. Inf. Process."},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-020-02901-4"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544563","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3544563","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:21Z","timestamp":1750178781000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544563"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,21]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3544563"],"URL":"https:\/\/doi.org\/10.1145\/3544563","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,21]]},"assertion":[{"value":"2021-06-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-06","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}