{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T10:16:26Z","timestamp":1775384186538,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200020-165843"],"award-info":[{"award-number":["200020-165843"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Centre of Competence in Research Quantum Science and Technology"},{"name":"Quantum Center of ETH Zurich"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>\n            Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a\n            <jats:italic>pattern<\/jats:italic>\n            , in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n            that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by \u223c 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.\n          <\/jats:p>","DOI":"10.1145\/3498325","type":"journal-article","created":{"date-parts":[[2022,1,23]],"date-time":"2022-01-23T06:44:52Z","timestamp":1642920292000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Exact and Practical Pattern Matching for Quantum Circuit Optimization"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5332-5093","authenticated-orcid":false,"given":"Raban","family":"Iten","sequence":"first","affiliation":[{"name":"Institute for Theoretical Physics, ETH Zurich, Zurich, Switzerland"}]},{"given":"Romain","family":"Moyard","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, ETH Zurich, Zurich, Switzerland"}]},{"given":"Tony","family":"Metger","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, ETH Zurich, Zurich, Switzerland"}]},{"given":"David","family":"Sutter","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM Research Europe \u2013 Zurich, Switzerland and Institute for Theoretical Physics, ETH Zurich, Switzerland"}]},{"given":"Stefan","family":"Woerner","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM Research Europe \u2013 Zurich, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2022,1,22]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2013.26"},{"key":"e_1_3_3_3_2","unstructured":"H\u00e9ctor Abraham et\u00a0al. 2019. Qiskit: An Open-source Framework for Quantum Computing. https:\/\/doi.org\/10.5281\/zenodo.2562110"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/285730.285814"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_3_6_2","article-title":"Graph-theoretic simplification of quantum circuits with the ZX-calculus","volume":"1902","author":"Duncan Ross","year":"2019","unstructured":"Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. 2019. Graph-theoretic simplification of quantum circuits with the ZX-calculus. ArXiv 1902.03178 (2019).","journal-title":"ArXiv"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"issue":"3","key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"032318","DOI":"10.1103\/PhysRevA.93.032318","article-title":"Quantum circuits for isometries","volume":"93","author":"Iten Raban","year":"2016","unstructured":"Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl. 2016. Quantum circuits for isometries. Physical Review A 93, 3 (March 2016), 032318. https:\/\/doi.org\/10.1103\/PhysRevA.93.032318","journal-title":"Physical Review A"},{"key":"e_1_3_3_10_2","article-title":"Introduction to UniversalQCompiler","author":"Iten Raban","year":"2019","unstructured":"Raban Iten, Oliver Reardon-Smith, Luca Mondada, Ethan Redmond, Ravjot Singh Kohli, and Roger Colbeck. 2019. Introduction to UniversalQCompiler. ArXiv:1904.01072 (April 2019). http:\/\/arxiv.org\/abs\/1904.01072.","journal-title":"ArXiv:1904.01072"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/513918.514026"},{"key":"e_1_3_3_12_2","article-title":"Identity check is QMA-complete","author":"Janzing Dominik","year":"2003","unstructured":"Dominik Janzing, Pawel Wocjan, and Thomas Beth. 2003. Identity check is QMA-complete. ArXiv:0305050 (2003).","journal-title":"ArXiv:0305050"},{"issue":"5","key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"052307","DOI":"10.1103\/PhysRevA.88.052307","article-title":"Optimization of Clifford circuits","volume":"88","author":"Kliuchnikov Vadym","year":"2013","unstructured":"Vadym Kliuchnikov and Dmitri Maslov. 2013. Optimization of Clifford circuits. Physical Review A 88, 5 (Nov. 2013), 052307. https:\/\/doi.org\/10.1103\/PhysRevA.88.052307","journal-title":"Physical Review A"},{"key":"e_1_3_3_14_2","unstructured":"Robin Kothari. [n.d.]. Private communication."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/800033.800862"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/942808.943941"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2005.844284"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1278349.1278355"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.911334"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775915"},{"key":"e_1_3_3_21_2","unstructured":"Luca Mondada. 2018. UniversalQCompiler: a quantum compiler from arbitrary isometries to elementary gates. Semester Thesis at ETH Zurich."},{"issue":"1","key":"e_1_3_3_22_2","article-title":"Automated optimization of large quantum circuits with continuous parameters","volume":"4","author":"Nam Yunseong","year":"2018","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 (May 2018). https:\/\/doi.org\/10.1038\/s41534-018-0072-4","journal-title":"npj Quantum Information"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/544199"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/157485.164556"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1216396.1216399"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1216396.1216399"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629537"},{"issue":"1","key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"012310","DOI":"10.1103\/PhysRevA.70.012310","article-title":"Recognizing small-circuit structure in two-qubit operators","volume":"70","author":"Shende Vivek V.","year":"2004","unstructured":"Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov. 2004. Recognizing small-circuit structure in two-qubit operators. Physical Review A 70, 1 (July 2004), 012310. https:\/\/doi.org\/10.1103\/PhysRevA.70.012310","journal-title":"Physical Review A"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1983.1270023"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498325","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:04Z","timestamp":1750188604000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,22]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3498325"],"URL":"https:\/\/doi.org\/10.1145\/3498325","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,22]]},"assertion":[{"value":"2020-12-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-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}