{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T20:12:51Z","timestamp":1784837571689,"version":"3.55.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Swiss National Science Foundation SNSF","award":["200021_207967\\\/1"],"award-info":[{"award-number":["200021_207967\\\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,4,29]]},"abstract":"<jats:p>To implement quantum algorithms on quantum computers it is crucial to decompose their operators into the limited gate set supported by those computers. Unfortunately, existing works automating this essential task are generally slow and only applicable to narrow use cases.We present Synthetiq, a method to synthesize quantum circuits implementing a given specification over arbitrary finite gate sets, which is faster and more versatile than existing works. Synthetiq utilizes Simulated Annealing instantiated with a novel, domain-specific energy function that allows developers to leverage partial specifications for better efficiency. Synthetiq further couples this synthesis method with a custom simplification pass, to ensure efficiency of the found circuits.<\/jats:p>\n          <jats:p>We experimentally demonstrate that Synthetiq can generate better implementations than were previously known for multiple relevant quantum operators including RCCCX, CCT, CCiSWAP, C\u221aSWAP, and C\u221aiSWAP. Our extensive evaluation also demonstrates Synthetiq frequently outperforms a wide variety of more specialized tools in their own domains, including (i)\u2004\u200dthe well-studied task of synthesizing fully specified operators in the Clifford+T gate set, (ii)\u2004\u200d\u0454-approximate synthesis of multi-qubit operators in the same gate set, and (iii)\u2004\u200dsynthesis tasks with custom gate sets. On all those tasks, Synthetiq is typically one to two orders of magnitude faster than previous state-of-the-art and can tackle problems that were previously out of the reach of any synthesis tool.<\/jats:p>","DOI":"10.1145\/3649813","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T17:53:50Z","timestamp":1714413230000},"page":"55-82","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Synthetiq: Fast and Versatile Quantum Circuit Synthesis"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6029-1386","authenticated-orcid":false,"given":"Anouk","family":"Paradis","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0621-170X","authenticated-orcid":false,"given":"Jasper","family":"Dekoninck","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3283-7908","authenticated-orcid":false,"given":"Benjamin","family":"Bichsel","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0054-9568","authenticated-orcid":false,"given":"Martin","family":"Vechev","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-018-33125-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2244643"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-021-85474-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Frank Arute Kunal Arya Ryan Babbush Dave Bacon Joseph C. Bardin Rami Barends Rupak Biswas Sergio Boixo Fernando G. S. L. Brandao David A. Buell Brian Burkett Yu Chen Zijun Chen Ben Chiaro Roberto Collins William Courtney Andrew Dunsworth Edward Farhi Brooks Foxen Austin Fowler Craig Gidney Marissa Giustina Rob Graff Keith Guerin Steve Habegger Matthew P. Harrigan Michael J. Hartmann Alan Ho Markus Hoffmann Trent Huang Travis S. Humble Sergei V. Isakov Evan Jeffrey Zhang Jiang Dvir Kafri Kostyantyn Kechedzhi Julian Kelly Paul V. Klimov Sergey Knysh Alexander Korotkov Fedor Kostritsa David Landhuis Mike Lindmark Erik Lucero Dmitry Lyakh Salvatore Mandr\u00e0 Jarrod R. McClean Matthew McEwen Anthony Megrant Xiao Mi Kristel Michielsen Masoud Mohseni Josh Mutus Ofer Naaman Matthew Neeley Charles Neill Murphy Yuezhen Niu Eric Ostby Andre Petukhov John C. Platt Chris Quintana Eleanor G. Rieffel Pedram Roushan Nicholas C. Rubin Daniel Sank Kevin J. Satzinger Vadim Smelyanskiy Kevin J. Sung Matthew D. Trevithick Amit Vainsencher Benjamin Villalonga Theodore White Z. Jamie Yao Ping Yeh Adam Zalcman Hartmut Neven and John M. Martinis. 2019. Quantum supremacy using a programmable superconducting processor. Nature 574 7779 (2019) Oct. 505\u2013510. issn:1476-4687 https:\/\/doi.org\/10.1038\/s41586-019-1666-5 10.1038\/s41586-019-1666-5","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_2_1_6_1","volume-title":"Reversible Pebble Games for Reducing Qubits in Hierarchical Quantum Circuit Synthesis. In 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL). 102\u2013107","author":"Bhattacharjee Debjyoti","year":"2019","unstructured":"Debjyoti Bhattacharjee, Mathias Soeken, Srijit Dutta, Anupam Chattopadhyay, and Giovanni De Micheli. 2019. Reversible Pebble Games for Reducing Qubits in Hierarchical Quantum Circuit Synthesis. In 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL). 102\u2013107. https:\/\/doi.org\/10.1109\/ISMVL.2019.00026 ISSN: 2378-2226 10.1109\/ISMVL.2019.00026"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mejo.2018.08.011"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1063\/5.0082975"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.chemrev.8b00803"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO \u201922)","author":"Chou Yao-Hsin","year":"2022","unstructured":"Yao-Hsin Chou, Shu-Yu Kuo, Yu-Chi Jiang, Ching-Hsuan Wu, Jyun-Yi Shen, Cheng-Yen Hua, Pei-Shin Huang, Yun-Ting Lai, Yong Feng Tong, and Ming-He Chang. 2022. A novel quantum-inspired evolutionary computation-based quantum circuit synthesis for various universal gate libraries. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO \u201922). Association for Computing Machinery, New York, NY, USA. 2182\u20132189. isbn:9781450392686 https:\/\/doi.org\/10.1145\/3520304.3533956 10.1145\/3520304.3533956"},{"key":"e_1_2_1_11_1","volume-title":"Examples: Basic Arithmetic.. https:\/\/github.com\/quantumlib\/Cirq\/blob\/master\/examples\/basic_arithmetic.py","year":"2023","unstructured":"Cirq. 2023. Examples: Basic Arithmetic.. https:\/\/github.com\/quantumlib\/Cirq\/blob\/master\/examples\/basic_arithmetic.py"},{"key":"e_1_2_1_12_1","unstructured":"Gavin E. Crooks. 2023. Gates States and Circuits. https:\/\/threeplusone.com\/gates https:\/\/github.com\/gecrooks\/on_gates Tech. Note 014 v0.9.0 beta"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1707.03429"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Marc Grau Davis Ethan Smith Ana Tudor Koushik Sen Irfan Siddiqi and Costin Iancu. 2019. Heuristics for Quantum Compiling with a Continuous Gate Set. arxiv:1912.02727. https:\/\/doi.org\/10.48550\/arXiv.1912.02727","DOI":"10.48550\/arXiv.1912.02727"},{"key":"e_1_2_1_15_1","volume-title":"Towards Optimal Topology Aware Quantum Circuit Synthesis. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). 223\u2013234","author":"Davis Marc G.","year":"2020","unstructured":"Marc G. Davis, Ethan Smith, Ana Tudor, Koushik Sen, Irfan Siddiqi, and Costin Iancu. 2020. Towards Optimal Topology Aware Quantum Circuit Synthesis. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). 223\u2013234. https:\/\/doi.org\/10.1109\/QCE49297.2020.00036 10.1109\/QCE49297.2020.00036"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10676-017-9439-z"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-022-00624-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-022-00651-y"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.032332"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.3039"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"David Gosset Vadym Kliuchnikov Michele Mosca and Vincent Russo. 2013. An algorithm for the T-count. arxiv:1308.4134. https:\/\/doi.org\/10.48550\/arXiv.1308.4134","DOI":"10.48550\/arXiv.1308.4134"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462177"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC \u201996)","author":"Grover Lov K.","year":"1996","unstructured":"Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC \u201996). Association for Computing Machinery, New York, NY, USA. 212\u2013219. isbn:0897917855 https:\/\/doi.org\/10.1145\/237814.237866 10.1145\/237814.237866"},{"key":"e_1_2_1_24_1","unstructured":"Ga\u00ebl Guennebaud and Beno\u00eet Jacob. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908121"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.93.032318"},{"key":"e_1_2_1_28_1","volume-title":"Proc. ACM Program. Lang., 7, OOPSLA1","author":"Kang Chan Gu","year":"2023","unstructured":"Chan Gu Kang and Hakjoo Oh. 2023. Modular Component-Based Quantum Circuit Synthesis. Proc. ACM Program. Lang., 7, OOPSLA1 (2023), Article 87, apr, 28 pages. https:\/\/doi.org\/10.1145\/3586039 10.1145\/3586039"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-05-13-140"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2409842"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","unstructured":"Guang Hao Low Vadym Kliuchnikov and Luke Schaeffer. 2018. Trading T-gates for dirty qubits in state preparation and unitary synthesis. arxiv:1812.00954. https:\/\/doi.org\/10.48550\/arXiv.1812.00954","DOI":"10.48550\/arXiv.1812.00954"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.93.022311"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information.","DOI":"10.1119\/1.1463744"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-020-02816-0"},{"key":"e_1_2_1_38_1","unstructured":"OpenMP Architecture Review Board. 2021. OpenMP Application Program Interface Version 5.2. https:\/\/www.openmp.org\/wp-content\/uploads\/OpenMP-API-Specification-5-2.pdf"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Association for Computing Machinery","author":"Paradis Anouk","year":"2021","unstructured":"Anouk Paradis, Benjamin Bichsel, Samuel Steffen, and Martin Vechev. 2021. Unqomp: synthesizing uncomputation in Quantum circuits. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Association for Computing Machinery, New York, NY, USA. 222\u2013236. isbn:978-1-4503-8391-2 https:\/\/doi.org\/10.1145\/3453483.3454040 10.1145\/3453483.3454040"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.10777503"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1510.00377"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59936-6_7"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.83.032302"},{"key":"e_1_2_1_44_1","unstructured":"Qiskit. 2023. Implement the multi-controlled X gate using a V-chain of CX gates.. https:\/\/qiskit.org\/documentation\/stubs\/qiskit.circuit.library.MCXVChain.html"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.287.17"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1403.2975"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","unstructured":"Peter Selinger. 2014. Efficient Clifford+T approximation of single-qubit operators. arxiv:1212.6253. https:\/\/doi.org\/10.48550\/arXiv.1212.6253","DOI":"10.48550\/arXiv.1212.6253"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548693"},{"key":"e_1_2_1_50_1","unstructured":"Quantum Computing StackExchange. 2018. How to implement the \"Square root of Swap gate\" on the IBM Q (composer)? https:\/\/quantumcomputing.stackexchange.com\/questions\/2228\/how-to-implement-the-square-root-of-swap-gate-on-the-ibm-q-composer"},{"key":"e_1_2_1_51_1","unstructured":"Quantum Computing StackExchange. 2020. Decomposition of |110> <-> |000> Exchange Gate. https:\/\/quantumcomputing.stackexchange.com\/questions\/13644\/decomposition-of-110-rangle-leftrightarrow-000-rangle-exchange-gate"},{"key":"e_1_2_1_52_1","unstructured":"Quantum Computing StackExchange. 2021. How to create CX from an entangling gate and arbitrary single-qubit gates? https:\/\/quantumcomputing.stackexchange.com\/questions\/17656\/how-to-create-cnot-from-an-entangling-gate-and-arbitrary-single-qubit-gates"},{"key":"e_1_2_1_53_1","volume-title":"Qiskit: How to implement a classical function? https:\/\/quantumcomputing.stackexchange.com\/questions\/26505\/qiskit-how-to-implement-a-classical-function","author":"StackExchange Quantum Computing","year":"2022","unstructured":"Quantum Computing StackExchange. 2022. Qiskit: How to implement a classical function? https:\/\/quantumcomputing.stackexchange.com\/questions\/26505\/qiskit-how-to-implement-a-classical-function"},{"key":"e_1_2_1_54_1","unstructured":"Quantum Computing StackExchange. 2023. How to decompose root iswap into root cz and single-qubit gates. https:\/\/quantumcomputing.stackexchange.com\/questions\/29617\/how-to-decompose-root-iswap-into-root-cz-and-single-qubit-gates"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1147\/JRD.2011.2165678"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.87.307"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2103.07093"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649813","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649813","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:06Z","timestamp":1750287246000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649813"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":57,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2024,4,29]]}},"alternative-id":["10.1145\/3649813"],"URL":"https:\/\/doi.org\/10.1145\/3649813","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"2024-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}