{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:48:25Z","timestamp":1759146505766,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,2,1]],"date-time":"2014-02-01T00:00:00Z","timestamp":1391212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Taiwan Ministry of Education Fellowship"},{"DOI":"10.13039\/100011039","name":"IARPA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100011039","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2014,2]]},"abstract":"<jats:p>In this article, we propose a flexible and efficient reversible logic synthesizer. It exploits the complementary advantages of two methods: Reed-Muller Reversible Logic Synthesis (RMRLS) and Decision Diagram Synthesis (DDS), and is thus called Reed-Muller Decision Diagram Synthesis (RMDDS). RMRLS does not scale to a large number of qubits (i.e., quantum bits). DDS tools, even though efficient, add a large number of ancillary qubits and typically incur much higher quantum cost than necessary. RMDDS overcomes these obstacles. It is flexible in the sense that users can either optimize the number of qubits or the quantum cost in the circuit implementation. It is also efficient because the circuits can be synthesized within user-defined CPU times. This combination of flexibility and efficiency has been missing from synthesizers presented earlier. When used to synthesize reversible functions, RMDDS reduces the number of qubits by up to 79.2% (average of 54.6%) when the synthesis objective is to minimize the number of qubits and the quantum cost by up to 71.5% (average of 35.7%) when the synthesis objective is to minimize quantum cost, relative to DDS methods. For irreversible functions (which are automatically embedded in reversible functions), the corresponding best (average) reductions in the number of qubits is 42.1% (22.5%) when minimizing the number of qubits, and in quantum cost, it is 63.0% (25.9%) when minimizing quantum cost.<\/jats:p>","DOI":"10.1145\/2564923","type":"journal-article","created":{"date-parts":[[2014,3,4]],"date-time":"2014-03-04T13:24:59Z","timestamp":1393939499000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["RMDDS"],"prefix":"10.1145","volume":"10","author":[{"given":"Chia-Chun","family":"Lin","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ"}]},{"given":"Niraj K.","family":"Jha","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ"}]}],"member":"320","published-online":{"date-parts":[[2014,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.335009"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"volume-title":"Proceedings of the International Colloquium on Automata Languages and Programming, 475--486","author":"Becker B.","key":"e_1_2_1_3_1","unstructured":"B. Becker , R. Drechsler , and M. Theobald . 1995. OKFDDs versus OBDDs and OFDDs . In Proceedings of the International Colloquium on Automata Languages and Programming, 475--486 . B. Becker, R. Drechsler, and M. Theobald. 1995. OKFDDs versus OBDDs and OFDDs. In Proceedings of the International Colloquium on Automata Languages and Programming, 475--486."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature10872"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ADCOM.2007.111"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062261.1062325"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1330521.1330523"},{"volume-title":"Proceedings of the International Conference on Computer Design, 602--607","author":"Drechsler R.","key":"e_1_2_1_9_1","unstructured":"R. Drechsler and B. Becker . 1995. Dynamic minimization of OKFDDs . In Proceedings of the International Conference on Computer Design, 602--607 . R. Drechsler and B. Becker. 1995. Dynamic minimization of OKFDDs. In Proceedings of the International Conference on Computer Design, 602--607."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.544485"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2011.40"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01857727"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2017215"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.871622"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICQNM.2009.25"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"e_1_2_1_17_1","unstructured":"D. Maslov. 2011. Reversible logic synthesis benchmarks page. http:\/\/webhome.cs.uvic.ca\/&sim;dmaslov\/.  D. Maslov. 2011. Reversible logic synthesis benchmarks page. http:\/\/webhome.cs.uvic.ca\/&sim;dmaslov\/."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.836735"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.847911"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.911334"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278349.1278355"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2005.249"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775915"},{"volume-title":"Proceedings of the International Workshop on Appl. Reed-Muller Expansion Circuit Design, 242--250","author":"Mishchenko A.","key":"e_1_2_1_24_1","unstructured":"A. Mishchenko , and M. Perkowski . 2001. Fast heuristic minimization of exclusive-sums-of-products . In Proceedings of the International Workshop on Appl. Reed-Muller Expansion Circuit Design, 242--250 . A. Mishchenko, and M. Perkowski. 2001. Fast heuristic minimization of exclusive-sums-of-products. In Proceedings of the International Workshop on Appl. Reed-Muller Expansion Circuit Design, 242--250."},{"volume-title":"Proceedings of the IEEE Conference on Nanotechnology, 417--420","author":"Morrison M.","key":"e_1_2_1_25_1","unstructured":"M. Morrison , M. Lewandowski , R. Meana , and N. Ranganathan . 2011. Design of static and dynamic RAM arrays using a novel reversible logic gate and decoder . In Proceedings of the IEEE Conference on Nanotechnology, 417--420 . M. Morrison, M. Lewandowski, R. Meana, and N. Ranganathan. 2011. Design of static and dynamic RAM arrays using a novel reversible logic gate and decoder. In Proceedings of the IEEE Conference on Nanotechnology, 417--420."},{"volume-title":"Proceedings of the IEEE Conference on Nanotechnology, 1445--1449","author":"Morrison M.","key":"e_1_2_1_26_1","unstructured":"M. Morrison , and N. Ranganathan . 2011. Design of a Moore finite state machine using a novel reversible logic gate, decoder and synchronous up-counter . In Proceedings of the IEEE Conference on Nanotechnology, 1445--1449 . M. Morrison, and N. Ranganathan. 2011. Design of a Moore finite state machine using a novel reversible logic gate, decoder and synchronous up-counter. In Proceedings of the IEEE Conference on Nanotechnology, 1445--1449."},{"key":"e_1_2_1_27_1","unstructured":"M. Nielsen and I. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press.   M. Nielsen and I. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.2011.5938201"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2011.6081399"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.32.3266"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_32_1","first-page":"262","article-title":"Block-based quantum-logic synthesis","volume":"11","author":"Saeedi M.","year":"2011","unstructured":"M. Saeedi , M. Arabzadeh , M. S. Zamani , and M. Sedighi . 2011 a. Block-based quantum-logic synthesis . Quantum Inf. Process. 11 , 262 -- 277 . M. Saeedi, M. Arabzadeh, M. S. Zamani, and M. Sedighi. 2011a. Block-based quantum-logic synthesis. Quantum Inf. Process. 11, 262--277.","journal-title":"Quantum Inf. Process."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431220"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-010-0201-2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1877745.1877747"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228368"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.811448"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/784894.785070"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"volume-title":"Proceedings of the Workshop on Reversible Computing. http:\/\/www.informatik.uni-bremen.de\/revkit\/.","author":"Soeken M.","key":"e_1_2_1_40_1","unstructured":"M. Soeken , S. Frehse , R. Wille , and R. Drechsler . 2010a. RevKit: A toolkit for reversible circuit design . In Proceedings of the Workshop on Reversible Computing. http:\/\/www.informatik.uni-bremen.de\/revkit\/. M. Soeken, S. Frehse, R. Wille, and R. Drechsler. 2010a. RevKit: A toolkit for reversible circuit design. In Proceedings of the Workshop on Reversible Computing. http:\/\/www.informatik.uni-bremen.de\/revkit\/."},{"volume-title":"Proceedings of the International Design & Test Workshop, 143--148","author":"Soeken M.","key":"e_1_2_1_41_1","unstructured":"M. Soeken , R. Wille , and R. Drechsler . 2010b. Hierarchical synthesis of reversible circuits using positive and negative Davio decomposition . In Proceedings of the International Design & Test Workshop, 143--148 . M. Soeken, R. Wille, and R. Drechsler. 2010b. Hierarchical synthesis of reversible circuits using positive and negative Davio decomposition. In Proceedings of the International Design & Test Workshop, 143--148."},{"key":"e_1_2_1_42_1","volume-title":"CUDD: CU decision diagram package release 2.4.2","author":"Somenzi F.","year":"2009","unstructured":"F. Somenzi . 2009 . CUDD: CU decision diagram package release 2.4.2 . University of Colorado at Boulder. F. Somenzi. 2009. CUDD: CU decision diagram package release 2.4.2. University of Colorado at Boulder."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491682"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/646234.682540"},{"volume-title":"Proceedings of the International Symposium on Integr. Circ. 325--328","author":"Vasudevan D.","key":"e_1_2_1_45_1","unstructured":"D. Vasudevan , M. Schellekens , N. Zeinolabedini , and E. Popovici . 2011. Prototyping a bidirectional processor design based on reversible principles . In Proceedings of the International Symposium on Integr. Circ. 325--328 . D. Vasudevan, M. Schellekens, N. Zeinolabedini, and E. Popovici. 2011. Prototyping a bidirectional processor design based on reversible principles. In Proceedings of the International Symposium on Integr. Circ. 325--328."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1629984"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2008.43"},{"volume-title":"Proceedings of the Forum Specification Design Languages. 1--6.","author":"Wille R.","key":"e_1_2_1_48_1","unstructured":"R. Wille , S. Offermann , and R. Drechsler . 2010. SyReC: A programming language for synthesis of reversible circuits . In Proceedings of the Forum Specification Design Languages. 1--6. R. Wille, S. Offermann, and R. Drechsler. 2010. SyReC: A programming language for synthesis of reversible circuits. In Proceedings of the Forum Specification Design Languages. 1--6."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2011.39"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2564923","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2564923","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:53Z","timestamp":1750277693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2564923"}},"subtitle":["Reed-muller decision diagram synthesis of reversible logic circuits"],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.1145\/2564923"],"URL":"https:\/\/doi.org\/10.1145\/2564923","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2014,2]]},"assertion":[{"value":"2012-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}