{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T02:18:34Z","timestamp":1769307514161,"version":"3.49.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,8,17]],"date-time":"2023-08-17T00:00:00Z","timestamp":1692230400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,17]],"date-time":"2023-08-17T00:00:00Z","timestamp":1692230400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-106263RB-I00"],"award-info":[{"award-number":["PID2019-106263RB-I00"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-106263RB-I00"],"award-info":[{"award-number":["PID2019-106263RB-I00"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-106263RB-I00"],"award-info":[{"award-number":["PID2019-106263RB-I00"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000844","name":"European Space Agency","doi-asserted-by":"publisher","award":["4000112300\/14\/D\/MRP Mars Express Data Planning Tool MEXAR2 Maintenance"],"award-info":[{"award-number":["4000112300\/14\/D\/MRP Mars Express Data Planning Tool MEXAR2 Maintenance"]}],"id":[{"id":"10.13039\/501100000844","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000844","name":"European Space Agency","doi-asserted-by":"publisher","award":["4000112300\/14\/D\/MRP Mars Express Data Planning Tool MEXAR2 Maintenance"],"award-info":[{"award-number":["4000112300\/14\/D\/MRP Mars Express Data Planning Tool MEXAR2 Maintenance"]}],"id":[{"id":"10.13039\/501100000844","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006382","name":"Universidad de Oviedo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006382","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed <jats:inline-formula><jats:alternatives><jats:tex-math>$$GA_{VX}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:msub>\n                      <mml:mi>A<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>VX<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, outperforms previous approaches in the literature.<\/jats:p>","DOI":"10.1007\/s11047-023-09955-0","type":"journal-article","created":{"date-parts":[[2023,8,17]],"date-time":"2023-08-17T16:02:21Z","timestamp":1692288141000},"page":"631-644","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Solving quantum circuit compilation problem variants through genetic algorithms"],"prefix":"10.1007","volume":"22","author":[{"given":"Lis","family":"Arufe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Rasconi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Oddi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramiro","family":"Varela","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel \u00c1ngel","family":"Gonz\u00e1lez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,17]]},"reference":[{"key":"9955_CR1","unstructured":"Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S, Regev O (2004) Adiabatic quantum computation is equivalent to standard quantum computation"},{"key":"9955_CR2","doi-asserted-by":"crossref","unstructured":"Alam M, Ash-Saki A, Ghosh S (2020) Circuit compilation methodologies for quantum approximate optimization algorithm. In: 2020 53rd annual IEEE\/ACM international symposium on microarchitecture (MICRO), pp 215\u2013228","DOI":"10.1109\/MICRO50266.2020.00029"},{"key":"9955_CR3","doi-asserted-by":"crossref","unstructured":"Aruf, L, Gonz\u00e1lez MA, Oddi A, Rasconi R, Varela R (2022) Quantum circuit compilation by genetic algorithm for quantum approximate optimization algorithm applied to maxcut problem. Swarm Evol Comput 101030","DOI":"10.1016\/j.swevo.2022.101030"},{"key":"9955_CR4","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-031-06527-9_9","volume-title":"Bio-inspired systems and applications: from robotics to ambient intelligence","author":"L Arufe","year":"2022","unstructured":"Arufe L, Rasconi R, Oddi A, Varela R, Gonz\u00e1lez M\u00c1 (2022) Compiling single round qccp-x quantum circuits by genetic algorithm. In: Ferr\u00e1ndez Vicente JM, \u00c1lvarez-S\u00e1nchez JR, de la Paz L\u00f3pez F, Adeli H (eds) Bio-inspired systems and applications: from robotics to ambient intelligence. Springer, Cham, pp 88\u201397"},{"key":"9955_CR5","doi-asserted-by":"crossref","unstructured":"Booth KE, Do M, Beck JC, Rieffel E, Venturelli D, Frank J (2018) Comparing and integrating constraint programming and temporal planning for quantum circuit compilation. In: Twenty-eighth international conference on automated planning and scheduling (ICAPS 2018), pp 366\u2013374","DOI":"10.1609\/icaps.v28i1.13920"},{"key":"9955_CR6","doi-asserted-by":"crossref","unstructured":"Chand S, Singh HK, Ray T, Ryan M (2019) Rollout based heuristics for the quantum circuit compilation problem. In: 2019 IEEE Congress on Evolutionary Computation (CEC), pp 974\u2013981","DOI":"10.1109\/CEC.2019.8790000"},{"key":"9955_CR7","unstructured":"Do M, Wang Z, O\u2019Gorman B, Venturelli D, Rieffel E, Frank J (2020) Planning for compilation of a quantum algorithm for graph coloring"},{"key":"9955_CR8","unstructured":"Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm"},{"key":"9955_CR9","doi-asserted-by":"crossref","unstructured":"Li G, Ding Y, Xie Y (2019) 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. Association for Computing Machinery, New York, NY, USA, pp 1001\u20131014","DOI":"10.1145\/3297858.3304023"},{"key":"9955_CR10","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-319-93031-2_32","volume-title":"CPAIOR 2018: integration of constraint programming, artificial intelligence, and operations research","author":"A Oddi","year":"2018","unstructured":"Oddi A, Rasconi R (2018) Greedy randomized search for scalable compilation of quantum circuits. In: van Hoeve W-J (ed) CPAIOR 2018: integration of constraint programming, artificial intelligence, and operations research. Springer, Cham, pp 446\u2013461"},{"key":"9955_CR11","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 (2018) Quantum Computing in the NISQ era and beyond. Quantum 2:79","journal-title":"Quantum"},{"key":"9955_CR12","doi-asserted-by":"crossref","unstructured":"Rasconi R, Oddi A (2019) An innovative genetic algorithm for the quantum circuit compilation problem. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, vol. 33, pp. 7707\u20137714","DOI":"10.1609\/aaai.v33i01.33017707"},{"key":"9955_CR13","doi-asserted-by":"crossref","unstructured":"Sete EA, Zeng WJ, Rigetti CT (2016) A functional architecture for scalable quantum computing. In: 2016 IEEE international conference on rebooting computing (ICRC). IEEE, pp 1\u20136","DOI":"10.1109\/ICRC.2016.7738703"},{"key":"9955_CR14","unstructured":"Venturelli D, Do M, O\u2019Gorman B, Frank J, Rieffel E, Booth KE, Nguyen T, Narayan P, Nanda S (2019) Quantum circuit compilation: an emerging application for automated reasoning. In: Bernardini S, Talamadupula K, Yorke-Smith N (eds) Proceedings of the 12th international scheduling and planning applications workshop (SPARK 2019), pp 95\u2013103"},{"key":"9955_CR15","doi-asserted-by":"crossref","unstructured":"Venturelli D, Do M, Rieffel EG, Frank J (2017) Temporal planning for compilation of quantum approximate optimization circuits. In: Proceedings of the twenty-sixth international joint conference on artificial intelligence (IJCAI 2017), pp 4440\u20134446","DOI":"10.24963\/ijcai.2017\/620"},{"key":"9955_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2022.108554","volume":"118","author":"YJ Zhang","year":"2022","unstructured":"Zhang YJ, Mu XD, Liu XW, Wang XY, Zhang X, Li K, Wu TY, Zhao D, Dong C (2022) Applying the quantum approximate optimization algorithm to the minimum vertex cover problem. Appl Soft Comput 118:108554","journal-title":"Appl Soft Comput"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-023-09955-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-023-09955-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-023-09955-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T17:18:54Z","timestamp":1698772734000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-023-09955-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,17]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["9955"],"URL":"https:\/\/doi.org\/10.1007\/s11047-023-09955-0","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,17]]},"assertion":[{"value":"1 August 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Ramiro Varela is editor of the \u201cBio-inspired Computing Approaches for Problem Solving\u201d special issue of the <i>Natural Computing<\/i> journal. Besides, there are no more relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}