{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T16:06:36Z","timestamp":1772726796512,"version":"3.50.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:00:00Z","timestamp":1744156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2212232"],"award-info":[{"award-number":["2212232"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,4,9]]},"abstract":"<jats:p>\n            Practical applications of quantum computing depend on fault-tolerant devices with error correction. We study the problem of compiling quantum circuits for quantum computers implementing surface codes. Optimal or near-optimal compilation is critical for both efficiency and correctness. The compilation problem requires (1)\n            <jats:italic toggle=\"yes\">mapping<\/jats:italic>\n            circuit qubits to the device qubits and (2)\n            <jats:italic toggle=\"yes\">routing<\/jats:italic>\n            execution paths between interacting qubits. We solve this problem efficiently and near-optimally with a novel algorithm that exploits the\n            <jats:italic toggle=\"yes\">dependency structure<\/jats:italic>\n            of circuit operations to formulate discrete optimization problems that can be approximated via\n            <jats:italic toggle=\"yes\">simulated annealing<\/jats:italic>\n            , a classic and simple algorithm. Our extensive evaluation shows that our approach is powerful and flexible for compiling realistic workloads.\n          <\/jats:p>","DOI":"10.1145\/3720416","type":"journal-article","created":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T13:48:26Z","timestamp":1744206506000},"page":"57-84","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Dependency-Aware Compilation for Surface Code Quantum Architectures"],"prefix":"10.1145","volume":"9","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-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":[[2025,4,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/314464.314579"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796312733"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.41"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Carlos Ans\u00f3tegui and Felip Many\u00e0. 2004. Mapping problems with finite-domain variables into problems with boolean variables. 1\u201315. https:\/\/doi.org\/10.1007\/11527695_1 10.1007\/11527695_1","DOI":"10.1007\/11527695_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313820"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.020342"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2211.07629"},{"key":"e_1_2_1_10_1","volume-title":"Plingeling and Treengeling Entering the SAT Competition","author":"Biere Armin","year":"2020","unstructured":"Armin Biere, Katalin Fazekas, Mathias Fleury, and Maximillian Heisinger. 2020. CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling Entering the SAT Competition 2020. In Proc. of SAT Competition 2020 \u2013 Solver and Benchmark Descriptions, Tomas Balyo, Nils Froleyks, Marijn Heule, Markus Iser, Matti J\u00e4rvisalo, and Martin Suda (Eds.) (Department of Computer Science Report Series B, Vol. B-2020-1). University of Helsinki, 51\u201353."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-023-06927-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.71.022316"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.21231\/GNT1-HW21"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/872726.806984"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.187"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897538"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-815412-0.00019-X"},{"key":"e_1_2_1_18_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_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2019.5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","unstructured":"M. P. da Silva C. Ryan-Anderson J. M. Bello-Rivas A. Chernoguzov J. M. Dreiling C. Foltz F. Frachon J. P. Gaebler T. M. Gatterman L. Grans-Samuelsson D. Hayes N. Hewitt J. Johansen D. Lucchetti M. Mills S. A. Moses B. Neyenhuis A. Paz J. Pino P. Siegfried J. Strabley A. Sundaram D. Tom S. J. Wernli M. Zanner R. P. Stutz and K. M. Svore. 2024. Demonstration of logical qubits and repeated error correction with better-than-physical error rates. https:\/\/doi.org\/10.48550\/arXiv.2404.02280 arxiv:2404.02280. 10.48550\/arXiv.2404.02280","DOI":"10.48550\/arXiv.2404.02280"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Thomas Erlebach. 2006. Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow. In Efficient Approximation and Online Algorithms - Recent Progress on Classical Combinatorial Optimization Problems and New Applications Evripidis Bampis Klaus Jansen and Claire Kenyon (Eds.) (Lecture Notes in Computer Science Vol. 3484). Springer 97\u2013134. https:\/\/doi.org\/10.1007\/11671541_4 10.1007\/11671541_4","DOI":"10.1007\/11671541_4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. https:\/\/doi.org\/10.48550\/arXiv.1411.4028 arxiv:1411.4028. 10.48550\/arXiv.1411.4028","DOI":"10.48550\/arXiv.1411.4028"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1808.06709"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.86.032324"},{"key":"e_1_2_1_25_1","first-page":"95","article-title":"A new encoding of All Different into SAT","volume":"3","author":"Gent Ian P.","year":"2004","unstructured":"Ian P. Gent and Peter Nightingale. 2004. A new encoding of All Different into SAT. In International Workshop on Modelling and Reformulating Constraint Satisfaction Problems. 3, 95\u2013110.","journal-title":"International Workshop on Modelling and Reformulating Constraint Satisfaction Problems."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-022-05434-1"},{"key":"e_1_2_1_27_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_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462177"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480072"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Alexey Ignatiev Antonio Morgado and Joao Marques-Silva. 2018. PySAT: A Python Toolkit for Prototyping with SAT Oracles. In SAT. 428\u2013437. https:\/\/doi.org\/10.1007\/978-3-319-94144-8_26 10.1007\/978-3-319-94144-8_26","DOI":"10.1007\/978-3-319-94144-8_26"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123949"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597917.2597939"},{"key":"e_1_2_1_35_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_36_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1998.0166"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0370-6"},{"key":"e_1_2_1_38_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_39_1","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6668\/ab8617"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aadd1a"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640362"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/DAC56929.2023.10247760"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-03-05-128"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-05-04-62"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO56248.2022.00077"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","unstructured":"Abtin Molavi Amanda Xu Swamit Tannu and Aws Albarghouthi. 2024. Dependency-Aware Compilation for Surface Code Quantum Architectures. https:\/\/doi.org\/10.48550\/arXiv.2311.18042 arxiv:2311.18042. 10.48550\/arXiv.2311.18042","DOI":"10.48550\/arXiv.2311.18042"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.14934044"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-58603-929-5-75"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195119"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","unstructured":"Ben W. Reichardt David Aasen Rui Chao Alex Chernoguzov Wim van Dam John P. Gaebler Dan Gresh Dominic Lucchetti Michael Mills Steven A. Moses Brian Neyenhuis Adam Paetznick Andres Paz Peter E. Siegfried Marcus P. da Silva Krysta M. Svore Zhenghan Wang and Matt Zanner. 2024. Demonstration of quantum computation and error correction with a tesseract code. https:\/\/doi.org\/10.48550\/arXiv.2409.04628 arxiv:2409.04628. 10.48550\/arXiv.2409.04628","DOI":"10.48550\/arXiv.2409.04628"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.11.041058"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SAT.2024.26"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_55_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_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564751_73"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360546"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO56248.2022.00078"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614300"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3400302.3415620"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA59077.2024.00032"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-05-22-1354"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317859"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2008.43"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SAT.2024.29"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.129.030501"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO57630.2024.10444874"},{"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\/10.1145\/3720416","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:07:53Z","timestamp":1760029673000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,9]]},"references-count":68,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2025,4,9]]}},"alternative-id":["10.1145\/3720416"],"URL":"https:\/\/doi.org\/10.1145\/3720416","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,9]]},"assertion":[{"value":"2024-10-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}