{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T18:15:10Z","timestamp":1780078510475,"version":"3.54.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            The multiplicative depth of a logic network over the gate basis {\u2227 , \u2295 , \u00ac} is the largest number of \u2227 gates on any path from a primary input to a primary output in the network. We describe a dynamic programming based logic synthesis algorithm to reduce the multiplicative depth of logic networks. It makes use of cut enumeration, tree balancing, and\n            <jats:bold>exclusive sum-of-products (ESOP)<\/jats:bold>\n            representations. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower\n            <jats:italic>T<\/jats:italic>\n            -depth of the corresponding quantum circuit. Our experimental results show improvements in\n            <jats:italic>T<\/jats:italic>\n            -depth over state-of-the-art methods and over several hand-optimized quantum circuits, for instance, of AES, SHA, and floating-point arithmetic.\n          <\/jats:p>","DOI":"10.1145\/3501334","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T09:54:52Z","timestamp":1646387692000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Lowering the T-depth of Quantum Circuits via Logic Network Optimization"],"prefix":"10.1145","volume":"3","author":[{"given":"Thomas","family":"H\u00e4ner","sequence":"first","affiliation":[{"name":"Microsoft Quantum, Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathias","family":"Soeken","sequence":"additional","affiliation":[{"name":"Microsoft Quantum, Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Int\u2019l Workshop on Logic and Synthesis","author":"Amar\u00f9 Luca Gaetano","year":"2015","unstructured":"Luca Gaetano Amar\u00f9, Pierre-Emmanuel Gaillardon, and Giovanni De Micheli. 2015. The EPFL combinational benchmark suite. In Int\u2019l Workshop on Logic and Synthesis."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2341953"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2244643"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-69453-5_18"},{"key":"e_1_3_2_6_2","unstructured":"David Archer Victor Arribas Abril Pieter Maene Nele Mertens Danilo Sijacic and Nigel Smart. \u2018Bristol Fashion\u2019 MPC circuits. Retrieved on Dec. 2021 from https:\/\/homes.esat.kuleuven.be\/nsmart\/MPC\/."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-40186-3_15"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.1990.112064"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-012-9124-7"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.223676"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.52213"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14295-6_5"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.7.021029"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78825-8_23"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278705"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2010.5654210"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31511-5_10"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/296399.296425"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.795226"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06686-8_13"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-06-18-74"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29360-8_3"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-99498-7_11"},{"key":"e_1_3_2_25_2","first-page":"427","volume-title":"Design Automation Conference","author":"Helliwell Martin","year":"1988","unstructured":"Martin Helliwell and Marek A. Perkowski. 1988. A fast algorithm to minimize multi-output mixed-polarity generalized reed-muller forms. In Design Automation Conference. 427\u2013432. http:\/\/portal.acm.org\/citation.cfm?id=285730.285799."},{"issue":"5","key":"e_1_3_2_26_2","first-page":"1214","article-title":"New three-level Boolean expression based on EXOR gates","volume":"87","author":"Ishikawa Ryoji","year":"2004","unstructured":"Ryoji Ishikawa, Takashi Hirayama, Goro Koda, and Kensuke Shimizu. 2004. New three-level Boolean expression based on EXOR gates. IEICE Trans. on Information & Systems 87-D, 5 (2004), 1214\u20131222. http:\/\/search.ieice.org\/bin\/summary.php?id=e87-d_5_1214.","journal-title":"IEICE Trans. on Information & Systems"},{"key":"e_1_3_2_27_2","article-title":"Implementing Grover oracles for quantum key search on AES and LowMC","author":"Jaques Samuel","year":"2019","unstructured":"Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia. 2019. Implementing Grover oracles for quantum key search on AES and LowMC. arXiv preprint arXiv:1910.01700 (2019).","journal-title":"arXiv preprint arXiv:1910.01700"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.022328"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-018-2107-3"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2020.2965697"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1023\/A%3A1023634616182"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-05-04-62"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.754996"},{"issue":"5","key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"361","DOI":"10.26421\/QIC12.5-6-1","article-title":"Constant-optimized quantum circuits for modular multiplication and exponentiation","volume":"12","author":"Markov Igor L.","year":"2012","unstructured":"Igor L. Markov and Mehdi Saeedi. 2012. Constant-optimized quantum circuits for modular multiplication and exponentiation. Quantum Information and Computation 12, 5&6 (2012), 361\u2013394.","journal-title":"Quantum Information and Computation"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.012310"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.1991.185226"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD45719.2019.8942093"},{"key":"e_1_3_2_38_2","volume-title":"Int\u2019l Symp. on Circuits and Systems","author":"Meuli Giulia","year":"2020","unstructured":"Giulia Meuli, Mathias Soeken, Martin Roetteler, and Giovanni De Micheli. 2020. Enumerating optimal quantum circuits using spectral classification. In Int\u2019l Symp. on Circuits and Systems."},{"key":"e_1_3_2_39_2","first-page":"15","volume-title":"Int\u2019l Workshop on Logic and Synthesis","author":"Mishchenko Alan","year":"2006","unstructured":"Alan Mishchenko and Robert K. Brayton. 2006. Scalable logic synthesis using a simple circuit structure. In Int\u2019l Workshop on Logic and Synthesis. 15\u201322."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1723112.1723144"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2011.6105357"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1147048"},{"key":"e_1_3_2_43_2","volume-title":"Reed-Muller Workshop","author":"Mishchenko Alan","year":"2001","unstructured":"Alan Mishchenko and Marek A. Perkowski. 2001. Fast heuristic minimization of exclusive-sum-of-products. In Reed-Muller Workshop."},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-1-4615-3154-8_3","volume-title":"Logic Synthesis and Optimization","author":"Muroga Saburo","year":"1993","unstructured":"Saburo Muroga. 1993. Logic synthesizers, the transduction method and its extension, SYLON. In Logic Synthesis and Optimization, Tsutomu Sasao (Ed.). Springer, 59\u201386."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2019.00027"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.95.032338"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126614500157"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1619152114"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/HST.2019.8740831"},{"key":"e_1_3_2_51_2","volume-title":"Advanced Boolean Techniques","author":"Riener Heinz","year":"2020","unstructured":"Heinz Riener, R\u00fcdiger Ehlers, Bruno Schmitt, and Giovanni De Micheli. 2020. Exact synthesis of ESOP forms. In Advanced Boolean Techniques, Rolf Drechsler and Mathias Soeken (Eds.). Springer. arXiv preprint arXiv:1807.11103 (2020)."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/196244.196448"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.5555\/523426"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.45212"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51083-4_47"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.3103\/S0278641914020083"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.042302"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.811448"},{"key":"e_1_3_2_59_2","article-title":"The EPFL logic synthesis libraries","author":"Soeken Mathias","year":"2018","unstructured":"Mathias Soeken, Heinz Riener, Winston Haaswijk, Eleonora Testa, Bruno Schmitt, Giulia Meuli, Fereshte Mozafari, and Giovanni De Micheli. 2018. The EPFL logic synthesis libraries. arXiv preprint arXiv:1805.05121v2 (2018).","journal-title":"arXiv preprint arXiv:1805.05121v2"},{"key":"e_1_3_2_60_2","article-title":"Quantum circuits for functionally controlled NOT gates","author":"Soeken Mathias","year":"2020","unstructured":"Mathias Soeken and Martin Roetteler. 2020. Quantum circuits for functionally controlled NOT gates. arXiv preprint arXiv:2005.12310 (2020).","journal-title":"arXiv preprint arXiv:2005.12310"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2859251"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/988952.988971"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2869760"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317893"},{"key":"e_1_3_2_65_2","volume-title":"Design, Automation and Test in Europe","author":"Testa Eleonora","year":"2020","unstructured":"Eleonora Testa, Mathias Soeken, Heinz Riener, Luca Gaetano Amar\u00f9, and Giovanni De Micheli. 2020. A logic synthesis toolbox for reducing the multiplicative complexity in logic networks. In Design, Automation and Test in Europe."},{"key":"e_1_3_2_66_2","volume-title":"Int\u2019l Workshop on Logic and Synthesis","author":"Verma Ajay K.","year":"2008","unstructured":"Ajay K. Verma, Philip Brisk, and Paolo Ienne. 2008. XP \\( ^2 \\) : A new compact representation for manipulating arithmetic circuits. In Int\u2019l Workshop on Logic and Synthesis."},{"key":"e_1_3_2_67_2","article-title":"Quantum computing enhanced computational catalysis","author":"Burg Vera von","year":"2020","unstructured":"Vera von Burg, Guang Hao Low, Thomas H\u00e4ner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer. 2020. Quantum computing enhanced computational catalysis. arXiv preprint arXiv:2007.14460 (2020).","journal-title":"arXiv preprint arXiv:2007.14460"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429513"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3501334","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3501334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:19Z","timestamp":1750188619000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3501334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3501334"],"URL":"https:\/\/doi.org\/10.1145\/3501334","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,4]]},"assertion":[{"value":"2021-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}