{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T22:16:15Z","timestamp":1772057775762,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2006,10]]},"abstract":"<jats:p>Reversible logic is motivated by low-power design, quantum circuits, and nanotechnology. We develop a compact representation of small reversible circuits to generate and store optimal circuits for all 40,320 three-input reversible functions, and millions of four-input circuits. This allows implementing a function optimally in constant time for use in the peephole optimization of larger circuits produced by existing techniques, and guarantees that every three-bit subcircuit is optimal. To generate subcircuits, we use a graph-based data structure and algorithms for circuit restructuring. Finally, we demonstrate a suboptimal circuit for which peephole optimization fails.<\/jats:p>","DOI":"10.1145\/1216396.1216399","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"277-293","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Data structures and algorithms for simplifying reversible circuits"],"prefix":"10.1145","volume":"2","author":[{"given":"Aditya K.","family":"Prasad","sequence":"first","affiliation":[{"name":"Amazon.com Inc., Seattle, WA"}]},{"given":"Vivek V.","family":"Shende","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"Igor L.","family":"Markov","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"John P.","family":"Hayes","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"Ketan N.","family":"Patel","sequence":"additional","affiliation":[{"name":"Qualcomm Inc., Campbell, CA"}]}],"member":"320","published-online":{"date-parts":[[2006,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Design, Automation and Test in Europe Conference and Exhibition. 1384--1385","author":"Agrawal A.","unstructured":"Agrawal , A. and Jha , N. K . 2004. Synthesis of reversible logic . In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition. 1384--1385 . Agrawal, A. and Jha, N. K. 2004. Synthesis of reversible logic. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition. 1384--1385."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","article-title":"Elementary gates for quantum computation","volume":"52","author":"Barenco A.","year":"1995","unstructured":"Barenco , A. , Bennett , C. H. , Cleve , R. , Di Vincenzo , D. P. , Margolus , N. , Shor , P. , Sleator , T. , Smolin , J. , and Weinfurter , H. 1995 . Elementary gates for quantum computation . Phys. Rev. A 52 , 3457 -- 3467 . Barenco, A., Bennett, C. H., Cleve, R., Di Vincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. 1995. Elementary gates for quantum computation. Phys. Rev. A 52, 3457--3467.","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1147\/rd.176.0525","article-title":"Logical reversibility of computation","volume":"17","author":"Bennett C.","year":"1973","unstructured":"Bennett , C. 1973 . Logical reversibility of computation . IBM J. Res. Develop. 17 , 525 -- 532 . Bennett, C. 1973. Logical reversibility of computation. IBM J. Res. Develop. 17, 525--532.","journal-title":"IBM J. Res. Develop."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Symposium on Physical Design. 88--94","author":"Cong J.","unstructured":"Cong , J. , Romesis , M. , and Xie , M . 2003. Optimality, scalability and stability study of partitioning and placement algorithms . In Proceedings of the International Symposium on Physical Design. 88--94 . 10.1145\/640000.640021 Cong, J., Romesis, M., and Xie, M. 2003. Optimality, scalability and stability study of partitioning and placement algorithms. In Proceedings of the International Symposium on Physical Design. 88--94. 10.1145\/640000.640021"},{"key":"e_1_2_1_5_1","unstructured":"Cormen T. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd ed. MIT Press Cambridge MA.   Cormen T. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd ed. MIT Press Cambridge MA."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Symposium of FPGAs. 66--72","author":"Darnauer J. A.","unstructured":"Darnauer , J. A. and Dai , W. W . 1996. A method for generating random circuits and its application to routability measurement . In Proceedings of the International Symposium of FPGAs. 66--72 . 10.1145\/228370.228380 Darnauer, J. A. and Dai, W. W. 1996. A method for generating random circuits and its application to routability measurement. In Proceedings of the International Symposium of FPGAs. 66--72. 10.1145\/228370.228380"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.285.0537"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9260(02)00051-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"7063","DOI":"10.1088\/0305-4470\/35\/33\/307","article-title":"Generating the group of reversible logic gates","volume":"35","author":"de Vos A.","year":"2002","unstructured":"de Vos , A. , Raa , B. , and Storme , L. 2002 . Generating the group of reversible logic gates . J. Phys. A 35 , 7063 -- 7078 . de Vos, A., Raa, B., and Storme, L. 2002. Generating the group of reversible logic gates. J. Phys. A 35, 7063--7078.","journal-title":"J. Phys. A"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1364\/ON.11.2.000011","article-title":"Quantum mechanical computers","volume":"11","author":"Feynman R.","year":"1985","unstructured":"Feynman , R. 1985 . Quantum mechanical computers . Optics News , 11 , 11 -- 20 . Feynman, R. 1985. Quantum mechanical computers. Optics News, 11, 11--20.","journal-title":"Optics News"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 30th Annual ACM Symposium on the Theory of Computing. 10","author":"Grover L. K.","year":"1998","unstructured":"Grover , L. K. 1998 . A framework for fast quantum mechanical algorithms . In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing. 10 .1145\/276698.276712 Grover, L. K. 1998. A framework for fast quantum mechanical algorithms. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing. 10.1145\/276698.276712"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 39th Conference on Design Automation. 419--425","author":"Iwama K.","unstructured":"Iwama , K. , Kambayashi , Y. , and Yamashita , S . 2002. Transformation rules for designing CNOT-based quantum circuits . In Proceedings of the 39th Conference on Design Automation. 419--425 . 10.1145\/513918.514026 Iwama, K., Kambayashi, Y., and Yamashita, S. 2002. Transformation rules for designing CNOT-based quantum circuits. In Proceedings of the 39th Conference on Design Automation. 419--425. 10.1145\/513918.514026"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Conference on Design Automation. 834--837","author":"Kerntopf P.","year":"2004","unstructured":"Kerntopf , P. 2004 . A new heuristic algorithm for reversible logic synthesis . In Proceedings of the Conference on Design Automation. 834--837 . 10.1145\/996566.996789 Kerntopf, P. 2004. A new heuristic algorithm for reversible logic synthesis. In Proceedings of the Conference on Design Automation. 834--837. 10.1145\/996566.996789"},{"key":"e_1_2_1_14_1","unstructured":"MacWilliams F. J. and Sloane N. J. A. 1977. The Theory of Error-Correcting Codes. North-Holland Amsterdam.  MacWilliams F. J. and Sloane N. J. A. 1977. The Theory of Error-Correcting Codes. North-Holland Amsterdam."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Symposium on Integrated Circuits and System Design","author":"Maslov D.","unstructured":"Maslov , D. , Dueck , D. , and Miller , D. M . 2003a. Simplification of Toffoli networks via templates . In Proceedings of the Symposium on Integrated Circuits and System Design ( Sao Paulo, Brazil). 53--58. Maslov, D., Dueck, D., and Miller, D. M. 2003a. Simplification of Toffoli networks via templates. In Proceedings of the Symposium on Integrated Circuits and System Design (Sao Paulo, Brazil). 53--58."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Computer Aided Design. 256--261","author":"Maslov D.","year":"2003","unstructured":"Maslov , D. , Dueck , D. , and Miller , D. M . 2003b. Fredkin\/Toffoli templates for reversible logic synthesis . In Proceedings of the International Conference on Computer Aided Design. 256--261 . 10.1109\/ICCAD. 2003 .73 Maslov, D., Dueck, D., and Miller, D. M. 2003b. Fredkin\/Toffoli templates for reversible logic synthesis. In Proceedings of the International Conference on Computer Aided Design. 256--261. 10.1109\/ICCAD.2003.73"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the IEEE International Conference on Computer Design 453--461","author":"McGregor J. P.","unstructured":"McGregor , J. P. and Lee , R. B . 2001. Architectural enhancements for fast subword permutations with repetitions in cryptographic applications . In Proceedings of the IEEE International Conference on Computer Design 453--461 . McGregor, J. P. and Lee, R. B. 2001. Architectural enhancements for fast subword permutations with repetitions in cryptographic applications. In Proceedings of the IEEE International Conference on Computer Design 453--461."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/364995.365000"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 40th Conference on Design Automation. 318--323","author":"Miller D. M.","unstructured":"Miller , D. M. , Maslov , D. , and Dueck , G. W . 2003. A transformation based algorithm for reversible logic synthesis . In Proceedings of the 40th Conference on Design Automation. 318--323 . 10.1145\/775832.775915 Miller, D. M., Maslov, D., and Dueck, G. W. 2003. A transformation based algorithm for reversible logic synthesis. In Proceedings of the 40th Conference on Design Automation. 318--323. 10.1145\/775832.775915"},{"key":"e_1_2_1_20_1","unstructured":"Nielsen M. and Chuang I. 2000. Quantum Computation and Quantum Information Cambridge University Press New York.   Nielsen M. and Chuang I. 2000. Quantum Computation and Quantum Information Cambridge University Press New York."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.811448"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Symposium on Physical Sesign. 60--66","author":"Stroobandt D.","year":"1999","unstructured":"Stroobandt , D. , Verplaetse , P. , and van Campenhout , J. 1999 . Towards synthetic benchmark circuits for evaluating timing-driven CAD tools . In Proceedings of the International Symposium on Physical Sesign. 60--66 . 10.1145\/299996.300023 Stroobandt, D., Verplaetse, P., and van Campenhout, J. 1999. Towards synthetic benchmark circuits for evaluating timing-driven CAD tools. In Proceedings of the International Symposium on Physical Sesign. 60--66. 10.1145\/299996.300023"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Toffoli T. 1980. Reversible computing. Tech. Memo MIT\/LCS\/TM-151 MIT Laboratory for Computer Science.  Toffoli T. 1980. Reversible computing. Tech. Memo MIT\/LCS\/TM-151 MIT Laboratory for Computer Science.","DOI":"10.21236\/ADA082021"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Workshop on Low Power Design.","author":"Younis S.","unstructured":"Younis , S. and Knight , T . 1994. Asymptotically zero energy split-level charge recovery logic . In Proceedings of the Workshop on Low Power Design. Younis, S. and Knight, T. 1994. Asymptotically zero energy split-level charge recovery logic. In Proceedings of the Workshop on Low Power Design."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"1934","DOI":"10.1109\/JPROC.2003.818324","article-title":"Limits to binary logic switch scaling---A Gedanken model","volume":"91","author":"Zhirnov V. V.","year":"2003","unstructured":"Zhirnov , V. V. , Cavin , R. K. , Hutchby , J. A. , and Bourianoff , G. I. 2003 . Limits to binary logic switch scaling---A Gedanken model . In Proc. IEEE 91 , 1934 -- 1939 . Zhirnov, V. V., Cavin, R. K., Hutchby, J. A., and Bourianoff, G. I. 2003. Limits to binary logic switch scaling---A Gedanken model. In Proc. IEEE 91, 1934--1939.","journal-title":"Proc. IEEE"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1216396.1216399","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:57:15Z","timestamp":1672261035000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1216396.1216399"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1145\/1216396.1216399"],"URL":"https:\/\/doi.org\/10.1145\/1216396.1216399","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"value":"1550-4832","type":"print"},{"value":"1550-4840","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]},"assertion":[{"value":"2006-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}