{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:04Z","timestamp":1787017384593,"version":"build-2736575974"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,7,13]],"date-time":"2024-07-13T00:00:00Z","timestamp":1720828800000},"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. Quantum Comput."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>\n                    An algorithm for reversible logic synthesis is proposed. The task is, for a given\n                    <jats:italic>n<\/jats:italic>\n                    -bit substitution map, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates with\n                    <jats:italic>m<\/jats:italic>\n                    control bits, where\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(m \\in \\lbrace 0, \\ldots , n-1\\rbrace\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . Controlled gates with large\n                    <jats:italic>m<\/jats:italic>\n                    (&gt; 2) are then further decomposed into smaller gates (\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(m \\le 2\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    ). A primary goal in designing the algorithm is to reduce the number of Toffoli gates, which is known to be universal.\n                  <\/jats:p>\n                  <jats:p>\n                    The main idea is to view an\n                    <jats:italic>n<\/jats:italic>\n                    -bit substitution map as a rank-2\n                    <jats:italic>n<\/jats:italic>\n                    tensor and to transform it such that the resulting map can be written as a tensor product of a rank-(2\n                    <jats:italic>n<\/jats:italic>\n                    -2) tensor and the 2\u00d7 2 identity matrix. It can then be seen that the transformed map acts nontrivially on\n                    <jats:italic>n<\/jats:italic>\n                    -1 bits only, meaning that the map to be synthesized becomes (\n                    <jats:italic>n<\/jats:italic>\n                    -1)-bit substitution. This size reduction process is iteratively applied until it reaches a tensor product of only 2\u00d7 2 matrices.\n                  <\/jats:p>\n                  <jats:p>\n                    The time complexity of the algorithm is exponential in\n                    <jats:italic>n<\/jats:italic>\n                    , as most previously known heuristic algorithms for reversible logic synthesis are, but it terminates within reasonable time for not too large\n                    <jats:italic>n<\/jats:italic>\n                    , which may find practical uses. As stated earlier, our primary target is to reduce the number of Toffoli gates in the output circuit. Benchmark results show that the algorithm works well for hard benchmark functions, but it does not seem advantageous when the function is structured. As an application, the algorithm is applied to find reversible circuits for cryptographic substitution boxes, which are often required in quantum cryptanalysis.\n                  <\/jats:p>","DOI":"10.1145\/3673242","type":"journal-article","created":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T05:21:43Z","timestamp":1718688103000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-2387-2364","authenticated-orcid":false,"given":"Hochang","family":"Lee","sequence":"first","affiliation":[{"name":"The Affiliated Institute of ETRI, Daejeon, Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7988-6761","authenticated-orcid":false,"given":"Kyung Chul","family":"Jeong","sequence":"additional","affiliation":[{"name":"The Affiliated Institute of ETRI, Daejeon, Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3285-3802","authenticated-orcid":false,"given":"Daewan","family":"Han","sequence":"additional","affiliation":[{"name":"The Affiliated Institute of ETRI, Daejeon, Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2657-311X","authenticated-orcid":false,"given":"Panjin","family":"Kim","sequence":"additional","affiliation":[{"name":"The Affiliated Institute of ETRI, Daejeon, Korea (the Republic of)"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,7,13]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Hochang Lee. 2021. Algorithm implementation. GitHub Repository Retrieved from https:\/\/github.com\/ReversibleLogicCircuit\/SizeReduction"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2004.1269099"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-018-1864-3"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2244643"},{"key":"e_1_3_3_7_2","unstructured":"Mona Arabzadeh and Mehdi Saeedi. 2013. RCViewer+ version 2.5 (2013). http:\/\/ceit.aut.ac.ir\/QDA\/RCV.htm"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-40186-3_15"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"issue":"106","key":"e_1_3_3_10_2","article-title":"The KHAZAD legacy-level block cipher","volume":"97","author":"Barreto P. S. L. M.","year":"2000","unstructured":"P. S. L. M. Barreto and Vincent Rijmen. 2000. The KHAZAD legacy-level block cipher. Primitive Submitted to NESSIE 97, 106 (2000).","journal-title":"Primitive Submitted to NESSIE"},{"key":"e_1_3_3_11_2","first-page":"105","article-title":"Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete","volume":"9","author":"Bernstein Daniel J.","year":"2009","unstructured":"Daniel J. Bernstein. 2009. Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete? Workshop Rec. SHARCS\u201909: Special-purp. Hardw. Attack. Cryptog. Syst. 9 (2009), 105.","journal-title":"Workshop Rec. SHARCS\u201909: Special-purp. Hardw. Attack. Cryptog. Syst."},{"key":"e_1_3_3_12_2","article-title":"Quantum Search for Lightweight Block Ciphers: GIFT, SKINNY, SATURNIN","author":"Bijwe Subodh","year":"2020","unstructured":"Subodh Bijwe, Amit Kumar Chauhan, and Somitra Kumar Sanadhya. 2020. Quantum Search for Lightweight Block Ciphers: GIFT, SKINNY, SATURNIN. Cryptology ePrint Archive, Report 2020\/1485. Retrieved from https:\/\/eprint.iacr.org\/2020\/1485","journal-title":"Cryptology ePrint Archive, Report 2020\/1485"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.13154\/tosc.v2019.i2.55-93"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-022-00583-7"},{"issue":"01","key":"e_1_3_3_15_2","first-page":"1170","article-title":"Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function","volume":"71","author":"Bravyi S.","year":"2021","unstructured":"S. Bravyi, T. Yoder, and D. Maslov. 2021. Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function. IEEE Trans. Comput. 71, 01 (Apr.2021), 1170\u20131180.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.73590"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-66626-2_13"},{"key":"e_1_3_3_18_2","first-page":"286","article-title":"DORCIS: Depth optimized quantum implementation of substitution boxes","author":"Chun Matthew","year":"2023","unstructured":"Matthew Chun, Anubhab Baksi, and Anupam Chattopadhyay. 2023. DORCIS: Depth optimized quantum implementation of substitution boxes. IACR Cryptol. ePrint Arch. (2023), 286. Retrieved from https:\/\/eprint.iacr.org\/2023\/286","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.3897\/jucs.69617"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/2821589"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/SOCC46988.2019.1570548320"},{"key":"e_1_3_3_22_2","unstructured":"Maslov Dmitri. 2009. Reversible logic synthesis benchmarks page.Retrieved from https:\/\/reversiblebenchmarks.github.io\/"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/2012086.2012090"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACRIM.2007.4313212"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837440"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.144"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29360-8_3"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.79.325"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.871622"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10773-017-3389-4"},{"key":"e_1_3_3_31_2","first-page":"1","article-title":"Quantum implementation and analysis of DEFAULT","author":"Jang Kyungbae","year":"2023","unstructured":"Kyungbae Jang, Anubhab Baksi, Jakub Breier, Hwajeong Seo, and Anupam Chattopadhyay. 2023. Quantum implementation and analysis of DEFAULT. Cryptog. Commun. (2023), 1\u201317.","journal-title":"Cryptog. Commun."},{"key":"e_1_3_3_32_2","article-title":"Grover on GIFT","author":"Jang Kyoungbae","year":"2020","unstructured":"Kyoungbae Jang, Hyunjun Kim, Siwoo Eum, and Hwajeong Seo. 2020. Grover on GIFT. Cryptology ePrint Archive, Report 2020\/1405. Retrieved from https:\/\/eprint.iacr.org\/2020\/1405","journal-title":"Cryptology ePrint Archive, Report 2020\/1405"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.3390\/electronics10101194"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_10"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5_8"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996789"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-018-2107-3"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.88.052307"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2020.2965697"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/WGEC.2008.37"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/S11128-023-04002-4"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1278349.1278355"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2006.35"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2004.1319923"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775915"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISED.2012.81"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.93.130502"},{"issue":"46","key":"e_1_3_3_48_2","article-title":"Data encryption standard","author":"Standards National Bureau of","year":"1977","unstructured":"National Bureau of Standards. 1977. Data encryption standard. FIPS Public.46 (1977).","journal-title":"FIPS Public."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_3_3_50_2","unstructured":"NIST. 1998. Skipjack and KEA algorithm specifications version 2.0. (May1998). https:\/\/csrc.nist.gov\/Presentations\/1998\/Skipjack-and-KEA-Algorithm-Specifications"},{"key":"e_1_3_3_51_2","volume-title":"Advanced Encryption Standard","year":"2001","unstructured":"NIST. 2001. Advanced Encryption Standard. FIPS PUB 197. https:\/\/csrc.nist.gov\/pubs\/fips\/197\/final"},{"key":"e_1_3_3_52_2","article-title":"Depth-optimized implementation of ASCON quantum circuit","author":"Oh Yujin","year":"2023","unstructured":"Yujin Oh, Kyungbae Jang, Anubhab Baksi, and Hwajeong Seo. 2023. Depth-optimized implementation of ASCON quantum circuit. Cryptology ePrint Archive, Paper 2023\/1030. Retrieved from https:\/\/eprint.iacr.org\/2023\/1030","journal-title":"Cryptology ePrint Archive, Paper 2023\/1030"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.5555\/2011763.2011767"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-08760-8_19"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/1216396.1216399"},{"key":"e_1_3_3_56_2","article-title":"Grover on Present: Quantum Resource Estimation","author":"Rahman Mostafizar","year":"2021","unstructured":"Mostafizar Rahman and Goutam Paul. 2021. Grover on Present: Quantum Resource Estimation. Cryptology ePrint Archive, Report 2021\/1655. Retrieved from https:\/\/eprint.iacr.org\/2021\/1655","journal-title":"Cryptology ePrint Archive, Report 2021\/1655"},{"key":"e_1_3_3_57_2","unstructured":"RevLib. 2008. An online resources for reversible functions and circuits. (2008). http:\/\/www.revlib.org"},{"key":"e_1_3_3_58_2","unstructured":"M. Saeedi. 2008. QDA Reversible Benchmarks. Retrieved from http:\/\/ceit.aut.ac.ir\/qda\/benchmarks.htm"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.5555\/2011395.2011401"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","unstructured":"Mehdi Saeedi and Igor L. Markov. 2013. Synthesis and optimization of reversible circuits-a survey Vol. 45. Association for Computing Machinery New York NY USA. 10.1145\/2431211.2431220","DOI":"10.1145\/2431211.2431220"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/1877745.1877747"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/1877745.1877747"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.5555\/523426"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aop.2010.09.012"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.7873\/DATE.2013.256"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.811448"},{"key":"e_1_3_3_67_2","article-title":"Grover on SPEEDY","author":"Song Gyeongju","year":"2021","unstructured":"Gyeongju Song, Kyungbae Jang, Hyunjun Kim, Siwoo Eum, Minjoo Sim, Hyunji Kim, Wai-Kong Lee, and Hwajeong Seo. 2021. Grover on SPEEDY. Cryptology ePrint Archive, Report 2021\/1211. Retrieved from https:\/\/eprint.iacr.org\/2021\/1211","journal-title":"Cryptology ePrint Archive, Report 2021\/1211"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10003-2_104"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1017\/978-90-481-3065-8"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.3934\/amc.2008.2.183"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2012.71"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm042"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40578-0_17"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.62.052305"},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.69.042309"},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64834-3_24"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3673242","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3673242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:03:40Z","timestamp":1750277020000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3673242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,13]]},"references-count":75,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3673242"],"URL":"https:\/\/doi.org\/10.1145\/3673242","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,13]]},"assertion":[{"value":"2024-02-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}