{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T03:45:14Z","timestamp":1778643914792,"version":"3.51.4"},"reference-count":39,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2023,11,1]]},"DOI":"10.1587\/transfun.2022eap1159","type":"journal-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T22:11:59Z","timestamp":1684275119000},"page":"1424-1431","source":"Crossref","is-referenced-by-count":15,"title":["A SAT Approach to the Initial Mapping Problem in SWAP Gate Insertion for Commuting Gates"],"prefix":"10.1587","volume":"E106.A","author":[{"given":"Atsushi","family":"MATSUO","sequence":"first","affiliation":[{"name":"IBM Quantum, IBM Research - Tokyo"},{"name":"Ritsumeikan University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigeru","family":"YAMASHITA","sequence":"additional","affiliation":[{"name":"Ritsumeikan University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"J. EGGER","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM Research - Z\u00fcrich R\u00fcschlikon"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] P. Shor, \u201cAlgorithms for quantum computation: Discrete logarithms and factoring,\u201d Proc. 35th Annual Symposium on Foundations of Computer Science, pp.124-134, 1994. 10.1109\/sfcs.1994.365700"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] N. Moll, P. Barkoutsos, L.S. Bishop, J.M. Chow, A. Cross, D.J. Egger, S. Filipp, A. Fuhrer, J.M. Gambetta, M. Ganzhorn, A. Kandala, A. Mezzacapo, P. M\u00fcller, W. Riess, G. Salis, J. Smolin, I. Tavernelli, and K. Temme, \u201cQuantum optimization using variational algorithms on near-term quantum devices,\u201d Quantum Sci. Technol., vol.3, no.3, p.030503, 2018. 10.1088\/2058-9565\/aab822","DOI":"10.1088\/2058-9565\/aab822"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] M.P. Harrigan, K.J. Sung, M. Neeley, K.J. Satzinger, F. Arute, K. Arya, J. Atalaya, J.C. Bardin, R. Barends, S. Boixo, M. Broughton, B.B. Buckley, D.A. Buell, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, S. Demura, A. Dunsworth, D. Eppens, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, S. Habegger, A. Ho, S. Hong, T. Huang, L.B. Ioffe, S.V. Isakov, E. Jeffrey, Z. Jiang, C. Jones, D. Kafri, K. Kechedzhi, J. Kelly, S. Kim, P.V. Klimov, A.N. Korotkov, F. Kostritsa, D. Landhuis, P. Laptev, M. Lindmark, M. Leib, O. Martin, J.M. Martinis, J.R. McClean, M. McEwen, A. Megrant, X. Mi, M. Mohseni, W. Mruczkiewicz, J. Mutus, O. Naaman, C. Neill, F. Neukart, M.Y. Niu, T.E. O&apos;Brien, B. O&apos;Gorman, E. Ostby, A. Petukhov, H. Putterman, C. Quintana, P. Roushan, N.C. Rubin, D. Sank, A. Skolik, V. Smelyanskiy, D. Strain, M. Streif, M. Szalay, A. Vainsencher, T. White, Z.J. Yao, P. Yeh, A. Zalcman, L. Zhou, H. Neven, D. Bacon, E. Lucero, E. Farhi, and R. Babbush, \u201cQuantum approximate optimization of non-planar graph problems on a planar superconducting processor,\u201d Nat. Phys., vol.17, no.3, pp.332-336, 2021. 10.1038\/s41567-020-01105-y","DOI":"10.1038\/s41567-020-01105-y"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] C. Chamberland, G. Zhu, T.J. Yoder, J.B. Hertzberg, and A.W. Cross, \u201cTopological and subsystem codes on low-degree graphs with flag qubits,\u201d Phys. Rev. X, vol.10, no.1, p.011022, 2020. 10.1103\/physrevx.10.011022","DOI":"10.1103\/PhysRevX.10.011022"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] K. Iwama, Y. Kambayashi, and S. Yamashita, \u201cTransformation rules for designing CNOT-based quantum circuits,\u201d Proc. 39th Annual Design Automation Conference, DAC&apos;02, New York, NY, USA, pp.419-424, Association for Computing Machinery, 2002. 10.1145\/513918.514026","DOI":"10.1145\/513918.514026"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] M.Y. Siraichi, V.F. dos Santos, C. Collange, and F.M.Q. Pereira, \u201cQubit allocation,\u201d Proc. 2018 International Symposium on Code Generation and Optimization, CGO 2018, New York, NY, USA, p.113-125, Association for Computing Machinery, 2018. 10.1145\/3179541.3168822","DOI":"10.1145\/3179541.3168822"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] S.S. Tannu and M.K. Qureshi, \u201cNot all qubits are created equal: A case for variability-aware policies for NISQ-era quantum computers,\u201d Proc. 24th Int. Conf. on Architectural Support for Program. Languages and Oper. Syst. (ASPLOS), New York, NY, USA, pp.987-999, Association for Computing Machinery, 2019. 10.1145\/3297858.3304007","DOI":"10.1145\/3297858.3304007"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] A.C. Vazquez, D.J. Egger, D. Ochsner, and S. Woerner, \u201cWell-conditioned multi-product formulas for hardware-friendly hamiltonian simulation,\u201d Quantum, vol.7, p.1067, 2023.","DOI":"10.22331\/q-2023-07-25-1067"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] A. Lye, R. Wille, and R. Drechsler, \u201cDetermining the minimal number of SWAP gates for multi-dimensional nearest neighbor quantum circuits,\u201d The 20th Asia and South Pacific Design Automation Conference, pp.178-183, 2015. 10.1109\/aspdac.2015.7059001","DOI":"10.1109\/ASPDAC.2015.7059001"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] P. Murali, A. Javadi-Abhari, F.T. Chong, and M. Martonosi, \u201cFormal constraint-based compilation for noisy intermediate-scale quantum systems,\u201d Microprocess. and Microsys., vol.66, pp.102-112, 2019. 10.1016\/j.micpro.2019.02.005","DOI":"10.1016\/j.micpro.2019.02.005"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] A. Kole, K. Datta, and I. Sengupta, \u201cA heuristic for linear nearest neighbor realization of quantum circuits by SWAP gate insertion using <i>N<\/i>-gate lookahead,\u201d IEEE Trans. Emerg. Sel. Topics Circuits Syst., vol.6, no.1, pp.62-72, 2016. 10.1109\/jetcas.2016.2528720","DOI":"10.1109\/JETCAS.2016.2528720"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] A. Bhattacharjee, C. Bandyopadhyay, R. Wille, R. Drechsler, and H. Rahaman, \u201cA novel approach for nearest neighbor realization of 2D quantum circuits,\u201d 2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pp.305-310, 2018. 10.1109\/isvlsi.2018.00063","DOI":"10.1109\/ISVLSI.2018.00063"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] G. Li, Y. Ding, and Y. Xie, \u201cTackling the qubit mapping problem for NISQ-era quantum devices,\u201d Proc. 24th Int. Conf. on Architectural Support for Program. Languages and Oper. Syst. (ASPLOS), New York, NY, USA, pp.1001-1014, Association for Computing Machinery, 2019. 10.1145\/3297858.3304023","DOI":"10.1145\/3297858.3304023"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] T. Itoko, R. Raymond, T. Imamichi, and A. Matsuo, \u201cOptimization of quantum circuit mapping using gate transformation and commutation,\u201d Integration, vol.70, pp.43-50, 2020. 10.1016\/j.vlsi.2019.10.004","DOI":"10.1016\/j.vlsi.2019.10.004"},{"key":"15","unstructured":"[15] M.S. Anis, A. Mitchell, H. Abraham, A. Offei, R. Agarwal, G. Agliardi, et al., \u201cQiskit: An open-source framework for quantum computing,\u201d 2021."},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan, \u201ct|ket&gt;: A retargetable compiler for NISQ devices,\u201d Quantum Sci. Technol., vol.6, no.1, p.014003, 2020. 10.1088\/2058-9565\/ab8e92","DOI":"10.1088\/2058-9565\/ab8e92"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] T. Alexander, N. Kanazawa, D.J. Egger, L. Capelluto, C.J. Wood, A. Javadi-Abhari, and D.C. McKay, \u201cQiskit pulse: Programming quantum computers through the cloud with pulses,\u201d Quantum Sci. Technol., vol.5, no.4, p.044006, 2020. 10.1088\/2058-9565\/aba404","DOI":"10.1088\/2058-9565\/aba404"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] N. Earnest, C. Tornow, and D.J. Egger, \u201cPulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware,\u201d Phys. Rev. Research, vol.3, no.4, p.043088, 2021. 10.1103\/physrevresearch.3.043088","DOI":"10.1103\/PhysRevResearch.3.043088"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] D. Maslov, S.M. Falconer, and M. Mosca, \u201cQuantum circuit placement,\u201d IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol.27, no.4, pp.752-763, 2008. 10.1109\/tcad.2008.917562","DOI":"10.1109\/TCAD.2008.917562"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] M. Alam, A. Ash-Saki, and S. Ghosh, \u201cCircuit compilation methodologies for quantum approximate optimization algorithm,\u201d 53rd Annual IEEE\/ACM Int. Symp. on Microarch. (MICRO), pp.215-228, 2020. 10.1109\/micro50266.2020.00029","DOI":"10.1109\/MICRO50266.2020.00029"},{"key":"21","unstructured":"[21] E. Farhi, J. Goldstone, and S. Gutmann, \u201cA quantum approximate optimization algorithm,\u201d 2014."},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] L. Lao and D.E. Browne, \u201c2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms,\u201d Proc. 49th Annual Int. Symp. Comput. Architecture, ISCA&apos;22, New York, NY, USA, p.351-365, Association for Computing Machinery, 2022.","DOI":"10.1145\/3470496.3527394"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[23] J. Weidenfeller, L.C. Valor, J. Gacon, C. Tornow, L. Bello, S. Woerner, and D.J. Egger, \u201cScaling of the quantum approximate optimization algorithm on superconducting qubit based hardware,\u201d Quantum, vol.6, p.870, 2022. 10.22331\/q-2022-12-07-870","DOI":"10.22331\/q-2022-12-07-870"},{"key":"24","unstructured":"[24] J. Gambetta, \u201cExpanding the IBM Quantum roadmap to anticipate the future of quantum-centric supercomputing,\u201d 2022."},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] L. Cordella, P. Foggia, C. Sansone, and M. Vento, \u201cA (sub)graph isomorphism algorithm for matching large graphs,\u201d IEEE Trans. Pattern Anal. Mach. Intell., vol.26, no.10, pp.1367-1372, 2004. 10.1109\/tpami.2004.75","DOI":"10.1109\/TPAMI.2004.75"},{"key":"26","doi-asserted-by":"publisher","unstructured":"[26] J. Koch, T.M. Yu, J. Gambetta, A.A. Houck, D.I. Schuster, J. Majer, A. Blais, M.H. Devoret, S.M. Girvin, and R.J. Schoelkopf, \u201cCharge-insensitive qubit design derived from the cooper pair box,\u201d Phys. Rev. A, vol.76, no.4, p.042319, 2007. 10.1103\/physreva.76.042319","DOI":"10.1103\/PhysRevA.76.042319"},{"key":"27","doi-asserted-by":"publisher","unstructured":"[27] S. Sheldon, E. Magesan, J.M. Chow, and J.M. Gambetta, \u201cProcedure for systematically tuning up cross-talk in the cross-resonance gate,\u201d Phys. Rev. A, vol.93, no.6, p.060302, 2016. 10.1103\/physreva.93.060302","DOI":"10.1103\/PhysRevA.93.060302"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] J. Tor\u00e1n, \u201cOn the resolution complexity of graph non-isomorphism,\u201d Theory and Applications of Satisfiability Testing-SAT 2013, M. J\u00e4rvisalo and A. Van Gelder, eds., Berlin, Heidelberg, pp.52-66, Springer Berlin Heidelberg, 2013. 10.1007\/978-3-642-39071-5_6","DOI":"10.1007\/978-3-642-39071-5_6"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] T. Balyo, N. Froleyks, M. Heule, M. Iser, M. J\u00e4rvisalo, and M. Suda, \u201cProceedings of SAT Competition 2021: Solver and Benchmark Descriptions,\u201d 2021.","DOI":"10.1016\/j.artint.2021.103572"},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] A. Ignatiev, A. Morgado, and J. Marques-Silva, \u201cPySAT: A Python toolkit for prototyping with SAT oracles,\u201d SAT, pp.428-437, 2018. 10.1007\/978-3-319-94144-8_26","DOI":"10.1007\/978-3-319-94144-8_26"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[31] W. Hattori and S. Yamashita, \u201cQuantum circuit optimization by changing the gate order for 2D nearest neighbor architectures,\u201d Reversible Computation, J. Kari and I. Ulidowski, eds., pp.228-243, Springer International Publishing, Cham, 2018. 10.1007\/978-3-319-99498-7_16","DOI":"10.1007\/978-3-319-99498-7_16"},{"key":"32","doi-asserted-by":"crossref","unstructured":"[32] A. Matsuo, W. Hattori, and S. Yamashita, \u201cReducing the overhead of mapping quantum circuits to IBM Q system,\u201d IEEE Int. Symp. Circuits Syst. (ISCAS), pp.1-5, 2019. 10.1109\/iscas.2019.8702439","DOI":"10.1109\/ISCAS.2019.8702439"},{"key":"33","unstructured":"[33] I.P. Gent and T. Walsh, \u201cThe SAT phase transition,\u201d Proc. 11th European Conference on Artificial Intelligence, ECAI&apos;94, USA, pp.105-109, John Wiley &amp; Sons, 1994."},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] C. McCreesh, P. Prosser, C. Solnon, and J. Trimble, \u201cWhen subgraph isomorphism is really hard, and why this matters for graph databases,\u201d J. Artif. Int. Res., vol.61, no.1, p.723-759, 2018. 10.1613\/jair.5768","DOI":"10.1613\/jair.5768"},{"key":"35","doi-asserted-by":"publisher","unstructured":"[35] S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, \u201cObstacles to variational quantum optimization from symmetry protection,\u201d Phys. Rev. Lett., vol.125, no.26, p.260505, 2020. 10.1103\/physrevlett.125.260505","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"36","doi-asserted-by":"publisher","unstructured":"[36] L. Zhou, S.T. Wang, S. Choi, H. Pichler, and M.D. Lukin, \u201cQuantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices,\u201d Phys. Rev. X, vol.10, no.2, p.021067, 2020. 10.1103\/physrevx.10.021067","DOI":"10.1103\/PhysRevX.10.021067"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] J. Shi and J. Malik, \u201cNormalized cuts and image segmentation,\u201d IEEE Trans. Pattern Anal. Mach. Intell., vol.22, no.8, pp.888-905, 2000. 10.1109\/34.868688","DOI":"10.1109\/34.868688"},{"key":"38","unstructured":"[38] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and \u00c9. Duchesnay, \u201cScikit-learn: Machine learning in Python,\u201d Journal of Machine Learning Research, vol.12, no.85, pp.2825-2830, 2011."},{"key":"39","doi-asserted-by":"publisher","unstructured":"[39] D.S. Fran\u00e7a and R. Garc\u00eda-Patr\u00f3n, \u201cLimitations of optimization algorithms on noisy quantum devices,\u201d Nat. Phys., vol.17, no.11, pp.1221-1227, 2021. 10.1038\/s41567-021-01356-3","DOI":"10.1038\/s41567-021-01356-3"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E106.A\/11\/E106.A_2022EAP1159\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T04:55:52Z","timestamp":1715576152000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E106.A\/11\/E106.A_2022EAP1159\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,1]]},"references-count":39,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2022eap1159","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,1]]},"article-number":"2022EAP1159"}}