{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T02:04:13Z","timestamp":1780711453342,"version":"3.54.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62072259"],"award-info":[{"award-number":["62072259"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"publisher","award":["BK20221411"],"award-info":[{"award-number":["BK20221411"]}],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Suqian Science and Technology Foundation","award":["K202121"],"award-info":[{"award-number":["K202121"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"DOI":"10.1007\/s11128-022-03698-0","type":"journal-article","created":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T18:07:46Z","timestamp":1666894066000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The complexity of quantum circuit mapping with fixed parameters"],"prefix":"10.1007","volume":"21","author":[{"given":"Pengcheng","family":"Zhu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shenggen","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lihua","family":"Wei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xueyun","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhijin","family":"Guan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5110-3881","authenticated-orcid":false,"given":"Shiguang","family":"Feng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,10,27]]},"reference":[{"issue":"2153","key":"3698_CR1","doi-asserted-by":"publisher","first-page":"20120686","DOI":"10.1098\/rspa.2012.0686","volume":"469","author":"R Beals","year":"2013","unstructured":"Beals, R., Brierley, S., Gray, O., et al.: Efficient distributed quantum computing. Proc. R. Soc. A: Math. Phys. Eng. Sci. 469(2153), 20120686 (2013)","journal-title":"Proc. R. Soc. A: Math. Phys. Eng. Sci."},{"key":"3698_CR2","unstructured":"Botea, A., Kishimoto, A., Marinescu, R.: On the complexity of quantum circuit compilation. In: Eleventh Annual Symposium on Combinatorial Search (2018)"},{"issue":"10","key":"3698_CR3","doi-asserted-by":"publisher","first-page":"1040","DOI":"10.1038\/s41567-020-0948-z","volume":"16","author":"S Bravyi","year":"2020","unstructured":"Bravyi, S., Gosset, D., K\u00f6nig, R., et al.: Quantum advantage with noisy shallow circuits. Nat. Phys. 16(10), 1040\u20131045 (2020)","journal-title":"Nat. Phys."},{"issue":"13 &14","key":"3698_CR4","first-page":"1096","volume":"17","author":"S Brierley","year":"2017","unstructured":"Brierley, S.: Efficient implementation of quantum circuits with limited qubit interactions. Quantum Inf. Comput. 17(13 &14), 1096\u20131104 (2017)","journal-title":"Quantum Inf. Comput."},{"issue":"1","key":"3698_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00354-022-00163-5","volume":"40","author":"L Chhangte","year":"2022","unstructured":"Chhangte, L., Chakrabarty, A.: Mapping quantum circuits in IBM q devices using progressive qubit assignment for global ordering. New Gener. Comput. 40(1), 311\u2013338 (2022)","journal-title":"New Gener. Comput."},{"key":"3698_CR6","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), Leibniz International Proceedings in Informatics (LIPIcs), vol 135. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 3:1\u20133:24 (2019)"},{"key":"3698_CR7","volume-title":"Parameterized Complexity. Monographs in Computer Science","author":"R Downey","year":"2012","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (2012)"},{"key":"3698_CR8","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer (2006)"},{"key":"3698_CR9","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, Mathematical Sciences Series, W. H (1979)"},{"issue":"3","key":"3698_CR10","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"24","key":"3698_CR11","doi-asserted-by":"publisher","first-page":"6166","DOI":"10.1016\/j.disc.2007.11.040","volume":"308","author":"VS Gordon","year":"2008","unstructured":"Gordon, V.S., Orlovich, Y.L., Werner, F.: Hamiltonian properties of triangular grid graphs. Discret. Math. 308(24), 6166\u20136188 (2008)","journal-title":"Discret. Math."},{"key":"3698_CR12","unstructured":"Islam, K., Meijer, H., Rodr\u00edguez, Y.N., et\u00a0al.: Hamilton circuits in hexagonal grid graphs. In: CCCG, pp. 85\u201388 (2007)"},{"issue":"4","key":"3698_CR13","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676\u2013686 (1982)","journal-title":"SIAM J. Comput."},{"key":"3698_CR14","doi-asserted-by":"crossref","unstructured":"Li, G., Ding, Y., Xie, Y.: Tackling the qubit mapping problem for NISQ-era quantum devices. In: Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 1001\u20131014 (2019)","DOI":"10.1145\/3297858.3304023"},{"issue":"11","key":"3698_CR15","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1109\/TC.2020.3023247","volume":"70","author":"S Li","year":"2020","unstructured":"Li, S., Zhou, X., Feng, Y.: Qubit mapping based on subgraph isomorphism and filtered depth-limited search. IEEE Trans. Comput. 70(11), 1777\u20131788 (2020)","journal-title":"IEEE Trans. Comput."},{"key":"3698_CR16","doi-asserted-by":"crossref","unstructured":"Maslov, D., Falconer, S.M., Mosca, M.: Quantum circuit placement: Optimizing qubit-to-qubit interactions through mapping quantum circuits into a physical experiment. In: 44th Annual Design Automation Conference. Association for Computing Machinery, New York, DAC \u201907, pp. 962\u2013965 (2007)","DOI":"10.1145\/1278480.1278717"},{"key":"3698_CR17","unstructured":"Nation, P., Paik, H., Cross, A., et\u00a0al.: The IBM Quantum Heavy Hex Lattice. https:\/\/research.ibm.com\/blog\/heavy-hex-lattice. Accessed 07 July 2021 (2021)"},{"key":"3698_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2020.3026544","volume":"1","author":"S Niu","year":"2020","unstructured":"Niu, S., Suau, A., Staffelbach, G., et al.: A hardware-aware heuristic for the qubit mapping problem in the NISQ era. IEEE Trans. Quantum Eng. 1, 1\u201314 (2020)","journal-title":"IEEE Trans. Quantum Eng."},{"key":"3698_CR19","unstructured":"Polishchuk, V., Arkin, E., Mitchell, J.: Hamiltonian cycles in triangular grids. In: CCCG, pp. 63\u201366 (2006)"},{"key":"3698_CR20","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018). https:\/\/doi.org\/10.22331\/q-2018-08-06-79","journal-title":"Quantum"},{"key":"3698_CR21","doi-asserted-by":"crossref","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 1st edn. International Thomson Publishing (1996)","DOI":"10.1145\/230514.571645"},{"key":"3698_CR22","doi-asserted-by":"publisher","unstructured":"Siraichi, M.Y., Santos, V.F.d., Collange, S., et\u00a0al.: Qubit allocation. In: 2018 International Symposium on Code Generation and Optimization. Association for Computing Machinery, CGO, pp. 113\u2013125, New York, (2018) https:\/\/doi.org\/10.1145\/3168822","DOI":"10.1145\/3168822"},{"key":"3698_CR23","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/11537311_10","volume-title":"Fundamentals of Computation Theory","author":"T Tantau","year":"2005","unstructured":"Tantau, T.: Logspace optimization problems and their approximability properties. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) Fundamentals of Computation Theory, pp. 103\u2013114. Springer, Berlin, Heidelberg (2005)"},{"key":"3698_CR24","unstructured":"Vizing, V.G.: On an Estimate of the Chromatic Class of a p-Graph (in russian). discret analiz (1964)"},{"key":"3698_CR25","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: 2019 56th ACM\/IEEE Design Automation Conference (DAC), IEEE, pp. 1\u20136 (2019)","DOI":"10.1145\/3316781.3317859"},{"key":"3698_CR26","doi-asserted-by":"crossref","unstructured":"Zhou, X., Feng, Y., Li, S.: A monte Carlo tree search framework for quantum circuit transformation. In: 39th International Conference on Computer-Aided Design, pp. 1\u20137 (2020)","DOI":"10.1145\/3400302.3415621"},{"issue":"12","key":"3698_CR27","doi-asserted-by":"publisher","first-page":"4721","DOI":"10.1109\/TCAD.2020.2970594","volume":"39","author":"P Zhu","year":"2020","unstructured":"Zhu, P., Guan, Z., Cheng, X.: A dynamic look-ahead heuristic for the qubit mapping problem of NISQ computers. IEEE Transa. Comput.-Aided Des. Integr. Circuits Syst. 39(12), 4721\u20134735 (2020)","journal-title":"IEEE Transa. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"3698_CR28","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3112143","author":"P Zhu","year":"2021","unstructured":"Zhu, P., Feng, S., Guan, Z.: An iterated local search methodology for the qubit mapping problem. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. (2021). https:\/\/doi.org\/10.1109\/TCAD.2021.3112143","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"3698_CR29","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-319-59936-6_15","volume-title":"Reversible Computation","author":"A Zulehner","year":"2017","unstructured":"Zulehner, A., Gasser, S., Wille, R.: Exact global reordering for nearest neighbor quantum circuits using a*. In: Phillips, I., Rahaman, H. (eds.) Reversible Computation, pp. 185\u2013201. Springer International Publishing, Cham (2017)"},{"issue":"7","key":"3698_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":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-022-03698-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-022-03698-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-022-03698-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T12:24:13Z","timestamp":1667996653000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-022-03698-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":30,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["3698"],"URL":"https:\/\/doi.org\/10.1007\/s11128-022-03698-0","relation":{},"ISSN":["1573-1332"],"issn-type":[{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,27]]},"assertion":[{"value":"22 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"361"}}