{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T18:43:17Z","timestamp":1791484997917,"version":"4.3.4"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000015","name":"DOE U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0019040"],"award-info":[{"award-number":["DE-SC0019040"]}],"id":[{"id":"10.13039\/100000015","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":[[2021,1,4]]},"abstract":"<jats:p>We present VOQC, the first fully verified optimizer for quantum circuits, written using the Coq proof assistant. Quantum circuits are expressed as programs in a simple, low-level language called SQIR, a simple quantum intermediate representation, which is deeply embedded in Coq. Optimizations and other transformations are expressed as Coq functions, which are proved correct with respect to a semantics of SQIR programs. SQIR uses a semantics of matrices of complex numbers, which is the standard for quantum computation, but treats matrices symbolically in order to reason about programs that use an arbitrary number of quantum bits. SQIR's careful design and our provided automation make it possible to write and verify a broad range of optimizations in VOQC, including full-circuit transformations from cutting-edge optimizers.<\/jats:p>","DOI":"10.1145\/3434318","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T12:34:24Z","timestamp":1609763664000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":109,"title":["A verified optimizer for Quantum circuits"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2724-0974","authenticated-orcid":false,"given":"Kesha","family":"Hietala","sequence":"first","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6842-5505","authenticated-orcid":false,"given":"Robert","family":"Rand","sequence":"additional","affiliation":[{"name":"University of Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3410-7466","authenticated-orcid":false,"given":"Shih-Han","family":"Hung","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaodi","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2759-9223","authenticated-orcid":false,"given":"Michael","family":"Hicks","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Samson Abramsky and Bob Coecke. 2009. Categorical quantum mechanics. Handbook of quantum logic and quantum structures 2 ( 2009 ) 261-325.","DOI":"10.1016\/B978-0-444-52869-8.50010-4"},{"key":"e_1_2_1_2_1","volume-title":"QPL","author":"Amy Matthew","year":"2018","unstructured":"Matthew Amy. 2018. Towards large-scale functional verification of universal quantum circuits. https:\/\/www.mathstat.dal. ca\/qpl2018\/papers\/QPL_2018_paper_30.pdf. Presented at QPL 2018."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-21500-2_6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Matthew Amy Parsiad Azimzadeh and Michele Mosca. 2018. On the controlled-NOT complexity of controlled-NOT-phase circuits. Quantum Science and Technology 4 1 ( 2018 ).","DOI":"10.1088\/2058-9565\/aad8ca"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD"},{"key":"e_1_2_1_6_1","volume-title":"Svore","author":"Amy Matthew","year":"2017","unstructured":"Matthew Amy, Martin Roetteler, and Krysta M. Svore. 2017. Verified compilation of space-eficient reversible circuits. In Proceedings of the 28th International Conference on Computer Aided Verification (CAV 2017 ). Springer. https:\/\/www. microsoft.com\/en-us\/research\/publication\/verified-compilation-of-space-eficient-reversible-circuits\/"},{"key":"e_1_2_1_7_1","volume-title":"Quantum cryptography: Public key distribution and coin tossing. arXiv preprint arXiv","author":"Bennett Charles H","year":"2003","unstructured":"Charles H Bennett and Gilles Brassard. 2020. Quantum cryptography: Public key distribution and coin tossing. arXiv preprint arXiv: 2003. 06557 ( 2020 )."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386007"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.195.6"},{"key":"e_1_2_1_10_1","unstructured":"Cambridge Quantum Computing Ltd. 2019. pytket. https:\/\/cqcl.github.io\/pytket\/build\/html\/index.html"},{"key":"e_1_2_1_11_1","volume-title":"Toward certified quantum programming. arXiv e-prints ( 2020 ). arXiv","author":"Chareton Christophe","year":"2003","unstructured":"Christophe Chareton, S\u00e9bastien Bardin, Fran\u00e7ois Bobot, Valentin Perrelle, and Benoit Valiron. 2020. Toward certified quantum programming. arXiv e-prints ( 2020 ). arXiv: 2003. 05841 [cs.PL]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Bob Coecke and Ross Duncan. 2009. Interacting quantum observables: Categorical algebra and diagrammatics. New Journal of Physics 13 ( 06 2009 ). https:\/\/doi.org\/10.1088\/ 1367-2630\/13\/4\/043016 10.1088\/1367-2630\/13\/4\/043016","DOI":"10.1088\/1367-2630\/13\/4\/043016"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","unstructured":"The Coq Development Team. 2019. The Coq proof assistant version 8.10.0. https:\/\/doi.org\/10.5281\/zenodo.3476303 10.5281\/zenodo.3476303","DOI":"10.5281\/zenodo.3476303"},{"key":"e_1_2_1_14_1","volume-title":"Gambetta","author":"Cross Andrew W.","year":"2017","unstructured":"Andrew W. Cross, Lev S. Bishop, John A. Smolin, and Jay M. Gambetta. 2017. Open quantum assembly language. arXiv e-prints ( Jul 2017 ). arXiv: 1707.03429 [quant-ph]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37036-6_8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/068\/2762145"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462177"},{"key":"e_1_2_1_19_1","unstructured":"Alexander S Green. 2010. Towards a formally verified functional quantum programming language. Ph.D. Dissertation. University of Nottingham."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0849-4_10"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aad604"},{"key":"e_1_2_1_23_1","volume-title":"Proving Quantum Programs Correct. arXiv","author":"Hietala Kesha","year":"2010","unstructured":"Kesha Hietala, Robert Rand, Shih-Han Hung, Liyi Li, and Michael Hicks. 2020a. Proving Quantum Programs Correct. arXiv: 2010. 01240 [cs.PL]"},{"key":"e_1_2_1_24_1","volume-title":"A Verified Optimizer for Quantum Circuits. arXiv","author":"Hietala Kesha","year":"1912","unstructured":"Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. 2020b. A Verified Optimizer for Quantum Circuits. arXiv: 1912. 02250 [cs.PL]"},{"key":"e_1_2_1_25_1","unstructured":"IBM. [n.d.]. IBM Q5 Tenerife V1.x.x version log. https:\/\/github.com\/Qiskit\/ibmq-device-information\/blob\/master\/backends\/ tenerife\/V1\/version_log.md"},{"key":"e_1_2_1_26_1","volume-title":"ial Staf","author":"Research IBM","year":"2018","unstructured":"IBM Research Editorial Staf. 2018. We have winners!... of the IBM Qiskit developer challenge. https:\/\/www.ibm.com\/ blogs\/research\/2018\/08\/winners-qiskit-developer-challenge\/"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597917.2597939"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209131"},{"key":"e_1_2_1_29_1","volume-title":"Programming Languages and Systems","author":"Jourdan Jacques-Henri","unstructured":"Jacques-Henri Jourdan, Fran\u00e7ois Pottier, and Xavier Leroy. 2012. Validating LR(1) parsers. In Programming Languages and Systems, Helmut Seidl (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 397-416."},{"key":"e_1_2_1_30_1","volume-title":"Reducing T-count with the ZX-calculus. arXiv e-prints ( 2019 ). arXiv","author":"Kissinger Aleks","year":"1903","unstructured":"Aleks Kissinger and John van de Wetering. 2019. Reducing T-count with the ZX-calculus. arXiv e-prints ( 2019 ). arXiv: 1903.10477 [quant-ph]"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.318.14"},{"key":"e_1_2_1_32_1","volume-title":"Quantomatic: A proof assistant for diagrammatic reasoning.","author":"Kissinger Aleks","year":"2015","unstructured":"Aleks Kissinger and Vladimir Zamdzhiev. 2015. Quantomatic: A proof assistant for diagrammatic reasoning. In Automated Deduction-CADE-25, Amy P. Felty and Aart Middeldorp (Eds.). Springer International Publishing, Cham, 326-336."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2172\/366453"},{"key":"e_1_2_1_34_1","volume-title":"Formal verification of a realistic compiler. Commun. ACM 52, 7 (","author":"Leroy Xavier","year":"2009","unstructured":"Xavier Leroy. 2009. Formal verification of a realistic compiler. Commun. ACM 52, 7 ( July 2009 ), 107-115. https:\/\/doi.org\/10\/ c9sb7q"},{"key":"e_1_2_1_35_1","volume-title":"Next steps in quantum computing: computer science's role. arXiv","author":"Martonosi Margaret","year":"1903","unstructured":"Margaret Martonosi and Martin Roetteler. 2019. Next steps in quantum computing: computer science's role. arXiv: 1903. 10541 [cs.ET]"},{"key":"e_1_2_1_36_1","unstructured":"Guillaume Melquiond. 2020. Interval package for Coq. https:\/\/gitlab.inria.fr\/coqinterval\/interval"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2006.35"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Yunseong Nam Neil J. Ross Yuan Su Andrew M. Childs and Dmitri Maslov. 2018. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information 4 1 ( 2018 ) 23. https:\/\/doi.org\/10.1038\/s41534-018-0072-4 10.1038\/s41534-018-0072-4","DOI":"10.1038\/s41534-018-0072-4"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC14.15-16-2"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009894"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.54010"},{"key":"e_1_2_1_42_1","unstructured":"Robert Rand. 2018. Formally verified quantum programming. Ph.D. Dissertation. University of Pennsylvania."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.287.17"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.266.8"},{"key":"e_1_2_1_45_1","volume-title":"The Fourth International Workshop on Coq for Programming Languages.","author":"Rand Robert","year":"2018","unstructured":"Robert Rand, Jennifer Paykin, and Steve Zdancewic. 2018a. Phantom types for quantum programs. The Fourth International Workshop on Coq for Programming Languages."},{"key":"e_1_2_1_46_1","unstructured":"Rigetti Computing. 2019a. Pyquil documentation. http:\/\/pyquil.readthedocs.io\/en\/latest\/"},{"key":"e_1_2_1_47_1","unstructured":"Rigetti Computing. 2019b. The @rigetti optimizing Quil compiler. https:\/\/github.com\/rigetti\/quilc"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-010-0201-2"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129504004256"},{"key":"e_1_2_1_50_1","volume-title":"Contract-based verification of a realistic quantum compiler. arXiv e-prints (","author":"Shi Yunong","year":"2019","unstructured":"Yunong Shi, Xupeng Li, Runzhou Tao, Ali Javadi-Abhari, Andrew W. Cross, Frederic T. Chong, and Ronghui Gu. 2019. Contract-based verification of a realistic quantum compiler. arXiv e-prints ( Aug 2019 ). arXiv: 1908.08963 [quant-ph]"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365701"},{"key":"e_1_2_1_53_1","volume-title":"The First International Workshop on Programming Languages for Quantum Computing.","author":"Singhal Kartik","year":"2020","unstructured":"Kartik Singhal, Robert Rand, and Michael Hicks. 2020. Verified translation between low-level quantum languages. The First International Workshop on Programming Languages for Quantum Computing."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322262"},{"key":"e_1_2_1_55_1","volume-title":"Zeng","author":"Smith Robert S.","year":"2016","unstructured":"Robert S. Smith, Michael J. Curtis, and William J. Zeng. 2016. A practical quantum instruction set architecture. arXiv e-prints (Aug 2016 ). arXiv: 1608.03355 [quant-ph]"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","unstructured":"Damian S. Steiger Thomas H\u00e4ner and Matthias Troyer. 2018. ProjectQ: An open source software framework for quantum computing. Quantum 2 ( 2018 ) 49. https:\/\/doi.org\/10.22331\/q-2018-01-31-49 10.22331\/q-2018-01-31-49","DOI":"10.22331\/q-2018-01-31-49"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304007"},{"key":"e_1_2_1_58_1","volume-title":"Cirq: A python library for NISQ circuits. https:\/\/cirq.readthedocs.io\/en\/stable\/","author":"Developers The Cirq","year":"2019","unstructured":"The Cirq Developers. 2019. Cirq: A python library for NISQ circuits. https:\/\/cirq.readthedocs.io\/en\/stable\/"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049706.2049708"},{"key":"e_1_2_1_60_1","volume-title":"Quantum computing: The good, the bad, and the (not so) ugly! Invited talk","author":"Zamdzhiev Vladimir","unstructured":"Vladimir Zamdzhiev. 2016. Quantum computing: The good, the bad, and the (not so) ugly! Invited talk, Tulane University."},{"key":"e_1_2_1_61_1","volume-title":"An eficient methodology for mapping quantum circuits to the IBM QX architectures. arXiv e-prints (","author":"Zulehner Alwin","year":"2017","unstructured":"Alwin Zulehner, Alexandru Paler, and Robert Wille. 2017. An eficient methodology for mapping quantum circuits to the IBM QX architectures. arXiv e-prints ( Dec 2017 ). arXiv: 1712.04722 [quant-ph]"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434318","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434318","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434318","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:25:15Z","timestamp":1781853915000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":61,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2021,1,4]]}},"alternative-id":["10.1145\/3434318"],"URL":"https:\/\/doi.org\/10.1145\/3434318","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2021-01-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}