{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T14:53:41Z","timestamp":1754146421340,"version":"3.41.2"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"TSMC, MPI, and NSTC of Taiwan","award":["NSTC 114-2927-I-011-501, 114-2640-E-002-001, 114-2640-E-006-001, and 113-2222-E-011-005-MY3"],"award-info":[{"award-number":["NSTC 114-2927-I-011-501, 114-2640-E-002-001, 114-2640-E-006-001, and 113-2222-E-011-005-MY3"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2025,7,31]]},"abstract":"<jats:p>State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.<\/jats:p>","DOI":"10.1145\/3744646","type":"journal-article","created":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T07:16:46Z","timestamp":1750058206000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Layout Synthesis for Quantum Circuits Considering Toffoli Gate Decomposition"],"prefix":"10.1145","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-6191-518X","authenticated-orcid":false,"given":"Po-Wei","family":"Chen","sequence":"first","affiliation":[{"name":"National Taiwan University of Science and Technology","place":["Taipei, Taiwan"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9002-681X","authenticated-orcid":false,"given":"Sheng-Tan","family":"Huang","sequence":"additional","affiliation":[{"name":"National Taiwan University of Science and Technology","place":["Taipei, Taiwan"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6675-2676","authenticated-orcid":false,"given":"Shao-Yun","family":"Fang","sequence":"additional","affiliation":[{"name":"Electrical Engineering, National Taiwan University of Science and Technology","place":["Taipei, Taiwan"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,18]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_1_3_2","first-page":"052327","article-title":"Speed limits for quantum gates in multiqubit systems","volume":"85","author":"Ashhab S.","year":"2012","unstructured":"S. Ashhab, P. C. de Groot, and F. Nori. 2012. Speed limits for quantum gates in multiqubit systems. PhysRevA. 85, 5 (2012), 052327.","journal-title":"PhysRevA."},{"key":"e_1_3_1_4_2","first-page":"022426","article-title":"Numerical analysis of quantum circuits for state preparation and unitary operator synthesis","volume":"106","author":"Ashhab S.","year":"2022","unstructured":"S. Ashhab, N. Yamamoto, F. Yoshihara, and K. Semba. 2022. Numerical analysis of quantum circuits for state preparation and unitary operator synthesis. PhysRevA. 106, 2 (2022), 022426.","journal-title":"PhysRevA."},{"key":"e_1_3_1_5_2","first-page":"052605","article-title":"Quantum circuit synthesis via a random combinatorial search","volume":"109","author":"Ashhab S.","year":"2024","unstructured":"S. Ashhab, F. Yoshihara, M. Tsuji, M. Sato, and K. Semba. 2024. Quantum circuit synthesis via a random combinatorial search. PhysRevA. 109, 5 (2024), 052605.","journal-title":"PhysRevA."},{"volume-title":"Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u201919)","author":"Li G.","key":"e_1_3_1_6_2","unstructured":"G. Li, Y. Ding, and Y. Xie. 2019. Tackling the qubit mapping problem for NISQ-Era quantum devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u201919). 1001\u20131014."},{"volume-title":"Proceedings of the 59th ACM\/IEEE Design Automation Conference (DAC\u201922)","author":"Park S.","key":"e_1_3_1_7_2","unstructured":"S. Park, D. Kim, M. Kweon, J.-Y. Sim, and S. Kang. 2022. A fast and scalable qubit-mapping method for noisy intermediate-scale quantum computers. In Proceedings of the 59th ACM\/IEEE Design Automation Conference (DAC\u201922). 13\u201318."},{"volume-title":"Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u201921)","author":"Duckering C.","key":"e_1_3_1_8_2","unstructured":"C. Duckering, J. Baker, A. Litteken, and F. T. Chong. 2021. Orchestrated trios: Compiling for efficient communication in Quantum programs with 3-Qubit gates. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u201921). 375\u2013385."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2019.10.004"},{"volume-title":"Proceedings of the 56th Annual Design Automation Conference 2019 (DAC\u201919)","author":"Wille R.","key":"e_1_3_1_10_2","unstructured":"R. Wille, L. Burgholzer, and A. Zulehner. 2022. Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H Operations. In Proceedings of the 56th Annual Design Automation Conference 2019 (DAC\u201919). 1\u20136."},{"volume-title":"Proceedings of the 39th International Conference on Computer-Aided Design (ICCAD\u201920)","author":"Tan B.","key":"e_1_3_1_11_2","unstructured":"B. Tan and J. Cong. 2020. Optimal layout synthesis for quantum computing. In Proceedings of the 39th International Conference on Computer-Aided Design (ICCAD\u201920). 1\u20139."},{"volume-title":"2021 IEEE\/ACM International Conference On Computer Aided Design (ICCAD\u201921)","author":"Tan B.","key":"e_1_3_1_12_2","unstructured":"B. Tan and J. Cong. 2021. Optimal qubit mapping with simultaneous gate absorption. In 2021 IEEE\/ACM International Conference On Computer Aided Design (ICCAD\u201921). 1\u20138."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3508352.3549394"},{"key":"e_1_3_1_14_2","unstructured":"M. A. Nielsen and I. L. Chuang. 2010. Quantum computation and quantum information quantum 10th edition. Cambridge University Press."},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"N. Schuch. 2002. Implementation of quantum algorithms with Josephson charge qubits. Universit\u00e4t Regensburg.","DOI":"10.1002\/1521-3951(200210)233:3<482::AID-PSSB482>3.0.CO;2-F"},{"key":"e_1_3_1_16_2","unstructured":"C. Gidney. 2015. Constructing large controlled nots. Retrieved from https:\/\/algassert.com\/circuits\/2015\/06\/05\/Constructing-Large-Controlled-Nots.html"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10773-017-3389-4"},{"key":"e_1_3_1_18_2","unstructured":"J. M. Baker C. Duckering A. Hoover and F. T. Chong. 2019. Decomposing quantum generalized toffoli with an arbitrary number of ancilla. arXiv preprint arXiv:1904.01671."},{"volume-title":"Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201908\/ETAPS\u201908)","author":"Moura L. d.","key":"e_1_3_1_19_2","unstructured":"L. d. Moura and N. Bj\u00f8rner. 2008. Z3: An efficient SMT solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201908\/ETAPS\u201908). 337\u2013340."},{"volume-title":"38th International Symposium on Multiple Valued Logic (ISMVL\u201908)","author":"Wille R.","key":"e_1_3_1_20_2","unstructured":"R. Wille, D. Gro\u00dfe, L. Teuber, G. W. Dueck, and R. Drechsler. 2008. RevLib: An online resource for reversible functions and reversible circuits. In 38th International Symposium on Multiple Valued Logic (ISMVL\u201908). 220\u2013225."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,18]],"date-time":"2025-07-18T08:28:08Z","timestamp":1752827288000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,18]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7,31]]}},"alternative-id":["10.1145\/3744646"],"URL":"https:\/\/doi.org\/10.1145\/3744646","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2025,7,18]]},"assertion":[{"value":"2024-10-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-04","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}