{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T14:15:50Z","timestamp":1784211350657,"version":"3.55.0"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"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>\n                    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\u2019s constraints. This is known as the\n                    <jats:italic toggle=\"yes\">qubit mapping and routing<\/jats:italic>\n                    (\n                    <jats:sc>qmr<\/jats:sc>\n                    ) problem. High-quality\n                    <jats:sc>qmr<\/jats:sc>\n                    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\n                    <jats:sc>qmr<\/jats:sc>\n                    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\n                    <jats:sc>qmr<\/jats:sc>\n                    problem is different, we identify a common core structure\u2014\n                    <jats:italic toggle=\"yes\">device state machine<\/jats:italic>\n                    \u2014that we use to formulate an\n                    <jats:italic toggle=\"yes\">abstract<\/jats:italic>\n                    <jats:sc>qmr<\/jats:sc>\n                    <jats:italic toggle=\"yes\">problem<\/jats:italic>\n                    . Our formulation naturally leads to a compact domain-specific language for specifying\n                    <jats:sc>qmr<\/jats:sc>\n                    problems and a powerful parametric algorithm that can be instantiated for any\n                    <jats:sc>qmr<\/jats:sc>\n                    specification. Our thorough evaluation on case studies of important\n                    <jats:sc>qmr<\/jats:sc>\n                    problems shows that generated compilers are competitive with handwritten, specialized compilers in terms of runtime and solution quality.\n                  <\/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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","unstructured":"2019. IEEE Standard for VHDL Language Reference Manual. IEEE Std 1076-2019 (2019) 1\u2013673. doi:10.1109\/IEEESTD.2019.8938196","DOI":"10.1109\/IEEESTD.2019.8938196"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","unstructured":"2024. IEEE Standard for SystemVerilog\u2013Unified Hardware Design Specification and Verification Language. IEEE Std 1800-2023 (Revision of IEEE Std 1800-2017) (2024) 1\u20131354. doi:10.1109\/IEEESTD.2024.10458102","DOI":"10.1109\/IEEESTD.2024.10458102"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","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 [quant-ph] https:\/\/arxiv.org\/abs\/2501.12470","DOI":"10.1145\/3831246"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","unstructured":"Dolev Bluvstein Simon J. Evered Alexandra A. Geim Sophie H. Li Hengyun Zhou Tom Manovitz Sepehr Ebadi Madelyn Cain Marcin Kalinowski Dominik Hangleiter J. Pablo Bonilla Ataides Nishad Maskara Iris Cong Xun Gao Pedro Sales Rodriguez Thomas Karolyshyn Giulia Semeghini Michael J. Gullans Markus Greiner Vladan Vuleti\u0107 and Mikhail D. Lukin. 2023. Logical quantum processor based on reconfigurable atom arrays. Nature 626 7997 (Dec. 2023) 58\u201365. doi:10.1038\/s41586-023-06927-3","DOI":"10.1038\/s41586-023-06927-3"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.71.022316"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","unstructured":"Center for High Throughput Computing. 2006. Center for High Throughput Computing. doi:10.21231\/GNT1-HW21","DOI":"10.21231\/GNT1-HW21"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","unstructured":"Don Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv preprint quant-ph\/0201067 (2002). doi:10.48550\/arXiv.quant-ph\/0201067","DOI":"10.48550\/arXiv.quant-ph\/0201067"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","unstructured":"Alexander Cowtan Silas Dilkes Ross Duncan Alexandre Krajenbrink Will Simmons and Seyon Sivarajah. 2019. On the Qubit Routing Problem. Leibniz Int. Proc. Inf. 135 (2019) 5:1\u20135:32. arXiv:1902.08091[quant-ph] doi:10.4230\/LIPIcs.TQC.2019.5","DOI":"10.4230\/LIPIcs.TQC.2019.5"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550\/arXiv.1411.4028","DOI":"10.48550\/arXiv.1411.4028"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","unstructured":"Austin G. Fowler Matteo Mariantoni John M. Martinis and Andrew N. Cleland. 2012. Surface codes: Towards practical large-scale quantum computation. Physical Review A 86 3 (sep 2012). doi:10.1103\/physreva.86.032324","DOI":"10.1103\/physreva.86.032324"},{"key":"e_1_3_2_13_2","unstructured":"Google. 2024. Google Quantum AI Roadmap. Google. https:\/\/quantumai.google\/roadmap Accessed: June 18 2025."},{"key":"e_1_3_2_14_2","unstructured":"Google Quantum AI. 2021. Sycamore Spec Sheet. https:\/\/quantumai.google\/hardware\/datasheet\/weber.pdf"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","unstructured":"Google Quantum AI. 2023. Suppressing quantum errors by scaling a surface code logical qubit. Nature 614 7949 (Feb. 2023) 676\u2013681. doi:10.1038\/s41586-022-05434-1","DOI":"10.1038\/s41586-022-05434-1"},{"key":"e_1_3_2_16_2","unstructured":"Google Quantum AI. 2024. Willow Spec Sheet. https:\/\/quantumai.google\/static\/site-assets\/downloads\/willow-spec-sheet.pdf"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","unstructured":"Google Quantum AI and Collaborators. 2024. Quantum error correction below the surface code threshold. Nature (Dec. 2024). doi:10.1038\/s41586-024-08449-y","DOI":"10.1038\/s41586-024-08449-y"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462177"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Clare Horsman Austin GFowler Simon Devitt and Rodney Van Meter. 2012. Surface code quantum computing by lattice surgery. New Journal of Physics 14 12 (dec 2012) 123011. doi:10.1088\/1367-2630\/14\/12\/123011","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480072"},{"key":"e_1_3_2_22_2","unstructured":"IBM. 2025. IBM Quantum Roadmap. IBM. https:\/\/www.ibm.com\/roadmaps\/quantum\/ Accessed: June 18 2025."},{"key":"e_1_3_2_23_2","unstructured":"IBM Quantum. 2025. Quantum processing units. https:\/\/quantum.ibm.com\/services\/resources"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3338843"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123949"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2597917.2597939"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","unstructured":"Ali Javadi-Abhari Matthew Treinish Kevin Krsulich Christopher J. Wood Jake Lishman Julien Gacon Simon Martiel Paul D. Nation Lev S. Bishop Andrew W. Cross Blake R. Johnson and Jay M. Gambetta. 2024. Quantum computing with Qiskit. arXiv:2405.08810[quant-ph] doi:10.48550\/arXiv.2405.08810","DOI":"10.48550\/arXiv.2405.08810"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359630"},{"key":"e_1_3_2_29_2","unstructured":"S.C. Johnson. 1975. YACC: Yet Another Compiler-Compiler. Technical Report Comp. Sci. Tech. Rep. 32. Bell Laboratories."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","unstructured":"D Kielpinski C Monroe and David Wineland. 2002. Architecture for a Large-Scale Ion-Trap Quantum Computer. 417 (2002-01-01 2002). doi:10.1038\/nature00784","DOI":"10.1038\/nature00784"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-023-06096-3"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_3_2_33_2","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."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","unstructured":"Ian Kuon Russell Tessier and Jonathan Rose. 2008. FPGA Architecture: Survey and Challenges. doi:10.1561\/1000000005","DOI":"10.1561\/1000000005"},{"key":"e_1_3_2_35_2","unstructured":"M.E. Lesk. 1975. LEX \u2013 A Lexical Analyzer Generator. Technical Report Comp. Sci. Tech. Rep. 39. Bell Laboratories."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304023"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","unstructured":"Wan-Hsuan Lin Jason Kimko Bochen Tan Nikolaj Bj\u00f8rner and Jason Cong. 2023. Scalable Optimal Layout Synthesis for NISQ Quantum Processors. In 2023 60th ACM\/IEEE Design Automation Conference (DAC). 1\u20136. doi:10.1109\/DAC56929.2023.10247760","DOI":"10.1109\/DAC56929.2023.10247760"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","unstructured":"Daniel Litinski. 2019. A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery. Quantum 3 (March 2019) 128. doi:10.22331\/q-2019-03-05-128","DOI":"10.22331\/q-2019-03-05-128"},{"key":"e_1_3_2_39_2","unstructured":"Abtin Molavi Amanda Xu Ethan Cecchetti Swamit Tannu and Aws Albarghouthi. 2025. Generating Compilers for Qubit Mapping and Routing. arXiv2508.10781 [cs.PL] https:\/\/arxiv.org\/abs\/2508.10781"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","unstructured":"Abtin Molavi Amanda Xu Martin Diges Lauren Pick Swamit S. Tannu and Aws Albarghouthi. 2022. Qubit Mapping and Routing via MaxSAT. 2022 55th IEEE\/ACM International Symposium on Microarchitecture (MICRO) (2022) 1078\u20131091. doi:10.1109\/MICRO56248.2022.00077","DOI":"10.1109\/MICRO56248.2022.00077"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","unstructured":"Abtin Molavi Amanda Xu Swamit Tannu and Aws Albarghouthi. 2025. Dependency-Aware Compilation for Surface Code Quantum Architectures. Proc. ACM Program. Lang. 9 OOPSLA1 Article 82 (April 2025) 28 pages. doi:10.1145\/3720416","DOI":"10.1145\/3720416"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304075"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","unstructured":"Prakash Murali Dripto M. Debroy Kenneth R. Brown and Margaret Martonosi. 2020. Architecting Noisy IntermediateScale Trapped Ion Quantum Computers. In 2020 ACM\/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). 529\u2013542. doi:10.1109\/ISCA45697.2020.00051","DOI":"10.1109\/ISCA45697.2020.00051"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","unstructured":"Julie L. Newcomb Andrew Adams Steven Johnson Rastislav Bodik and Shoaib Kamil. 2020. Verifying and improving Halide\u2019s term rewriting system with program synthesis. Proc. ACM Program. Lang. 4 OOPSLA Article 166 (Nov. 2020) 28 pages. doi:10.1145\/3428234","DOI":"10.1145\/3428234"},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","unstructured":"Michael A. Nielsen and Isaac L. Chuang. 2011. Quantum Computation and Quantum Information: 10th Anniversary Edition(10th ed.). Cambridge University Press USA.","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737959"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","unstructured":"Anouk Paradis Jasper Dekoninck Benjamin Bichsel and Martin Vechev. 2024. Synthetiq: Fast and Versatile Quantum Circuit Synthesis. Proc. ACM Program. Lang. 8 OOPSLA1 Article 96 (April 2024) 28 pages. doi:10.1145\/3649813","DOI":"10.1145\/3649813"},{"key":"e_1_3_2_48_2","unstructured":"Terence Parr. 2013. The Definitive ANTLR 4 Reference (2nd ed.). Pragmatic Bookshelf."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-021-03318-4"},{"key":"e_1_3_2_50_2","unstructured":"Rigetti Computing. 2025. Rigetti Systems. https:\/\/qcs.rigetti.com\/qpus"},{"key":"e_1_3_2_51_2","unstructured":"Rob Gerth. 1997. Concise Promela reference. https:\/\/spinroot.com\/spin\/Man\/Quick.html"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2490301.2451150"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SAT.2024.26"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","unstructured":"P.W. Shor. 1994. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science. 124\u2013134. doi:10.1109\/SFCS.1994.365700","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_2_55_2","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. doi:10.4230\/LIPICS.TQC.2024.1","DOI":"10.4230\/LIPICS.TQC.2024.1"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3168822"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","unstructured":"Bochen Tan Dolev Bluvstein Mikhail Lukin and Jason Cong. 2024. Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors. Quantum 8 (03 2024) 1281. doi:10.22331\/q-2024-03-14-1281","DOI":"10.22331\/q-2024-03-14-1281"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3658617.3697778"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2986138"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304007"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA61900.2025.00030"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA59077.2024.00030"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3569052.3578928"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","unstructured":"Robert Wille Daniel Gro\u00dfe Lisa Teuber Gerhard W. Dueck and Rolf Drechsler. 2008. RevLib: An Online Resource for Reversible Functions and Reversible Circuits. In 38th International Symposium on Multiple Valued Logic (ismvl 2008). 220\u2013225. doi:10.1109\/ISMVL.2008.43","DOI":"10.1109\/ISMVL.2008.43"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591254"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523433"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SAT.2024.29"},{"key":"e_1_3_2_68_2","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 (2025)."},{"key":"e_1_3_2_69_2","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,7,16]],"date-time":"2026-07-16T13:42:30Z","timestamp":1784209350000},"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"}}]}}