{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T15:09:10Z","timestamp":1774451350746,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"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 Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2007,9]]},"abstract":"<jats:p>We present certain new techniques for the synthesis of reversible networks of Toffoli gates, as well as improvements to previous methods. Gate count and technology oriented cost metrics are used. Two new synthesis procedures employing Reed-Muller spectra are introduced and shown to complement earlier synthesis approaches. The previously proposed template simplification method is enhanced through the introduction of a faster and more efficient template application algorithm, an updated classification of the templates, and the addition of new templates of sizes 7 and 9. A resynthesis approach is introduced wherein a sequence of gates is chosen from a network, and the reversible specification it realizes is resynthesized as an independent problem in hopes of reducing the network cost. Empirical results are presented to show that the methods are efficient in terms of the realization of reversible benchmark specifications.<\/jats:p>","DOI":"10.1145\/1278349.1278355","type":"journal-article","created":{"date-parts":[[2007,10,14]],"date-time":"2007-10-14T12:41:11Z","timestamp":1192365671000},"page":"42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":131,"title":["Techniques for the synthesis of reversible Toffoli networks"],"prefix":"10.1145","volume":"12","author":[{"given":"D.","family":"Maslov","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}]},{"given":"G. W.","family":"Dueck","sequence":"additional","affiliation":[{"name":"University of New Brunswick, Fredericton, Canada"}]},{"given":"D. M.","family":"Miller","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}]}],"member":"320","published-online":{"date-parts":[[2007,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Conference and Exhibition on Design, Automation, and Test in Europe. 21384--21385","author":"Agrawal A.","unstructured":"Agrawal , A. and Jha , N. K . 2004. Synthesis of reversible logic . In Proceedings of the Conference and Exhibition on Design, Automation, and Test in Europe. 21384--21385 . Agrawal, A. and Jha, N. K. 2004. Synthesis of reversible logic. In Proceedings of the Conference and Exhibition on Design, Automation, and Test in Europe. 21384--21385."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Cory D. G. Laflamme R. Knill E. Viola L. Havel T. F. Boulant N. Boutis G. Fortunato E. Lloyd S. Martinez R. Negrevergne C. Pravia M. Sharf Y. Teklemariam G. Weinstein Y. S. and Zurek W. H. 2000. NMR-Based quantum information processing: achievements and prospects. Wiley Inter Science.  Cory D. G. Laflamme R. Knill E. Viola L. Havel T. F. Boulant N. Boutis G. Fortunato E. Lloyd S. Martinez R. Negrevergne C. Pravia M. Sharf Y. Teklemariam G. Weinstein Y. S. and Zurek W. H. 2000. NMR-Based quantum information processing: achievements and prospects. Wiley Inter Science.","DOI":"10.1002\/chin.200039300"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1364\/ON.11.2.000011"},{"key":"e_1_2_1_6_1","unstructured":"Gershenfeld N. and Chuang I. L. 1980. Quantum computing with molecules. Scientific American.  Gershenfeld N. and Chuang I. L. 1980. Quantum computing with molecules. Scientific American."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04279"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/513918.514026"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996789"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"e_1_2_1_11_1","unstructured":"Lee S. Lee S. Kim T. Lee J. Biamonte J. and Perkowski M. 2006. The cost of quantum gate primitives. J. Multiple-Valued Logic Soft Comp. 12(5--6).  Lee S. Lee S. Kim T. Lee J. Biamonte J. and Perkowski M. 2006. The cost of quantum gate primitives. J. Multiple-Valued Logic Soft Comp. 12(5--6)."},{"key":"e_1_2_1_12_1","unstructured":"Lomont C. 2003. Quantum circuit identities. Arxiv quant-ph\/0307111.  Lomont C. 2003. Quantum circuit identities. Arxiv quant-ph\/0307111."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.836735"},{"key":"e_1_2_1_14_1","unstructured":"Maslov D. Dueck G. and Scott N. 2005a. Reversible logic synthesis benchmarks page. http:\/\/www.cs.uvic.ca\/~dmaslov\/.  Maslov D. Dueck G. and Scott N. 2005a. Reversible logic synthesis benchmarks page. http:\/\/www.cs.uvic.ca\/~dmaslov\/."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.847911"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2005.249"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/4\/1\/002"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/4\/2\/007"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWSCAS.2002.1186906"},{"key":"e_1_2_1_20_1","first-page":"197","volume-title":"Proceedings of the International Workshop on Logic and Synthesis","author":"Mishchenko A.","unstructured":"Mishchenko , A. and Perkowski , M . 2002. Logic synthesis of reversible wave cascades . In Proceedings of the International Workshop on Logic and Synthesis , pp. 197 -- 202 . Mishchenko, A. and Perkowski, M. 2002. Logic synthesis of reversible wave cascades. In Proceedings of the International Workshop on Logic and Synthesis, pp. 197--202."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.96.170501"},{"key":"e_1_2_1_22_1","volume-title":"2000 Quantum Computation and Quantum Information","author":"Nielsen M.","unstructured":"Nielsen , M. and Chuang , I . 2000 Quantum Computation and Quantum Information . Cambridge University Press . Nielsen, M. and Chuang, I. 2000 Quantum Computation and Quantum Information. Cambridge University Press."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Workshop on Logic and Synthesis, 470--477","author":"Patel K. N.","unstructured":"Patel , K. N. , Markov , I. L. , and Hayes , J. P . 2004 Efficient Synthesis of Linear Reversible Circuits . In Proceedings of the International Workshop on Logic and Synthesis, 470--477 . Patel, K. N., Markov, I. L., and Hayes, J. P. 2004 Efficient Synthesis of Linear Reversible Circuits. In Proceedings of the International Workshop on Logic and Synthesis, 470--477."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.32.3266"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.811448"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216396.1216399"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Thornton M. A. Drechsler R. and Miller D. M. 2001. Spectral Techniques in VLSI CAD. Kluwer Academic Publishers.   Thornton M. A. Drechsler R. and Miller D. M. 2001. Spectral Techniques in VLSI CAD. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-1425-1"},{"key":"e_1_2_1_29_1","unstructured":"Toffoli T. 2001. Reversible computing. Tech memo MIT\/LCS\/TM-151 MIT Lab for Computer Science.  Toffoli T. 2001. Reversible computing. Tech memo MIT\/LCS\/TM-151 MIT Lab for Computer Science."},{"key":"e_1_2_1_30_1","volume-title":"IEEE Conference on Nanotechnology, 111--116","author":"Tsai I. M.","unstructured":"Tsai , I. M. and Kuo , S. Y ., 2001. Quantum boolean circuit construction and layout under locality constraint . In IEEE Conference on Nanotechnology, 111--116 . Tsai, I. M. and Kuo, S. Y., 2001. Quantum boolean circuit construction and layout under locality constraint. In IEEE Conference on Nanotechnology, 111--116."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1038\/414883a"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2003.818324"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1278349.1278355","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1278349.1278355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:29Z","timestamp":1750258049000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1278349.1278355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,9]]}},"alternative-id":["10.1145\/1278349.1278355"],"URL":"https:\/\/doi.org\/10.1145\/1278349.1278355","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9]]},"assertion":[{"value":"2007-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}