{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T10:14:09Z","timestamp":1775384049713,"version":"3.50.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,12,30]],"date-time":"2014-12-30T00:00:00Z","timestamp":1419897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSER Discovery grant"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2014,12,30]]},"abstract":"<jats:p>Quantum circuits are often generated by decomposing gates from networks with classical reversible gates. Only in rare cases, the results are minimal. Post-optimization methods, such as template matching, are employed to reduce the quantum costs of circuits. Quantum templates are derived from identity circuits. All minimal realizations, within certain limitations, can be embedded into templates. Due to this property, templates matching has the potential to reduce quantum costs of circuits. However, one of the difficulties in finding templates matches is due to the mobility of the gates within the circuit. Thus far, template matching procedures have employed heuristics to reduce the search space. This article presents an in-depth study of exact template matching with a set of algorithms. A graph structure with the corresponding circuits facilitates the discovery of potential sequences of templates to be matched, and how exact minimization of circuits can be accomplished. The significance of the proposed method is verified in benchmarks optimization.<\/jats:p>","DOI":"10.1145\/2629537","type":"journal-article","created":{"date-parts":[[2015,1,5]],"date-time":"2015-01-05T13:27:09Z","timestamp":1420464429000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["An Algorithm for Quantum Template Matching"],"prefix":"10.1145","volume":"11","author":[{"given":"Md. Mazder","family":"Rahman","sequence":"first","affiliation":[{"name":"University of New Brunswick, Fredericton, NB, Canada"}]},{"given":"Gerhard W.","family":"Dueck","sequence":"additional","affiliation":[{"name":"University of New Brunswick, Fredericton, NB, Canada"}]},{"given":"Joseph D.","family":"Horton","sequence":"additional","affiliation":[{"name":"University of New Brunswick, Fredericton, NB, Canada"}]}],"member":"320","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.321.0016"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01857727"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.858352"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.847911"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2005.249"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2011.54"},{"key":"e_1_2_1_9_1","volume-title":"Chuang","author":"Nielsen Michael A.","year":"2000","unstructured":"Michael A. Nielsen and Isaac L . Chuang . 2000 . Quantum Computation and Quantum Information. Cambridge University Press . Michael A. Nielsen and Isaac L. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.32.3266"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IEEE Congress on Evolutionary Computation. 623--629","unstructured":"Md. Mazder Rahman and Gerhard W. Dueck. 2012a. An algorithm to find quantum templates . In Proceedings of the IEEE Congress on Evolutionary Computation. 623--629 . Md. Mazder Rahman and Gerhard W. Dueck. 2012a. An algorithm to find quantum templates. In Proceedings of the IEEE Congress on Evolutionary Computation. 623--629."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2012.43"},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"Mazder Rahman and Gerhard W. Dueck","year":"2013","unstructured":"Md. Mazder Rahman and Gerhard W. Dueck . 2013 a. Properties of quantum templates. In Reversible Computation, Robert Glek and Tetsuo Yokoyama (Eds.), Lecture Notes in Computer Science , vol. 7581 , Springer , Berlin Heidelberg, 125--137. DOI: http:\/\/dx.doi.org\/10.1007\/978-3-642-36315-3_10 10.1007\/978-3-642-36315-3_10 Md. Mazder Rahman and Gerhard W. Dueck. 2013a. Properties of quantum templates. In Reversible Computation, Robert Glek and Tetsuo Yokoyama (Eds.), Lecture Notes in Computer Science, vol. 7581, Springer, Berlin Heidelberg, 125--137. DOI: http:\/\/dx.doi.org\/10.1007\/978-3-642-36315-3_10"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Reed-Muller Workshop. 75--79","unstructured":"Md. Mazder Rahman and Gerhard W. Dueck. 2013b. Template matching in quantum circuits optimization . In Proceedings of the Reed-Muller Workshop. 75--79 . Md. Mazder Rahman and Gerhard W. Dueck. 2013b. Template matching in quantum circuits optimization. In Proceedings of the Reed-Muller Workshop. 75--79."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29517-1_4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29517-1_7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228368"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/646234.682540"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2008.43"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629537","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629537","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:18Z","timestamp":1750230078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629537"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,12,30]]}},"alternative-id":["10.1145\/2629537"],"URL":"https:\/\/doi.org\/10.1145\/2629537","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"value":"1550-4832","type":"print"},{"value":"1550-4840","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,30]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}