{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:29:23Z","timestamp":1776785363855,"version":"3.51.2"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,1,8]]},"abstract":"<jats:p>To evaluate a quantum circuit on a quantum processor, one must find a mapping from circuit qubits to processor qubits and plan the instruction execution while satisfying the processor's constraints. This is known as the qubit mapping and routing (QMR) problem. High-quality QMR solutions are key to maximizing the utility of scarce quantum resources and minimizing the probability of logical errors affecting computation. The challenge is that the landscape of quantum processors is incredibly diverse and fast-evolving. Given this diversity, dozens of papers have addressed the QMR problem for different qubit hardware, connectivity constraints, and quantum error correction schemes by a developing a new algorithm for a particular context. We present an alternative approach: automatically generating qubit mapping and routing compilers for arbitrary quantum processors. Though each QMR problem is different, we identify a common core structure\u2014device state machine\u2014that we use to formulate an abstract QMR problem. Our formulation naturally leads to a compact domain-specific language for specifying QMR problems and a powerful parametric algorithm that can be instantiated for any QMR specification. Our thorough evaluation on case studies of important QMR problems shows that generated compilers are competitive with handwritten, specialized compilers in terms of runtime and solution quality.<\/jats:p>","DOI":"10.1145\/3776720","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:59:43Z","timestamp":1767898783000},"page":"2265-2294","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Generating Compilers for Qubit Mapping and Routing"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-1841-9565","authenticated-orcid":false,"given":"Abtin","family":"Molavi","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2279-5816","authenticated-orcid":false,"given":"Amanda","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7900-8328","authenticated-orcid":false,"given":"Ethan","family":"Cecchetti","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4479-7413","authenticated-orcid":false,"given":"Swamit","family":"Tannu","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4577-175X","authenticated-orcid":false,"given":"Aws","family":"Albarghouthi","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, USA"}]}],"member":"320","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEEESTD.2019.8938196"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEEESTD.2024.10458102"},{"key":"e_1_2_1_3_1","volume-title":"Younis","author":"Bach Bao","year":"2025","unstructured":"Bao Bach, Ilya Safro, and Ed Younis. 2025. Efficient Compilation for Shuttling Trapped-Ion Machines via the Position Graph Architectural Abstraction. arxiv:2501.12470. arxiv:2501.12470"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-023-06927-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.71.022316"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.21231\/GNT1-HW21"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Don Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv preprint quant-ph\/0201067 https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0201067 10.48550\/arXiv.quant-ph\/0201067","DOI":"10.48550\/arXiv.quant-ph\/0201067"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2019.5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. arxiv:1411.4028. https:\/\/doi.org\/10.48550\/arXiv.1411.4028 10.48550\/arXiv.1411.4028","DOI":"10.48550\/arXiv.1411.4028"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.86.032324"},{"key":"e_1_2_1_12_1","volume-title":"Google Quantum AI Roadmap. https:\/\/quantumai.google\/roadmap Accessed","year":"2025","unstructured":"Google. 2024. Google Quantum AI Roadmap. https:\/\/quantumai.google\/roadmap Accessed: June 18, 2025"},{"key":"e_1_2_1_13_1","unstructured":"Google Quantum AI. 2021. Sycamore Spec Sheet. https:\/\/quantumai.google\/hardware\/datasheet\/weber.pdf"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-022-05434-1"},{"key":"e_1_2_1_15_1","unstructured":"Google Quantum AI. 2024. Willow Spec Sheet. https:\/\/quantumai.google\/static\/site-assets\/downloads\/willow-spec-sheet.pdf"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Google Quantum AI and Collaborators. 2024. Quantum error correction below the surface code threshold. Nature Dec. https:\/\/doi.org\/10.1038\/s41586-024-08449-y 10.1038\/s41586-024-08449-y","DOI":"10.1038\/s41586-024-08449-y"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462177"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480072"},{"key":"e_1_2_1_21_1","volume-title":"IBM Quantum Roadmap. https:\/\/www.ibm.com\/roadmaps\/quantum\/ Accessed","author":"IBM.","year":"2025","unstructured":"IBM. 2025. IBM Quantum Roadmap. https:\/\/www.ibm.com\/roadmaps\/quantum\/ Accessed: June 18, 2025"},{"key":"e_1_2_1_22_1","unstructured":"IBM Quantum. 2025. Quantum processing units. https:\/\/quantum.ibm.com\/services\/resources"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338843"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123949"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597917.2597939"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2405.08810"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359630"},{"key":"e_1_2_1_28_1","volume-title":"YACC: Yet Another Compiler-Compiler. Bell Laboratories.","author":"Johnson S.C.","year":"1975","unstructured":"S.C. Johnson. 1975. YACC: Yet Another Compiler-Compiler. Bell Laboratories."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","unstructured":"D Kielpinski C Monroe and David Wineland. 2002. Architecture for a Large-Scale Ion-Trap Quantum Computer. 2002-01-01 https:\/\/doi.org\/10.1038\/nature00784 10.1038\/nature00784","DOI":"10.1038\/nature00784"},{"key":"e_1_2_1_30_1","volume-title":"Ken Xuan Wei","author":"Kim Youngseok","year":"2023","unstructured":"Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al. 2023. Evidence for the utility of quantum computing before fault tolerance. Nature, 618, 7965 (2023), 500\u2013505."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","unstructured":"S. Kirkpatrick C. D. Gelatt and M. P. Vecchi. 1983. Optimization by Simulated Annealing. Science 220 4598 (1983) 671\u2013680. https:\/\/doi.org\/10.1126\/science.220.4598.671 10.1126\/science.220.4598.671","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_32_1","first-page":"020342","article-title":"The complexity of wire-routing and finding minimum area layouts for arbitrary vlsi circuits","volume":"2","author":"Kramer M.R","year":"1984","unstructured":"M.R Kramer and J van Leeuwen. 1984. The complexity of wire-routing and finding minimum area layouts for arbitrary vlsi circuits. Advances in Computing Research, 2 (1984), 020342.","journal-title":"Advances in Computing Research"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Ian Kuon Russell Tessier and Jonathan Rose. 2008. FPGA Architecture: Survey and Challenges. https:\/\/doi.org\/10.1561\/1000000005 10.1561\/1000000005","DOI":"10.1561\/1000000005"},{"key":"e_1_2_1_34_1","unstructured":"M.E. Lesk. 1975. LEX \u2013 A Lexical Analyzer Generator. Bell Laboratories."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304023"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/DAC56929.2023.10247760"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-03-05-128"},{"key":"e_1_2_1_38_1","unstructured":"Abtin Molavi Amanda Xu Ethan Cecchetti Swamit Tannu and Aws Albarghouthi. 2025. Generating Compilers for Qubit Mapping and Routing. arxiv:2508.10781. arxiv:2508.10781"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO56248.2022.00077"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3720416"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304075"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA45697.2020.00051"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428234"},{"key":"e_1_2_1_44_1","volume-title":"Chuang","author":"Nielsen Michael A.","year":"2011","unstructured":"Michael A. Nielsen and Isaac L. Chuang. 2011. Quantum Computation and Quantum Information: 10th Anniversary Edition (10th ed.). Cambridge University Press, USA. isbn:1107002176"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737959"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649813"},{"key":"e_1_2_1_47_1","volume-title":"The Definitive ANTLR 4 Reference","author":"Parr Terence","year":"1934","unstructured":"Terence Parr. 2013. The Definitive ANTLR 4 Reference (2nd ed.). Pragmatic Bookshelf. isbn:1934356999","edition":"2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","unstructured":"J. M. Pino J. M. Dreiling C. Figgatt J. P. Gaebler S. A. Moses M. S. Allman C. H. Baldwin M. Foss-Feig D. Hayes K. Mayer C. Ryan-Anderson and B. Neyenhuis. 2021. Demonstration of the trapped-ion quantum CCD computer architecture. Nature 592 7853 (2021) issn:1476-4687 https:\/\/doi.org\/10.1038\/s41586-021-03318-4 10.1038\/s41586-021-03318-4","DOI":"10.1038\/s41586-021-03318-4"},{"key":"e_1_2_1_49_1","unstructured":"Rigetti Computing. 2025. Rigetti Systems. https:\/\/qcs.rigetti.com\/qpus"},{"key":"e_1_2_1_50_1","unstructured":"Rob Gerth. 1997. Concise Promela reference. https:\/\/spinroot.com\/spin\/Man\/Quick.html"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2490301.2451150"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SAT.2024.26"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","unstructured":"Allyson Silva Xiangyi Zhang Zak Webb Mia Kramer Chan-Woo Yang Xiao Liu Jessica Lemieux Ka-Wai Chen Artur Scherer and Pooya Ronagh. 2024. Multi-qubit Lattice Surgery Scheduling. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPICS.TQC.2024.1 10.4230\/LIPICS.TQC.2024.1","DOI":"10.4230\/LIPICS.TQC.2024.1"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3168822"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-03-14-1281"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658617.3697778"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2986138"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304007"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA61900.2025.00030"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA59077.2024.00030"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3569052.3578928"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2008.43"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591254"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523433"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SAT.2024.29"},{"key":"e_1_2_1_67_1","unstructured":"Chenghong Zhu Xian Wu Zhaohui Yang Jingbo Wang Anbang Wu Shenggen Zheng and Xin Wang. 2025. Quantum Compiler Design for Qubit Mapping and Routing: A Cross-Architectural Survey of Superconducting Trapped-Ion and Neutral Atom Systems. arXiv preprint arXiv:2505.16891."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2846658"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T19:02:56Z","timestamp":1767898976000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":68,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2026,1,8]]}},"alternative-id":["10.1145\/3776720"],"URL":"https:\/\/doi.org\/10.1145\/3776720","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-07-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}