{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:59:29Z","timestamp":1740142769557,"version":"3.37.3"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"10","license":[{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61961023"],"award-info":[{"award-number":["61961023"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004607","name":"Guangxi Natural Science Foundation","doi-asserted-by":"publisher","award":["2021GXNSFAA220046","2018GXNSFAA050020"],"award-info":[{"award-number":["2021GXNSFAA220046","2018GXNSFAA050020"]}],"id":[{"id":"10.13039\/501100004607","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004479","name":"Jiangxi Provincial Natural Science Foundation","doi-asserted-by":"crossref","award":["20202BABL202007"],"award-info":[{"award-number":["20202BABL202007"]}],"id":[{"id":"10.13039\/501100004479","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Doctoral Foundation of Guangxi University of Science and Technology","award":["21Z04"],"award-info":[{"award-number":["21Z04"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Reversible circuit synthesis methods based on decision diagrams achieve low quantum costs but do not account for quantum bit (qubit) limits for the application of reversible logic in quantum computing. Here, a synthesis method using sub-graphs of shared functional decision diagrams (SFDDs) is proposed for reducing the number of lines when synthesizing reversible circuits. An SFDD is partitioned into sub-graphs by exploiting the longest dominant-active paths, and the sub-graphs are mapped to reversible gate cascades. To further reduce the number of lines, template root matching is presented for reusing circuit lines. Experimental results indicate that the proposed method achieves the known minimum number of lines in many cases and has good scalability. Although the proposed method increases the quantum cost over a prior method based on functional decision diagrams, it significantly reduces the number of lines in most cases. Compared with the one-pass method using quantum multiple-valued decision diagrams, the proposed method reduces the quantum cost without increasing the number of lines in many cases. When compared with the lookup table-based method using a direct mapping flow, the method reduces the number of lines in a few cases. Thus, the method aids in the physical realization of a quantum circuit.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac107","type":"journal-article","created":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T16:11:16Z","timestamp":1659456676000},"page":"2574-2592","source":"Crossref","is-referenced-by-count":1,"title":["Reversible Circuit Synthesis Method Using Sub-graphs of Shared Functional Decision Diagrams"],"prefix":"10.1093","volume":"66","author":[{"given":"Dengli","family":"Bu","sequence":"first","affiliation":[{"name":"School of Electrical, Electronic and Computer Science, Guangxi University of Science and Technology , Liuzhou 545006, P.R. China"},{"name":"School of Electronics and Information Engineering, Jinggangshan University , Ji\u2019an 343009, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junyi","family":"Deng","sequence":"additional","affiliation":[{"name":"School of Electrical, Electronic and Computer Science, Guangxi University of Science and Technology , Liuzhou 545006, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pengjie","family":"Tang","sequence":"additional","affiliation":[{"name":"School of Electronics and Information Engineering, Jinggangshan University , Ji\u2019an 343009, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuhong","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Electrical, Electronic and Computer Science, Guangxi University of Science and Technology , Liuzhou 545006, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,8,1]]},"reference":[{"key":"2023101421214977400_ref1","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1147\/rd.53.0183","article-title":"Irreversibility and heat generation in the computing process","volume":"5","author":"Landauer","year":"1961","journal-title":"IBM J. Res. Dev."},{"key":"2023101421214977400_ref2","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1147\/rd.176.0525","article-title":"Logical reversibility of computation","volume":"17","author":"Bennett","year":"1973","journal-title":"IBM J. Res. Dev."},{"key":"2023101421214977400_ref3","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1007\/3-540-10003-2_104","volume-title":"Proceedings of International Colloquium on Automata, Languages, and Programming","author":"Toffoli","year":"1980"},{"volume-title":"Quantum Computation and Quantum Information: 10th Anniversary Edition","year":"2010","author":"Nielsen","key":"2023101421214977400_ref4"},{"key":"2023101421214977400_ref5","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s11128-013-0642-5","article-title":"Considering nearest neighbor constraints of quantum circuits at the reversible circuit level","volume":"13","author":"Wille","year":"2014","journal-title":"Quantum Inf. Process."},{"key":"2023101421214977400_ref6","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1109\/ISMVL.2019.00027","volume-title":"Proceedings of 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL)","author":"Niemann","year":"2019"},{"key":"2023101421214977400_ref7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-31937-7","volume-title":"Reversible and Quantum Circuits: Optimization and Complexity Analysis","author":"Abdessaied","year":"2016"},{"key":"2023101421214977400_ref8","first-page":"996","article-title":"One-pass design of reversible circuits: combining embedding and synthesis for reversible logic","volume":"37","author":"Zulehner","year":"2018","journal-title":"IEEE Trans. Comput. Aided Design Integrated Circuits Syst."},{"key":"2023101421214977400_ref9","doi-asserted-by":"crossref","first-page":"42:1","DOI":"10.1145\/1278349.1278355","article-title":"Techniques for the synthesis of reversible Toffoli networks","volume":"12","author":"Maslov","year":"2007","journal-title":"ACM Trans. Design Autom. Electron. Syst."},{"key":"2023101421214977400_ref10","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/978-3-319-59936-6_10","volume-title":"Proceedings of International Conference on Reversible Computation","author":"Parlapalli","year":"2017"},{"key":"2023101421214977400_ref11","doi-asserted-by":"crossref","first-page":"1675","DOI":"10.1109\/TCAD.2018.2859251","article-title":"LUT-based hierarchical reversible logic synthesis","volume":"38","author":"Soeken","year":"2019","journal-title":"IEEE Trans. Comput. Aided Design Integrated Circuits Syst."},{"key":"2023101421214977400_ref12","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1145\/1629911.1629984","volume-title":"Proceedings of the 46th Annual Design Automation Conference","author":"Wille","year":"2009"},{"key":"2023101421214977400_ref13","doi-asserted-by":"crossref","first-page":"2050079:1","DOI":"10.1142\/S0218126620500796","article-title":"Reversible circuits synthesis from functional decision diagrams by using node dependency matrices","volume":"29","author":"Stojkovi\u0107","year":"2020","journal-title":"J. Circuits Syst. Comput."},{"volume-title":"Proceedings of 2015 IEEE Pacific Rim Conference on Communications","year":"2015","author":"Law","key":"2023101421214977400_ref14"},{"key":"2023101421214977400_ref15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/ISMVL.2015.21","volume-title":"Proceedings of 2015 IEEE International Symposium on Multiple-Valued Logic","author":"Chattopadhyay","year":"2015"},{"key":"2023101421214977400_ref16","doi-asserted-by":"crossref","first-page":"470","DOI":"10.23919\/DATE.2017.7927035","volume-title":"Proceedings of Design, Automation & Test in Europe","author":"Soeken","year":"2017"},{"key":"2023101421214977400_ref17","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1049\/iet-cdt.2017.0097","article-title":"Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures","volume":"13","author":"Bandyopadhyay","year":"2019","journal-title":"IET Comput. Digital Tech."},{"key":"2023101421214977400_ref18","doi-asserted-by":"crossref","first-page":"1208","DOI":"10.1109\/TC.2014.2315641","article-title":"A post-synthesis optimization technique for reversible circuits exploiting negative control lines","volume":"64","author":"Datta","year":"2015","journal-title":"IEEE Trans. Comput."},{"key":"2023101421214977400_ref19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jsc.2015.03.002","article-title":"Ancilla-free synthesis of large reversible functions using binary decision diagrams","volume":"73","author":"Soeken","year":"2016","journal-title":"J. Symb. Comput."},{"key":"2023101421214977400_ref20","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/2564923","article-title":"RMDDS: Reed-Muller decision diagram synthesis of reversible logic circuits","volume":"10","author":"Lin","year":"2014","journal-title":"ACM J. Emerg. Technol. Comput. Syst."},{"key":"2023101421214977400_ref21","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1109\/TCAD.2005.847911","article-title":"Toffoli network synthesis with templates","volume":"24","author":"Maslov","year":"2005","journal-title":"IEEE Trans. Comput. Aided Design Integrated Circuits Syst."},{"key":"2023101421214977400_ref22","first-page":"385","article-title":"A shared-cube approach to ESOP-based synthesis of reversible logic","volume":"24","author":"Nayeem","year":"2011","journal-title":"Facta universitatis\u2014ser.: Electron. Energetics"},{"key":"2023101421214977400_ref23","first-page":"1866","article-title":"Reversible circuit synthesis method based on maximum weighted output-compatibility class of ESOP","volume":"46","author":"Bu","year":"2018","journal-title":"Acta Electron. Sinica"},{"key":"2023101421214977400_ref24","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.vlsi.2019.04.008","article-title":"An improved KFDD based reversible circuit synthesis method","volume":"69","author":"Bu","year":"2019","journal-title":"Integration VLSI J."},{"key":"2023101421214977400_ref25","doi-asserted-by":"crossref","first-page":"21:1","DOI":"10.1145\/2431211.2431220","article-title":"Synthesis and optimization of reversible circuits\u2013a survey","volume":"45","author":"Saeedi","year":"2013","journal-title":"ACM Comput. Surv."},{"key":"2023101421214977400_ref26","doi-asserted-by":"crossref","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","article-title":"Elementary gates for quantum computation","volume":"52","author":"Barenco","year":"1995","journal-title":"Phys. Rev. A"},{"key":"2023101421214977400_ref27","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1080\/00207210412331272643","article-title":"Representation of Boolean quantum circuits as Reed-Muller expansions","volume":"91","author":"Younes","year":"2004","journal-title":"Int. J. Electron."},{"key":"2023101421214977400_ref28","doi-asserted-by":"crossref","first-page":"1294","DOI":"10.1109\/12.544485","article-title":"Fast OFDD-based minimization of fixed polarity Reed-Muller expressions","volume":"45","author":"Drechsler","year":"1996","journal-title":"IEEE Trans. Comput."},{"key":"2023101421214977400_ref29","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/43.728917","article-title":"Ordered Kronecker functional decision diagrams\u2013a data structure for representation and manipulation of Boolean functions","volume":"17","author":"Drechsler","year":"1998","journal-title":"IEEE Trans. Comput. Aided Design Integrated Circuits Syst."},{"key":"2023101421214977400_ref30","first-page":"220","volume-title":"Proceedings of 38th International Symposium on Multiple Valued Logic","author":"Wille","year":"2008"},{"volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","year":"2004","author":"Schrijver","key":"2023101421214977400_ref31"},{"volume-title":"Logic Synthesis and Optimization Benchmark User Guide Version 3.0","year":"1991","author":"Yang","key":"2023101421214977400_ref32"},{"key":"2023101421214977400_ref33","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph-based algorithms for Boolean function manipulation","volume":"C-35","author":"Bryant","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"2023101421214977400_ref34","first-page":"64","volume-title":"Proceedings of International Workshop on Reversible Computation","author":"Soeken","year":"2011"},{"key":"2023101421214977400_ref35","first-page":"242","volume-title":"Proceedings of 5th International Workshop on Applications of the Reed-Muller Expansion in Circuit Design","author":"Mishchenko","year":"2001"},{"volume-title":"CUDD: CU Decision Diagram Package Release 2.5.0.","year":"2012","author":"Somenzi","key":"2023101421214977400_ref36"},{"article-title":"EXTRA v. 2.0: Software Library Extending CUDD Package","year":"2003","author":"Mishchenko","key":"2023101421214977400_ref37"},{"volume-title":"Proceedings of the 24th International Workshop on Logic & Synthesis","year":"2015","author":"Amar\u00fa","key":"2023101421214977400_ref38"},{"volume-title":"ABC: A System for Sequential Synthesis and Verification","year":"2013","author":"Berkeley Logic Synthesis and Verification Group","key":"2023101421214977400_ref39"},{"key":"2023101421214977400_ref40","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/j.microrel.2017.12.031","article-title":"Towards AND\/XOR balanced synthesis: logic circuits rewriting with XOR","volume":"81","author":"H\u00e1le\u010dek","year":"2018","journal-title":"Microelectron. Reliab."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/10\/2574\/52134864\/bxac107.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/10\/2574\/52134864\/bxac107.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T14:28:15Z","timestamp":1727706495000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/10\/2574\/6652787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,1]]},"references-count":40,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,8,1]]},"published-print":{"date-parts":[[2023,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac107","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2023,10]]},"published":{"date-parts":[[2022,8,1]]}}}