{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:48:26Z","timestamp":1780674506986,"version":"3.54.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T00:00:00Z","timestamp":1683158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T00:00:00Z","timestamp":1683158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100020639","name":"Bayerische Staatsministerium fur Wirtschaft, Landesentwicklung und Energie","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100020639","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100018808","name":"ADA Lovelace Center for Analytics, Data, Applications","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100018808","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Bayerische Staatsregierung"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021,<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/arxiv.org\/abs\/2106.06446\">http:\/\/arxiv.org\/abs\/2106.06446<\/jats:ext-link>), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods.<\/jats:p>","DOI":"10.1007\/s10957-023-02229-w","type":"journal-article","created":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T19:01:59Z","timestamp":1683226919000},"page":"1161-1194","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Improving Quantum Computation by Optimized Qubit Routing"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9031-1870","authenticated-orcid":false,"given":"Friedrich","family":"Wagner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"B\u00e4rmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frauke","family":"Liers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Markus","family":"Weissenb\u00e4ck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,5,4]]},"reference":[{"key":"2229_CR1","doi-asserted-by":"publisher","unstructured":"Childs, A.M., Schoute, E., Unsal, C.M.: Circuit transformations for quantum architectures. In: van Dam, W., Mancinska, L. (eds.), 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pp 3:1\u20133:24, Dagstuhl, Germany, 2019. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10395, https:\/\/doi.org\/10.4230\/LIPIcs.TQC.2019.3","DOI":"10.4230\/LIPIcs.TQC.2019.3"},{"key":"2229_CR2","doi-asserted-by":"publisher","unstructured":"Cirq. https:\/\/quantumai.google\/cirq, (2021). https:\/\/doi.org\/10.5281\/zenodo.5182845","DOI":"10.5281\/zenodo.5182845"},{"key":"2229_CR3","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: An improved algorithm for matching large graphs. In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen. pp 149\u2013159. (2001)"},{"key":"2229_CR4","doi-asserted-by":"publisher","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367\u20131372 . https:\/\/doi.org\/10.1109\/TPAMI.2004.75","DOI":"10.1109\/TPAMI.2004.75"},{"key":"2229_CR5","doi-asserted-by":"publisher","unstructured":"Cowtan, A., Dilkes, S., Duncan, R., Krajenbrink, A., Simmons, W., Sivarajah, S.: On the qubit routing problem. In: van Dam, W., Mancinska, L. (eds.),14thConference on the Theory of Quantum Computation, Communication and Cryptography (TQC2019),volume 135 of Leibniz International Proceedings in Informatics(LIPIcs), pp 5:1\u20135:32, Dagstuhl, Germany, 2019. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. URL: http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10397, https:\/\/doi.org\/10.4230\/LIPIcs.TQC.2019.5","DOI":"10.4230\/LIPIcs.TQC.2019.5"},{"key":"2229_CR6","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.100.032328","volume":"100","author":"AW Cross","year":"2019","unstructured":"Cross, A.W., Bishop, L.S., Sheldon, S., Nation, P.D., Gambetta, J.M.: Validating quantum computers using randomized model circuits. Phys. Revue A 100, 032328 (2019). https:\/\/doi.org\/10.1103\/PhysRevA.100.032328","journal-title":"Phys. Revue A"},{"key":"2229_CR7","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm, (2014). arXiv:1411.4028"},{"key":"2229_CR8","unstructured":"Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, (2022). https:\/\/www.gurobi.com"},{"key":"2229_CR9","doi-asserted-by":"crossref","unstructured":"Hagberg, A.A., Schult, D.A., Swart, P.J.: Exploring network structure, dynamics, and function using networkx. In: Varoquaux, G., Vaught, T., Millman, J. (eds.), Proceedings of the 7th Python in Science Conference, pp 11\u201315, Pasadena, CA USA, 2008. http:\/\/conference.scipy.org\/proceedings\/SciPy2008\/paper_2\/","DOI":"10.25080\/TCWV9851"},{"key":"2229_CR10","unstructured":"IBM Quantum (2021). https:\/\/quantum-computing.ibm.com\/"},{"issue":"10","key":"2229_CR11","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1119\/10.0006204","volume":"89","author":"S Johnstun","year":"2021","unstructured":"Johnstun, S., Van Huele, J.-F.: Understanding and compensating for noise on IBM quantum computers. Am. J. Phys. 89(10), 935\u2013942 (2021). https:\/\/doi.org\/10.1119\/10.0006204","journal-title":"Am. J. Phys."},{"key":"2229_CR12","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.cosrev.2016.09.003","volume":"22","author":"D Kim","year":"2016","unstructured":"Kim, D.: Sorting on graphs by adjacent swaps using permutation groups. Comput. Sci. Rev. 22, 89\u2013105 (2016). https:\/\/doi.org\/10.1016\/j.cosrev.2016.09.003","journal-title":"Comput. Sci. Rev."},{"issue":"7\/8","key":"2229_CR13","first-page":"581","volume":"20","author":"A Kissinger","year":"2020","unstructured":"Kissinger, A., Griend, A.M.-V.D.: CNOT circuit extraction for topologically-constrained quantum memories. Quantum Inf. Comput. 20(7\/8), 581\u2013596 (2020)","journal-title":"Quantum Inf. Comput."},{"key":"2229_CR14","doi-asserted-by":"publisher","unstructured":"Li, G., Ding, Y., Xie, Y.: 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, page 1001-1014, New York, NY, USA, 2019. Association for Computing Machinery. https:\/\/doi.org\/10.1145\/3297858.3304023","DOI":"10.1145\/3297858.3304023"},{"key":"2229_CR15","doi-asserted-by":"publisher","unstructured":"Miltzow, T., Narins, L., Okamoto, Y., Rote, G., Thomas, A., Uno, T.: Approximation and Hardness of Token Swapping. In: Sankowski, P., Zaroliagis, C. (eds.), 24th Annual European Symposium on Algorithms (ESA 2016), volume\u00a057 of Leibniz International Proceedings in Informatics (LIPIcs), pp 66:1\u201366:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/6408, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.66","DOI":"10.4230\/LIPIcs.ESA.2016.66"},{"issue":"3","key":"2229_CR16","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aab822","volume":"3","author":"N Moll","year":"2018","unstructured":"Moll, N., Barkoutsos, P., Bishop, L.S., Chow, J.M., Cross, A., Egger, D.J., Filipp, S., Fuhrer, A., Gambetta, J.M., Ganzhorn, M., Kandala, A., Mezzacapo, A., M\u00fcller, P., Riess, W., Salis, G., Smolin, J., Tavernelli, I., Temme, K.: Quantum optimization using variational algorithms on near-term quantum devices. Quantum Sci. Technol. 3(3), 030503 (2018). https:\/\/doi.org\/10.1088\/2058-9565\/aab822","journal-title":"Quantum Sci. Technol."},{"issue":"1","key":"2229_CR17","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1038\/s42005-021-00684-3","volume":"4","author":"L Moro","year":"2021","unstructured":"Moro, L., Paris, M.G.A., Restelli, M., Prati, E.: Quantum compiling by deep reinforcement learning. Commun. Phys. 4(1), 178 (2021). https:\/\/doi.org\/10.1038\/s42005-021-00684-3","journal-title":"Commun. Phys."},{"key":"2229_CR18","doi-asserted-by":"crossref","unstructured":"Nannicini, G., Bishop, L.S. G\u00fcnl\u00fck, O., Jurcevic, P.: Optimal qubit assignment and routing via integer programming, (2021). arXiv:2106.06446","DOI":"10.1145\/3544563"},{"key":"2229_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667","volume-title":"Quantum Computation and Quantum Information: 10th Anniversary Edition","author":"MA Nielsen","year":"2010","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press (2010). https:\/\/doi.org\/10.1017\/CBO9780511976667"},{"key":"2229_CR20","doi-asserted-by":"publisher","unstructured":"Qiskit. An open-source framework for quantum computing (2021). http:\/\/www.qiskit.org. https:\/\/doi.org\/10.5281\/zenodo.2573505","DOI":"10.5281\/zenodo.2573505"},{"key":"2229_CR21","doi-asserted-by":"publisher","DOI":"10.1145\/3360546","author":"MY Siraichi","year":"2019","unstructured":"Siraichi, M.Y., Santos, VFd., Collange, C., Pereira, F.MQa.: Qubit allocation as a combination of subgraph isomorphism and token swapping. ACM Program Lang. Proc. (2019). https:\/\/doi.org\/10.1145\/3360546","journal-title":"ACM Program Lang. Proc."},{"key":"2229_CR22","doi-asserted-by":"publisher","unstructured":"Siraichi, M.Y., Santos, V.F.d., Collange, C., Quint\u00e3o\u00a0Pereira, F.M.: Qubit allocation. In: CGO 2018 - International Symposium on Code Generation and Optimization, pp 1\u201312, Vienna, Austria, Feb 2018. https:\/\/hal.archives-ouvertes.fr\/hal-01655951, https:\/\/doi.org\/10.1145\/3168822","DOI":"10.1145\/3168822"},{"issue":"1","key":"2229_CR23","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8e92","volume":"6","author":"S Sivarajah","year":"2020","unstructured":"Sivarajah, S., Dilkes, S., Cowtan, A., Simmons, W., Edgington, A., Duncan, R.: t$$\\vert $$ket$$\\rangle $$: a retargetable compiler for NISQ devices. Quantum Sci. Technol. 6(1), 014003 (2020). https:\/\/doi.org\/10.1088\/2058-9565\/ab8e92","journal-title":"Quantum Sci. Technol."},{"issue":"9","key":"2229_CR24","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1109\/TC.2020.3009140","volume":"70","author":"B Tan","year":"2021","unstructured":"Tan, B., Cong, J.: Optimality study of existing quantum computing layout synthesis tools. IEEE Trans. Comput. 70(9), 1363\u20131373 (2021). https:\/\/doi.org\/10.1109\/TC.2020.3009140","journal-title":"IEEE Trans. Comput."},{"key":"2229_CR25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.97.022304","volume":"97","author":"Z Wang","year":"2017","unstructured":"Wang, Z., Hadfield, S., Jiang, Z., Rieffel, E.: The quantum approximation optimization algorithm for MaxCut: a fermionic view. Phys. Rev. A 97, 022304 (2017). https:\/\/doi.org\/10.1103\/PhysRevA.97.022304","journal-title":"Phys. Rev. A"},{"key":"2229_CR26","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/3-540-27477-4","volume-title":"Complexity Theory: Exploring the Limits of Efficient Algorithms","author":"I Wegener","year":"2005","unstructured":"Wegener, I.: Complexity Theory: Exploring the Limits of Efficient Algorithms, p. 81. Springer, Berlin (2005). https:\/\/doi.org\/10.1007\/3-540-27477-4"},{"key":"2229_CR27","doi-asserted-by":"crossref","unstructured":"Wille, R., Burgholzer, L., Zulehner, A.: Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations. In: Design Automation Conference, (2019)","DOI":"10.1145\/3316781.3317859"},{"key":"2229_CR28","doi-asserted-by":"publisher","unstructured":"Yamanaka, K., Demaine, E.D., Ito, T., Kawahara, J., Kiyomi, M., Okamoto, Y., Saitoh, T., Suzuki, A., Uchizawa, K., Uno, T.: Swapping labeled tokens on graphs. In: Theoretical Computer Science, 586:81\u201394, 2015. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397515001656, https:\/\/doi.org\/10.1016\/j.tcs.2015.01.052","DOI":"10.1016\/j.tcs.2015.01.052"},{"key":"2229_CR29","unstructured":"Yasui, G., Abe, K., Yamanaka, K., Hirayama, T.: Swapping labeled tokens on complete split graphs. In: IPSJ SIG Technical Report, 14 (2015)"},{"issue":"7","key":"2229_CR30","doi-asserted-by":"publisher","first-page":"1226","DOI":"10.1109\/TCAD.2018.2846658","volume":"38","author":"A Zulehner","year":"2019","unstructured":"Zulehner, A., Paler, A., Wille, R.: An efficient methodology for mapping quantum circuits to the IBM-QX architectures. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 38(7), 1226\u20131236 (2019). https:\/\/doi.org\/10.1109\/TCAD.2018.2846658","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02229-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-023-02229-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02229-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T20:35:16Z","timestamp":1729370116000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-023-02229-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,4]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["2229"],"URL":"https:\/\/doi.org\/10.1007\/s10957-023-02229-w","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,4]]},"assertion":[{"value":"3 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}