{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:04Z","timestamp":1750306684785,"version":"3.41.0"},"reference-count":25,"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":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61070240 and 61170321"],"award-info":[{"award-number":["61070240 and 61170321"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Foundation of College of Jiangsu Province","award":["10KJB520021"],"award-info":[{"award-number":["10KJB520021"]}]},{"DOI":"10.13039\/501100013286","name":"Specialized Research Fund for the Doctoral Program of Higher Education","doi-asserted-by":"crossref","award":["20110092110024"],"award-info":[{"award-number":["20110092110024"]}],"id":[{"id":"10.13039\/501100013286","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,12,30]]},"abstract":"<jats:p>This article presents an algorithm which can quickly find the exact minimum solution to almost all of 4-bit reversible functions. We assume minimization of quantum cost (MQC). This algorithm is designed in the most memory-efficient way, or it will quickly run out of memory. Therefore, we construct the shortest coding of permutations, the topological compression and flexible data structures for the memory savings. First, hash tables are used for all 8-gate 4-bit circuits with the minimization of gate count (MGC) by using the GT library (with NOT, CNOT, Toffoli and Toffoli-4 gates). Second, we merge and split the hash tables, thus generating a single longer hash table for high-performance. Third, we synthesize these circuits with MQC by using the GTP library (with GT, Peres, and Inverted Peres gates) based on the hash table. Finally, according to the comparison of the QC of circuits, the algorithm can quickly converge for any 4-bit reversible circuit with MQC. By synthesizing all benchmark functions, in comparison with Szyprowski and Kerntopf [2011], the running time and QC are reduced up to 99.95% and 18.2%, respectively.<\/jats:p>","DOI":"10.1145\/2629542","type":"journal-article","created":{"date-parts":[[2015,1,5]],"date-time":"2015-01-05T13:27:09Z","timestamp":1420464429000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Synthesis Algorithm for 4-Bit Reversible Logic Circuits with Minimum Quantum Cost"],"prefix":"10.1145","volume":"11","author":[{"given":"Zhiqiang","family":"Li","sequence":"first","affiliation":[{"name":"Yangzhou University, Yangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanwu","family":"Chen","sequence":"additional","affiliation":[{"name":"Southeast University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyu","family":"Song","sequence":"additional","affiliation":[{"name":"Portland State University, Portland, OR"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Perkowski","sequence":"additional","affiliation":[{"name":"Portland State University, Portland, OR"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01886518"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.32.3266"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.871622"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431220"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.144"},{"volume-title":"Proceedings of Reed-Muller 2011 Workshop","author":"Szyprowski M.","key":"e_1_2_1_6_1","unstructured":"M. Szyprowski and P. Kerntopf . 2011. Reducing quantum cost in reversible Toffoli circuits . In Proceedings of Reed-Muller 2011 Workshop , Tuusula, Finland, IEEE Computer Society, 127--136. M. Szyprowski and P. Kerntopf. 2011. Reducing quantum cost in reversible Toffoli circuits. In Proceedings of Reed-Muller 2011 Workshop, Tuusula, Finland, IEEE Computer Society, 127--136."},{"key":"e_1_2_1_7_1","first-page":"402","article-title":"Efficient synthesis of optimal 3-qubit reversible circuits using bit operation","volume":"6","author":"Li Z.","year":"2012","unstructured":"Z. Li , H. Chen , and X. Song . 2012 . Efficient synthesis of optimal 3-qubit reversible circuits using bit operation . Int. J. Digit. Cont. Tech. Its Appl. 6 , 11, 402 -- 408 . Z. Li, H. Chen, and X. Song. 2012. Efficient synthesis of optimal 3-qubit reversible circuits using bit operation. Int. J. Digit. Cont. Tech. Its Appl. 6, 11, 402--408.","journal-title":"Int. J. Digit. Cont. Tech. Its Appl."},{"key":"e_1_2_1_8_1","unstructured":"D. Maslov. 2011. Reversible logic synthesis benchmarks page http:\/\/www.cs.uvic.ca\/&sim;dmaslov.  D. Maslov. 2011. Reversible logic synthesis benchmarks page http:\/\/www.cs.uvic.ca\/&sim;dmaslov."},{"volume-title":"Proceedings of WCCI'08","author":"Li Z.","key":"e_1_2_1_9_1","unstructured":"Z. Li , H. Chen , B. Xu , W. Liu , X. Song , and X. Xue . 2008. Fast algorithm for 4-qubit reversible logic circuits synthesis . In Proceedings of WCCI'08 . 2202--2207. Z. Li, H. Chen, B. Xu, W. Liu, X. Song, and X. Xue. 2008. Fast algorithm for 4-qubit reversible logic circuits synthesis. In Proceedings of WCCI'08. 2202--2207."},{"key":"#cr-split#-e_1_2_1_10_1.1","doi-asserted-by":"crossref","unstructured":"Z. Li H. Chen G. Yang and W. Liu. 2013. Efficient algorithms for optimal 4-bit reversible logic system synthesis. J. Appl. Math. 2013 Article ID 291410 doi.org\/10.1155\/2013\/291410 10.1155\/2013","DOI":"10.1155\/2013\/291410"},{"key":"#cr-split#-e_1_2_1_10_1.2","doi-asserted-by":"crossref","unstructured":"Z. Li H. Chen G. Yang and W. Liu. 2013. Efficient algorithms for optimal 4-bit reversible logic system synthesis. J. Appl. Math. 2013 Article ID 291410 doi.org\/10.1155\/2013\/291410","DOI":"10.1155\/2013\/291410"},{"key":"e_1_2_1_11_1","unstructured":"L. Tran N. Alhagi M. Lukac R. Fiszer M. Hawash Z. Li and M. Perkowski. 2013. An approach to synthesis of reversible circuits based on combination of methods. Tech. Rep. ECE Portland State University Portland OR.  L. Tran N. Alhagi M. Lukac R. Fiszer M. Hawash Z. Li and M. Perkowski. 2013. An approach to synthesis of reversible circuits based on combination of methods. Tech. Rep. ECE Portland State University Portland OR."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2011.2105555"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216396.1216399"},{"volume-title":"Proceedings of 5th Reed-Muller Workshop. 119--138","author":"Perkowski M.","key":"e_1_2_1_14_1","unstructured":"M. Perkowski , L. Jozwiak , P. Kerntopf , A. Mishchenko , and A. Al-Rabadi . 2001. A general decomposition for reversible logic . In Proceedings of 5th Reed-Muller Workshop. 119--138 . M. Perkowski, L. Jozwiak, P. Kerntopf, A. Mishchenko, and A. Al-Rabadi. 2001. A general decomposition for reversible logic. In Proceedings of 5th Reed-Muller Workshop. 119--138."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2007.72"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWSCAS.2002.1186906"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837440"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2008.43"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.031"},{"key":"e_1_2_1_20_1","first-page":"49","article-title":"Detection and elimination of non-trivial reversible identities","volume":"2","author":"Younes A.","year":"2011","unstructured":"A. Younes . 2011 . Detection and elimination of non-trivial reversible identities . Int. J. Comput. Sci. Eng. Appl. 2 , 4, 49 -- 61 . A. Younes. 2011. Detection and elimination of non-trivial reversible identities. Int. J. Comput. Sci. Eng. Appl. 2, 4, 49--61.","journal-title":"Int. J. Comput. Sci. Eng. Appl."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm042"},{"key":"e_1_2_1_22_1","first-page":"49","article-title":"Detection and elimination of non-trivial reversible identities","volume":"2","author":"Younes A.","year":"2012","unstructured":"A. Younes . 2012 . Detection and elimination of non-trivial reversible identities . Int. J. Comput. Sci. Eng. Appl. 2 , 4, 49 -- 61 . A. Younes. 2012. Detection and elimination of non-trivial reversible identities. Int. J. Comput. Sci. Eng. Appl. 2, 4, 49--61.","journal-title":"Int. J. Comput. Sci. Eng. Appl."},{"volume-title":"Proceedings of 21st ULSI'12.","author":"Alhagi Nouraddin","key":"e_1_2_1_23_1","unstructured":"Nouraddin Alhagi , M. Lukac , L. Tran , and M. Perkowski . 2012. Two-stage approach to the minimization of quantum circuits based on ESOP minimization and addition of a single ancilla qubit . In Proceedings of 21st ULSI'12. Nouraddin Alhagi, M. Lukac, L. Tran, and M. Perkowski. 2012. Two-stage approach to the minimization of quantum circuits based on ESOP minimization and addition of a single ancilla qubit. In Proceedings of 21st ULSI'12."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Z. Li. 2013. 4-bit reversible logic synthesis benchmarks page http:\/\/itedu.yzu.edu.cn\/&sim;zli\/4-bit.html.  Z. Li. 2013. 4-bit reversible logic synthesis benchmarks page http:\/\/itedu.yzu.edu.cn\/&sim;zli\/4-bit.html.","DOI":"10.1155\/2013\/291410"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629542","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629542","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\/2629542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,12,30]]}},"alternative-id":["10.1145\/2629542"],"URL":"https:\/\/doi.org\/10.1145\/2629542","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"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"}}]}}