{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:48:17Z","timestamp":1774687697300,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018YFA0306704"],"award-info":[{"award-number":["2018YFA0306704"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP220102059, DP180100691"],"award-info":[{"award-number":["DP220102059, DP180100691"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["61871111, 12071271"],"award-info":[{"award-number":["61871111, 12071271"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2022,11,30]]},"abstract":"<jats:p>\n            In the noisy intermediate-scale quantum era, quantum processing units suffer from, among others, highly limited connectivity between physical qubits. To make a quantum circuit effectively executable, a circuit transformation process is necessary to transform it, with overhead cost the smaller the better, into a functionally equivalent one so that the connectivity constraints imposed by the quantum processing unit are satisfied. Although several algorithms have been proposed for this goal, the overhead costs are often very high, which degenerates the fidelity of the obtained circuits sharply. One major reason for this lies in that, due to the high branching factor and vast search space, almost all of these algorithms only search very shallowly, and thus, very often, only (at most) locally optimal solutions can be reached. In this article, we propose a Monte Carlo Tree Search (MCTS) framework to tackle the circuit transformation problem, which enables the search process to go much deeper. The general framework supports implementations aiming to reduce either the size or depth of the output circuit through introducing SWAP or remote CNOT gates. The algorithms, called\n            <jats:italic>MCTS-Size<\/jats:italic>\n            and\n            <jats:italic>MCTS-Depth<\/jats:italic>\n            , are polynomial in all relevant parameters. Empirical results on extensive realistic circuits and IBM Q Tokyo show that the MCTS-based algorithms can reduce the size (respectively, depth) overhead by, on average, 66% (respectively, 84%) when compared with t\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\left| {\\mathrm{ket}} \\right\\rangle \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , an industrial-level compiler.\n          <\/jats:p>","DOI":"10.1145\/3514239","type":"journal-article","created":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T19:50:50Z","timestamp":1645213850000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Quantum Circuit Transformation: A Monte Carlo Tree Search Framework"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3244-6675","authenticated-orcid":false,"given":"Xiangzhen","family":"Zhou","sequence":"first","affiliation":[{"name":"Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology Sydney, Ultimo NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuan","family":"Feng","sequence":"additional","affiliation":[{"name":"Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology Sydney, Ultimo NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjiang","family":"Li","sequence":"additional","affiliation":[{"name":"Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology Sydney, Ultimo NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.2562110"},{"key":"e_1_3_3_4_1","volume-title":"Proceedings of the 28th International Conference on Automated Planning and Scheduling","author":"Booth Kyle E. C.","year":"2018","unstructured":"Kyle E. C. Booth, Minh Do, J. Christopher Beck, Eleanor Rieffel, Davide Venturelli, and Jeremy Frank. 2018. Comparing and integrating constraint programming and temporal planning for quantum circuit compilation. In Proceedings of the 28th International Conference on Automated Planning and Scheduling."},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2186810"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793005708001094"},{"key":"e_1_3_3_7_1","volume-title":"Proceedings of the Workshop on Quantum Information Processing","author":"Cheung Donny","year":"2007","unstructured":"Donny Cheung, Dmitri Maslov, and Simone Severini. 2007. Translation techniques between quantum circuit architectures. In Proceedings of the Workshop on Quantum Information Processing."},{"key":"e_1_3_3_8_1","volume-title":"Proceedings of the 14th Conference on the Theory of Quantum Computation, Communication, and Cryptography","author":"Childs Andrew M.","year":"2019","unstructured":"Andrew M. Childs, Eddie Schoute, and Cem M. Unsal. 2019. Circuit transformations for quantum architectures. In Proceedings of the 14th Conference on the Theory of Quantum Computation, Communication, and Cryptography."},{"key":"e_1_3_3_9_1","volume-title":"Proceedings of the 14th Conference on the Theory of Quantum Computation, Communication, and Cryptography","author":"Cowtan Alexander","year":"2019","unstructured":"Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. 2019. On the qubit routing problem. In Proceedings of the 14th Conference on the Theory of Quantum Computation, Communication, and Cryptography."},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338852.3339829"},{"key":"e_1_3_3_11_1","article-title":"Qubit allocation for noisy intermediate-scale quantum computers","author":"Finigan Will","year":"2018","unstructured":"Will Finigan, Michael Cubeddu, Thomas Lively, Johannes Flick, and Prineha Narang. 2018. Qubit allocation for noisy intermediate-scale quantum computers. arXiv preprint arXiv:1810.08291 (2018).","journal-title":"arXiv preprint arXiv:1810.08291"},{"key":"e_1_3_3_12_1","article-title":"Reducing the CNOT count for Clifford+T circuits on NISQ architectures","author":"Gheorghiu Vlad","year":"2020","unstructured":"Vlad Gheorghiu, Sarah Meng Li, Michele Mosca, and Priyanka Mukhopadhyay. 2020. Reducing the CNOT count for Clifford+T circuits on NISQ architectures. arXiv preprint arXiv:2011.12191 (2020).","journal-title":"arXiv preprint arXiv:2011.12191"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aaa5cc"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394885.3431604"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3287624.3287701"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11871842_29"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2021.3068355"},{"key":"e_1_3_3_18_1","first-page":"3","article-title":"Mapping of quantum circuits onto NISQ superconducting processors","volume":"2","author":"Lao Lingling","year":"2019","unstructured":"Lingling Lao, Daniel M. Manzano, Hans van Someren, Imran Ashraf, and Carmen G. Almudever. 2019. Mapping of quantum circuits onto NISQ superconducting processors. Quantum 2 (2019), 3.","journal-title":"Quantum"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304023"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.3023247"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2015.7059001"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278717"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304075"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab79b1"},{"key":"e_1_3_3_25_1","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen Michael A.","year":"2002","unstructured":"Michael A. Nielsen and Isaac Chuang. 2002. Quantum Computation and Quantum Information. Cambridge University Press."},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386162"},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93031-2_32"},{"key":"e_1_3_3_28_1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-030-14082-3_18","volume-title":"International Workshop on Quantum Technology and Optimization Problems","author":"Paler Alexandru","year":"2019","unstructured":"Alexandru Paler. 2019. On the influence of initial qubit placement during NISQ circuit compilation. In International Workshop on Quantum Technology and Optimization Problems. Springer, 207\u2013217."},{"key":"e_1_3_3_29_1","article-title":"Using reinforcement learning to perform qubit routing in quantum compilers","author":"Pozzi Matteo G.","year":"2020","unstructured":"Matteo G. Pozzi, Steven J. Herbert, Akash Sengupta, and Robert D. Mullins. 2020. Using reinforcement learning to perform qubit routing in quantum compilers. arXiv preprint arXiv:2007.15957 (2020).","journal-title":"arXiv preprint arXiv:2007.15957"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33017707"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-010-0201-2"},{"key":"e_1_3_3_32_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature16961"},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature24270"},{"key":"e_1_3_3_34_1","article-title":"Qubit routing using graph neural network aided Monte Carlo tree search","author":"Sinha Animesh","year":"2021","unstructured":"Animesh Sinha, Utkarsh Azad, and Harjinder Singh. 2021. Qubit routing using graph neural network aided Monte Carlo tree search. arXiv preprint arXiv:2104.01992 (2021).","journal-title":"arXiv preprint arXiv:2104.01992"},{"key":"e_1_3_3_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3168822"},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360546"},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8e92"},{"key":"e_1_3_3_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.3009140"},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/3171837.3171907"},{"key":"e_1_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aaa331"},{"key":"e_1_3_3_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317859"},{"key":"e_1_3_3_42_1","article-title":"A depth-aware swap insertion scheme for the qubit mapping problem","author":"Zhang Chi","year":"2020","unstructured":"Chi Zhang, Yanhao Chen, Yuwei Jin, Wonsun Ahn, Youtao Zhang, and Eddy Z. Zhang. 2020. A depth-aware swap insertion scheme for the qubit mapping problem. arXiv preprint arXiv:2002.07289 (2020).","journal-title":"arXiv preprint arXiv:2002.07289"},{"key":"e_1_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446706"},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3400302.3415621"},{"key":"e_1_3_3_45_1","article-title":"Supervised learning enhanced quantum circuit transformation","author":"Zhou Xiangzhen","year":"2021","unstructured":"Xiangzhen Zhou, Yuan Feng, and Sanjiang Li. 2021. Supervised learning enhanced quantum circuit transformation. arXiv preprint arXiv:2110.03057 (2021).","journal-title":"arXiv preprint arXiv:2110.03057"},{"key":"e_1_3_3_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.2969647"},{"key":"e_1_3_3_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-020-02901-4"},{"key":"e_1_3_3_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2846658"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514239","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:14Z","timestamp":1750183814000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,27]]},"references-count":47,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11,30]]}},"alternative-id":["10.1145\/3514239"],"URL":"https:\/\/doi.org\/10.1145\/3514239","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,27]]},"assertion":[{"value":"2021-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}