{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T14:57:54Z","timestamp":1784300274168,"version":"3.55.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>Approximation errors must be taken into account when compiling quantum programs into a low-level gate set. We present a methodology that tracks such errors automatically and then optimizes accuracy parameters to guarantee a specified overall accuracy while aiming to minimize the implementation cost in terms of quantum gates. The core idea of our approach is to extract functions that specify the optimization problem directly from the high-level description of the quantum program. Then, custom compiler passes optimize these functions, turning them into (near-)symbolic expressions for (1) the total error and (2) the implementation cost (e.g., total quantum gate count). All unspecified parameters of the quantum program will show up as variables in these expressions, including accuracy parameters. After solving the corresponding optimization problem, a circuit can be instantiated from the found solution. We develop two prototype implementations, one in C++ based on Clang\/LLVM, and another using the Q# compiler infrastructure. We benchmark our prototypes on typical quantum computing programs, including the quantum Fourier transform, quantum phase estimation, and Shor's algorithm.<\/jats:p>","DOI":"10.1145\/3428198","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:40:14Z","timestamp":1606261214000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Enabling accuracy-aware Quantum compilers using symbolic resource estimation"],"prefix":"10.1145","volume":"4","author":[{"given":"Giulia","family":"Meuli","sequence":"first","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathias","family":"Soeken","sequence":"additional","affiliation":[{"name":"Microsoft, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Roetteler","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"H\u00e4ner","sequence":"additional","affiliation":[{"name":"Microsoft, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.2562110"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/tcad.2013.2244643"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_1"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568293"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aa9463"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2480359.2429133"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Stephane Beauregard. 2002. Circuit for Shor's algorithm using 2n+3 qubits. Quantum information & computation 3 ( 06 2002 ).  Stephane Beauregard. 2002. Circuit for Shor's algorithm using 2n+3 qubits. Quantum information & computation 3 ( 06 2002 ).","DOI":"10.26421\/QIC3.2-8"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.05.025"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539796300921"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/tc.2008.200"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.95.022316"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4072-3"},{"key":"e_1_2_2_14_1","unstructured":"Don Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph\/0201067 [quant-ph]  Don Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph\/0201067 [quant-ph]"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578855.2535874"},{"key":"e_1_2_2_16_1","unstructured":"Thomas G. Draper. 2000. Addition on a quantum computer. arXiv preprint quant-ph\/0008033 ( 2000 ). arXiv:quant-ph\/0008033  Thomas G. Draper. 2000. Addition on a quantum computer. arXiv preprint quant-ph\/0008033 ( 2000 ). arXiv:quant-ph\/0008033"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.86.032324"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462177"},{"key":"e_1_2_2_19_1","volume-title":"Svore","author":"H\u00e4ner Thomas","year":"2018","unstructured":"Thomas H\u00e4ner , Martin Roetteler , and Krysta M . Svore . 2018 . Managing approximation errors in quantum programs. ( 2018 ). arXiv: 1807.02336 [quant-ph] Thomas H\u00e4ner, Martin Roetteler, and Krysta M. Svore. 2018. Managing approximation errors in quantum programs. ( 2018 ). arXiv: 1807.02336 [quant-ph]"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-0980-2"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290344"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597917.2597939"},{"key":"e_1_2_2_23_1","unstructured":"Alexei Kitaev. 1995. Quantum measurements and the Abelian Stabilizer Problem. arXiv preprint arXiv:quant-ph\/9511026 ( 1995 ). arXiv:quant-ph\/9511026 [quant-ph]  Alexei Kitaev. 1995. Quantum measurements and the Abelian Stabilizer Problem. arXiv preprint arXiv:quant-ph\/9511026 ( 1995 ). arXiv:quant-ph\/9511026 [quant-ph]"},{"key":"e_1_2_2_24_1","volume-title":"Fast and eficient exact synthesis of single qubit unitaries generated by Cliford and gates. Quantum Information & Computation 13 (","author":"Kliuchnikov Vadym","year":"2013","unstructured":"Vadym Kliuchnikov , Dmitri Maslov , and Michele Mosca . 2013. Fast and eficient exact synthesis of single qubit unitaries generated by Cliford and gates. Quantum Information & Computation 13 ( June 2013 ), 607-630. Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. 2013. Fast and eficient exact synthesis of single qubit unitaries generated by Cliford and gates. Quantum Information & Computation 13 ( June 2013 ), 607-630."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.2172\/366453"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-07-12-163"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.92.015003"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC14.15-16-2"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737959"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093333.3009894"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1364\/AOP.361502"},{"key":"e_1_2_2_33_1","first-page":"5","article-title":"The Trotter Step Size Required for Accurate Quantum Simulation of Quantum Chemistry","volume":"15","author":"Poulin David","year":"2015","unstructured":"David Poulin , Matthew B. Hastings , Dave Wecker , Nathan Wiebe , Andrew C. Doberty , and Matthias Troyer . 2015 . The Trotter Step Size Required for Accurate Quantum Simulation of Quantum Chemistry . Quantum Information & Computation 15 , 5 - 6 ( 2015 ), 361-384. David Poulin, Matthew B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doberty, and Matthias Troyer. 2015. The Trotter Step Size Required for Accurate Quantum Simulation of Quantum Chemistry. Quantum Information & Computation 15, 5-6 ( 2015 ), 361-384.","journal-title":"Quantum Information & Computation"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1619152114"},{"key":"e_1_2_2_35_1","volume-title":"Ross and Peter Selinger","author":"Neil","year":"2016","unstructured":"Neil J. Ross and Peter Selinger . 2016 . Optimal ancilla-free Cliford+ T approximation of z-rotations. Quantum Information & Computation 16, 11 & 12 ( 2016 ), 901-953. Neil J. Ross and Peter Selinger. 2016. Optimal ancilla-free Cliford+ T approximation of z-rotations. Quantum Information & Computation 16, 11 & 12 ( 2016 ), 901-953."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-016-1495-5"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_2_38_1","unstructured":"Jonathan M. Smith Neil J. Ross Peter Selinger and Beno\u00eet Valiron. 2014. Quipper: concrete resource estimation in quantum algorithms. arXiv:1412.0625  Jonathan M. Smith Neil J. Ross Peter Selinger and Beno\u00eet Valiron. 2014. Quipper: concrete resource estimation in quantum algorithms. arXiv:1412.0625"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-01-31-49"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2013.6657074"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183895.3183901"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a011"},{"key":"e_1_2_2_43_1","unstructured":"Wolfram Research Inc. 2019. Mathematica Version 12.0. https:\/\/www.wolfram.com\/mathematica Champaign IL.  Wolfram Research Inc. 2019. Mathematica Version 12.0. https:\/\/www.wolfram.com\/mathematica Champaign IL."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049706.2049708"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428198","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:56Z","timestamp":1750197776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":44,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428198"],"URL":"https:\/\/doi.org\/10.1145\/3428198","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}