{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T02:39:41Z","timestamp":1769308781747,"version":"3.49.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T00:00:00Z","timestamp":1748563200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS KAKENHI","award":["JP19K11814, JP20H05793, JP20H05795, JP20K11670, JP20K11692, JP21H03397, JP22H05001, JP23K10982, JP24H00686, and JP24H00690"],"award-info":[{"award-number":["JP19K11814, JP20H05793, JP20H05795, JP20K11670, JP20K11692, JP21H03397, JP22H05001, JP23K10982, JP24H00686, and JP24H00690"]}]},{"name":"JST ERATO","award":["JPMJER2301"],"award-info":[{"award-number":["JPMJER2301"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1)\u00a0We prove that the qubit routing problem is NP-hard. (2)\u00a0We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3)\u00a0We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.<\/jats:p>","DOI":"10.1145\/3722119","type":"journal-article","created":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T11:40:11Z","timestamp":1741434011000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithmic Theory of Qubit Routing in the Linear Nearest Neighbor Architectures"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9912-6898","authenticated-orcid":false,"given":"Takehiro","family":"Ito","sequence":"first","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Sendai, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3918-3479","authenticated-orcid":false,"given":"Naonori","family":"Kakimura","sequence":"additional","affiliation":[{"name":"Faculty of Science and Technology, Keio University, Yokohama, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7712-2730","authenticated-orcid":false,"given":"Naoyuki","family":"Kamiyama","sequence":"additional","affiliation":[{"name":"Institute of Mathematics for Industry, Kyushu University, Fukuoka, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9478-7307","authenticated-orcid":false,"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[{"name":"Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9826-7074","authenticated-orcid":false,"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics and Engineering, The University of Electro-Communications, Chofu, Japan"}]}],"member":"320","published-online":{"date-parts":[[2025,5,30]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2022.3"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-020-02776-5"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0387-0"},{"key":"e_1_3_3_5_2","first-page":"138","volume-title":"Proceedings of the 11th International Symposium on Combinatorial Search (SOCS\u201918)","author":"Botea Adi","year":"2018","unstructured":"Adi Botea, Akihiro Kishimoto, and Radu Marinescu. 2018. On the complexity of quantum circuit compilation. In Proceedings of the 11th International Symposium on Combinatorial Search (SOCS\u201918), Vadim Bulitko and Sabine Storandt (Eds.). AAAI Press, 138\u2013142."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00483"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304023"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2016.66"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3544563"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-010-0201-2"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3168822"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360546"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-020-02630-8"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.01.052"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3722119","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3722119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:43:50Z","timestamp":1750272230000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3722119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,30]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3722119"],"URL":"https:\/\/doi.org\/10.1145\/3722119","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,30]]},"assertion":[{"value":"2023-10-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}