{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T17:25:26Z","timestamp":1787592326922,"version":"build-2736575974"},"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\/legalcode"}],"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. Today, the most promising approach is a class of error-correcting codes called\n                    <jats:italic toggle=\"yes\">surface codes.<\/jats:italic>\n                    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":11,"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"}],"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-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":[[2025,4,9]]},"reference":[{"key":"e_1_3_2_1_2","doi-asserted-by":"publisher","DOI":"10.5555\/314464.314579"},{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796312733"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","unstructured":"M. Andrews J. Chuzhoy Sanjeev Khanna and L. Zhang. 2005. Hardness of the undirected edge-disjoint paths problem with congestion. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905). 226\u2013241. https:\/\/doi.org\/10.1109\/SFCS.2005.41","DOI":"10.1109\/SFCS.2005.41"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","unstructured":"Carlos Ans\u00f4tegui 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_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313820"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_8"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.020342"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","unstructured":"Michael E. Beverland Prakash Murali Matthias Troyer Krysta M. Svore Torsten Hoefler Vadym Kliuchnikov Guang Hao Low Mathias Soeken Aarthi Sundaram and Alexander Vaschillo. 2022. Assessing requirements to scale to practical quantum advantage. https:\/\/doi.org\/10.48550\/arXiv.2211.07629 10.48550\/arXiv.2211.07629 arXiv:2211.07629 [quant- ph]","DOI":"10.48550\/arXiv.2211.07629"},{"key":"e_1_3_2_10_2","first-page":"51","volume-title":"Proc, of SAT Competition 2020 - Solver and Benchmark Descriptions (Department of Computer Science Report Series B, Vol. B-2020-1)","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 - Solver and Benchmark Descriptions (Department of Computer Science Report Series B, Vol. B-2020-1), Tomas Balyo, Nils Froleyks, Marijn Heule, Markus Iser, Matti J\u00e4rvisalo, and Martin Suda (Eds.). University of Helsinki, 51\u201353."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-023-06927-3"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.71.022316"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","unstructured":"Center for High Throughput Computing. 2006. Center for High Throughput Computing. https:\/\/doi.org\/10.21231\/GNT1-HW21 10.21231\/GNT1-HW21","DOI":"10.21231\/GNT1-HW21"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/872726.806984"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.187"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897538"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-815412-0.00019-X"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","unstructured":"Don Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv preprint quant- ph\/0201067 (2002). 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_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.quant-ph\/0201067"},{"key":"e_1_3_2_20_2","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 10.48550\/arXiv.2404.02280 arXiv:2404.02280","DOI":"10.48550\/arXiv.2404.02280"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/11671541_4"},{"key":"e_1_3_2_22_2","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. https: \/\/doi.org\/10.48550\/arXiv.l411.4028 arXiv: 1411.4028"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","unstructured":"Austin G. Fowler and Craig Gidney. 2018. Low overhead quantum computation using lattice surgery. arXiv: Quantum Physics (2018). https:\/\/doi.org\/10.48550\/arXiv.1808.06709 10.48550\/arXiv.1808.06709","DOI":"10.48550\/arXiv.1808.06709"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.86.032324"},{"key":"e_1_3_2_25_2","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, Vol. 3. 95\u2013110.","journal-title":"International Workshop on Modelling and Reformulating Constraint Satisfaction Problems"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-022-05434-1"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","unstructured":"Google Quantum AI and Collaborators. 2024. Quantum error correction below the surface code threshold. Nature (Dec. 2024). 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_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462177"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480072"},{"key":"e_1_3_2_32_2","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_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123949"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2597917.2597939"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1998.0166"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","unstructured":"Stavros G. Kolliopoulos and Clifford Stein. 1997. Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs. In Conference on Integer Programming and Combinatorial Optimization. https:\/\/doi.org\/10.1007\/S10107-002-0370-6 10.1007\/S10107-002-0370-6","DOI":"10.1007\/S10107-002-0370-6"},{"issue":"1984","key":"e_1_3_2_38_2","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_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6668\/ab8617"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aaddla"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640362"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","unstructured":"Wan-Hsuan Lin Jason Kimko Boehen Tan Nikolaj Bjorner and Jason Cong. 2023. Scalable Optimal Layout Synthesis for NISQ Quantum Processors. In 2023 60th ACM\/IEEE Design Automation Conference (DAC). . 1\u20136.https:\/\/doi.org\/10.1109\/DAC56929.2023.10247760 10.1109\/DAC56929.2023.10247760","DOI":"10.1109\/DAC56929.2023.10247760"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-03-05-128"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-05-04-62"},{"key":"e_1_3_2_45_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. In 2022 55th IEEE\/ACM International Symposium on Microarchitecture (MICRO)(2022) 1078\u20131091. https:\/\/doi.org\/10.1109\/MICR056248.2022.00077 10.1109\/MICR056248.2022.00077","DOI":"10.1109\/MICR056248.2022.00077"},{"key":"e_1_3_2_46_2","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 10.48550\/arXiv.2311.18042 arXiv:2311.18042 [quant-ph]","DOI":"10.48550\/arXiv.2311.18042"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","unstructured":"Abtin Molavi Amanda Xu Swamit Tannu and Aws Albarghouthi. 2025. Artifact for \u201cDependency-Aware Compilation for Surface Code Quantum Architectures\u201d (DASCOT). https:\/\/doi.org\/10.5281\/zenodo.14934044 10.5281\/zenodo.14934044","DOI":"10.5281\/zenodo.14934044"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-58603-929-5-75"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195119"},{"key":"e_1_3_2_51_2","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 10.48550\/arXiv.2409.04628 arXiv:2409.04628 [quant-ph]","DOI":"10.48550\/arXiv.2409.04628"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.11.041058"},{"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. https:\/\/doi.org\/10.1109\/SFCS.1994.365700 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 - 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_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/11564751_73"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360546"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICR056248.2022.00078"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614300"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3400302.3415620"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA59077.2024.00032"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-05-22-1354"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317859"},{"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. https:\/\/doi.org\/10.1109\/ISMVL.2008.43 10.1109\/ISMVL.2008.43","DOI":"10.1109\/ISMVL.2008.43"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SAT.2024.29"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.129.030501"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO57630.2024.10444874"},{"key":"e_1_3_2_68_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\/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":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T16:29:10Z","timestamp":1787588950000},"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"}}]}}