{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T18:40:53Z","timestamp":1772822453518,"version":"3.50.1"},"reference-count":35,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-21-1-2575"],"award-info":[{"award-number":["N00014-21-1-2575"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1016\/j.dam.2025.08.005","type":"journal-article","created":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T21:15:18Z","timestamp":1755551718000},"page":"480-497","update-policy":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Parallel token swapping for qubit routing"],"prefix":"10.1016","volume":"377","author":[{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-5083-309X","authenticated-orcid":false,"given":"Ishan","family":"Bansal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oktay","family":"G\u00fcnl\u00fck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Shapley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.dam.2025.08.005_b1","series-title":"30th Annual European Symposium on Algorithms (ESA 2022)","first-page":"3:1","article-title":"Hardness of token swapping on trees","author":"Aichholzer","year":"2022"},{"issue":"3","key":"10.1016\/j.dam.2025.08.005_b2","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/S0895480192236628","article-title":"Routing permutations on graphs via matchings","volume":"7","author":"Alon","year":"1994","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.dam.2025.08.005_b3","doi-asserted-by":"crossref","DOI":"10.1103\/PRXQuantum.4.010313","article-title":"Advantages and limitations of quantum routing","volume":"4","author":"Bapat","year":"2023","journal-title":"PRX Quantum"},{"key":"10.1016\/j.dam.2025.08.005_b4","series-title":"A Survey of Qubit Routing Algorithms","author":"Barnes","year":"2023"},{"key":"10.1016\/j.dam.2025.08.005_b5","doi-asserted-by":"crossref","first-page":"2656","DOI":"10.1007\/s00453-017-0387-0","article-title":"Complexity of token swapping and its variants","volume":"80","author":"Bonnet","year":"2018","journal-title":"Algorithmica"},{"issue":"232","key":"10.1016\/j.dam.2025.08.005_b6","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1080\/14786444908646287","article-title":"LxxVII. Note on the theory of permutations","volume":"34","author":"Cayley","year":"1849","journal-title":"Lond. Edinb. Dublin Philos. Mag. J. Sci."},{"key":"10.1016\/j.dam.2025.08.005_b7","series-title":"14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)","first-page":"3:1","article-title":"Circuit transformations for quantum architectures","author":"Childs","year":"2019"},{"key":"10.1016\/j.dam.2025.08.005_b8","series-title":"14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)","article-title":"On the qubit routing problem","author":"Cowtan","year":"2019"},{"issue":"6","key":"10.1016\/j.dam.2025.08.005_b9","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1137\/18M1194341","article-title":"Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch","volume":"48","author":"Demaine","year":"2019","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.dam.2025.08.005_b10","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevResearch.6.033313","article-title":"Quantum routing with teleportation","volume":"6","author":"Devulapalli","year":"2024","journal-title":"Phys. Rev. Res."},{"key":"10.1016\/j.dam.2025.08.005_b11","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","article-title":"The complexity of finding minimum-length generator sequences","volume":"36","author":"Jerrum","year":"1985","journal-title":"Theoret. Comput. Sci."},{"issue":"10","key":"10.1016\/j.dam.2025.08.005_b12","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1119\/10.0006204","article-title":"Understanding and compensating for noise on IBM quantum computers","volume":"89","author":"Johnstun","year":"2021","journal-title":"Am. J. Phys."},{"issue":"2","key":"10.1016\/j.dam.2025.08.005_b13","doi-asserted-by":"crossref","DOI":"10.1088\/2058-9565\/abe519","article-title":"Demonstration of quantum volume 64 on a superconducting quantum computing system","volume":"6","author":"Jurcevic","year":"2021","journal-title":"Quantum Sci. Technol."},{"key":"10.1016\/j.dam.2025.08.005_b14","series-title":"WALCOM: Algorithms and Computation: 11th International Conference and Workshops","first-page":"448","article-title":"The time complexity of the token swapping problem and its parallel variants","author":"Kawahara","year":"2017"},{"key":"10.1016\/j.dam.2025.08.005_b15","series-title":"CNOT circuit extraction for topologically-constrained quantum memories","author":"Kissinger","year":"2019"},{"key":"10.1016\/j.dam.2025.08.005_b16","series-title":"The Art of Computer Programming. 3 Sorting and Searching","first-page":"736","author":"Knuth","year":"1973"},{"key":"10.1016\/j.dam.2025.08.005_b17","doi-asserted-by":"crossref","unstructured":"Gushu Li, Yufei Ding, Yuan Xie, 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, 2019, pp. 1001\u20131014.","DOI":"10.1145\/3297858.3304023"},{"key":"10.1016\/j.dam.2025.08.005_b18","series-title":"24th Annual European Symposium on Algorithms (ESA 2016)","first-page":"66:1","article-title":"Approximation and hardness of token swapping","author":"Miltzow","year":"2016"},{"key":"10.1016\/j.dam.2025.08.005_b19","series-title":"2022 55th IEEE\/ACM International Symposium on Microarchitecture","first-page":"1078","article-title":"Qubit mapping and routing via maxsat","author":"Molavi","year":"2022"},{"issue":"1","key":"10.1016\/j.dam.2025.08.005_b20","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1038\/s42005-021-00684-3","article-title":"Quantum compiling by deep reinforcement learning","volume":"4","author":"Moro","year":"2021","journal-title":"Commun. Phys."},{"issue":"1","key":"10.1016\/j.dam.2025.08.005_b21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3544563","article-title":"Optimal qubit assignment and routing via integer programming","volume":"4","author":"Nannicini","year":"2022","journal-title":"ACM Trans. Quantum Comput."},{"key":"10.1016\/j.dam.2025.08.005_b22","series-title":"Quantum Computation and Quantum Information","author":"Nielsen","year":"2010"},{"issue":"3","key":"10.1016\/j.dam.2025.08.005_b23","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0195-6698(13)80127-8","article-title":"Whitney numbers of the second kind for the star poset","volume":"11","author":"Portier","year":"1990","journal-title":"European J. Combin."},{"issue":"2","key":"10.1016\/j.dam.2025.08.005_b24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3520434","article-title":"Using reinforcement learning to perform qubit routing in quantum compilers","volume":"3","author":"Pozzi","year":"2022","journal-title":"ACM Trans. Quantum Comput."},{"key":"10.1016\/j.dam.2025.08.005_b25","series-title":"An open-source framework for quantum computing","author":"Qiskit","year":"2019"},{"key":"10.1016\/j.dam.2025.08.005_b26","first-page":"9935","article-title":"Qubit routing using graph neural network aided Monte Carlo tree search","volume":"vol. 36\/9","author":"Sinha","year":"2022"},{"key":"10.1016\/j.dam.2025.08.005_b27","doi-asserted-by":"crossref","unstructured":"Marcos\u00a0Yukio Siraichi, Vin\u00edcius Fernandes\u00a0dos Santos, Caroline Collange, Fernando Magno\u00a0Quint\u00e3o Pereira, Qubit allocation, in: Proceedings of the 2018 International Symposium on Code Generation and Optimization, 2018, pp. 113\u2013125.","DOI":"10.1145\/3168822"},{"issue":"1","key":"10.1016\/j.dam.2025.08.005_b28","doi-asserted-by":"crossref","DOI":"10.1088\/2058-9565\/ab8e92","article-title":"T\u2014 ket>: a retargetable compiler for NISQ devices","volume":"6","author":"Sivarajah","year":"2020","journal-title":"Quantum Sci. Technol."},{"key":"10.1016\/j.dam.2025.08.005_b29","first-page":"129","article-title":"Factoring a permutation on a broom","volume":"30","author":"Vaughan","year":"1999","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"10.1016\/j.dam.2025.08.005_b30","first-page":"1","article-title":"Improving quantum computation by optimized qubit routing","author":"Wagner","year":"2023","journal-title":"J. Optim. Theory Appl."},{"key":"10.1016\/j.dam.2025.08.005_b31","doi-asserted-by":"crossref","unstructured":"Robert Wille, Lukas Burgholzer, Alwin Zulehner, 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, 2019, pp. 1\u20136.","DOI":"10.1145\/3316781.3317859"},{"key":"10.1016\/j.dam.2025.08.005_b32","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.tcs.2015.01.052","article-title":"Swapping labeled tokens on graphs","volume":"586","author":"Yamanaka","year":"2015","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2025.08.005_b33","first-page":"1","article-title":"Swapping labeled tokens on complete split graphs","volume":"14","author":"Yasui","year":"2015","journal-title":"Inf. Process. Soc. Jpn. SIG Tech. Rep"},{"issue":"1","key":"10.1016\/j.dam.2025.08.005_b34","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1137\/S0895480197323159","article-title":"Optimal bounds for matching routing on trees","volume":"12","author":"Zhang","year":"1999","journal-title":"SIAM J. Discrete Math."},{"issue":"7","key":"10.1016\/j.dam.2025.08.005_b35","doi-asserted-by":"crossref","first-page":"1226","DOI":"10.1109\/TCAD.2018.2846658","article-title":"An efficient methodology for mapping quantum circuits to the IBM qx architectures","volume":"38","author":"Zulehner","year":"2018","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S0166218X25004482?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S0166218X25004482?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T12:52:20Z","timestamp":1772801540000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X25004482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":35,"alternative-id":["S0166218X25004482"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1016\/j.dam.2025.08.005","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Parallel token swapping for qubit routing","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1016\/j.dam.2025.08.005","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}