{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T05:33:59Z","timestamp":1777095239482,"version":"3.51.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T00:00:00Z","timestamp":1772236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T00:00:00Z","timestamp":1772236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u0824egli Studi di Perugia"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Evol. Intel."],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Quantum Circuit Compilation is an important problem in Quantum Computing and its purpose is to make a quantum circuit executable by a quantum machine. In particular, the nearest-neighborhood constraint required by many quantum machines for the execution of binary quantum gates is enforced by inserting additional swap gates in the circuit. Despite swap gates allow to overcome the limited connectivity of quantum devices, they increase both the noise of the circuit and its depth, with a consequent loss of quantum coherence. In this paper we propose to use a new Ant Colony Optimization (ACO) algorithm to solve the compilation problem by optimizing the number of swaps and its\n                    <jats:italic>depth<\/jats:italic>\n                    . The algorithm includes two original contributions: a\n                    <jats:italic>Divide-et-Impera<\/jats:italic>\n                    strategy to compile the input quantum circuit and a novel\n                    <jats:italic>iterated local search<\/jats:italic>\n                    strategy to set its initial state.\n                  <\/jats:p>","DOI":"10.1007\/s12065-025-01127-6","type":"journal-article","created":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T11:25:46Z","timestamp":1772277946000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Divide-et-Impera approach for compiling large quantum circuits via ant colony optimization"],"prefix":"10.1007","volume":"19","author":[{"given":"Marco","family":"Baioletti","sequence":"first","affiliation":[]},{"given":"Angelo","family":"Oddi","sequence":"additional","affiliation":[]},{"given":"Riccardo","family":"Rasconi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,28]]},"reference":[{"issue":"3","key":"1127_CR1","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s10472-011-9265-7","volume":"62","author":"M Baioletti","year":"2011","unstructured":"Baioletti M, Milani A, Poggioni V et al (2011) Experimental evaluation of pheromone models in ACOPlan. Ann Math Artif Intell62(3):187\u2013217. https:\/\/doi.org\/10.1007\/s10472-011-9265-7","journal-title":"Ann Math Artif Intell"},{"key":"1127_CR2","doi-asserted-by":"publisher","unstructured":"Baioletti M, Milani A, Santucci V (2017) A new precedence-based ant colony optimization for permutation problems. In: Simulated evolution and Learning - 11th International Conference, SEAL 2017, Shenzhen, China, November 10-13, 2017, Proceedings, Lecture Notes in Computer Science, vol 10593. Springer, pp 960\u2013971, https:\/\/doi.org\/10.1007\/978-3-319-68759-9_79","DOI":"10.1007\/978-3-319-68759-9_79"},{"key":"1127_CR3","doi-asserted-by":"publisher","unstructured":"Baioletti M, Rasconi R, Oddi A (2021) A novel ant colony optimization strategy for the quantum circuit compilation problem. In: Zarges C, V\u00e9rel S (Eds) Proceedings of EvoCOP 2021, Lecture Notes in Computer Science, vol 12692. Springer, pp 1\u201316, https:\/\/doi.org\/10.1007\/978-3-030-72904-2_1","DOI":"10.1007\/978-3-030-72904-2_1"},{"key":"1127_CR4","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1109\/TSMCB.2003.821450","volume":"34","author":"C Blum","year":"2004","unstructured":"Blum C, Dorigo M (2004) The hyper-cube framework for ant colony optimization. IEEE transactions on systems man and cybernetics Part B Cybernetics a publication of the IEEE Systems Man and Cybernetics Society 34:1161\u201372. https:\/\/doi.org\/10.1109\/TSMCB.2003.821450","journal-title":"IEEE transactions on systems man and cybernetics Part B Cybernetics a publication of the IEEE Systems Man and Cybernetics Society"},{"key":"1127_CR5","doi-asserted-by":"crossref","unstructured":"Booth KEC, Do M, Beck C, et\u00a0al (2018) Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation. In: Proceedings of the $$28^{th}$$ International Conference on Automated Planning & Scheduling, ICAPS-18, pp 366\u2013374","DOI":"10.1609\/icaps.v28i1.13920"},{"key":"1127_CR6","doi-asserted-by":"crossref","unstructured":"Brierley S (2017) Efficient implementation of quantum circuits with limited qubit interactions. Quantum Info Comput 17(13-14):1096\u20131104. http:\/\/dl.acm.org\/citation.cfm?id=3179575.3179577","DOI":"10.26421\/QIC17.13-14-2"},{"key":"1127_CR7","doi-asserted-by":"crossref","unstructured":"Chand S, Singh HK, Ray T, et\u00a0al (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":"1127_CR8","doi-asserted-by":"publisher","first-page":"4091","DOI":"10.1103\/PhysRevLett.74.4091","volume":"74","author":"JI Cirac","year":"1995","unstructured":"Cirac JI, Zoller P (1995) Quantum computations with cold trapped ions. Phys Rev Lett 74:4091\u20134094. https:\/\/doi.org\/10.1103\/PhysRevLett.74.4091","journal-title":"Phys Rev Lett"},{"key":"1127_CR9","unstructured":"Cormen TH, Leiserson CE, Rivest RL et al (2001) Introduction to Algorithms, 2nd edn. MIT Press"},{"key":"1127_CR10","doi-asserted-by":"publisher","unstructured":"Cruz D, Fournier R, Gremion F et al (2019) Efficient quantum algorithms for ghz and w states, and implementation on the ibm quantum computer. Adv Quant Technol 2(5\u20136):1900015. https:\/\/doi.org\/10.1002\/qute.201900015https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/qute.201900015","DOI":"10.1002\/qute.201900015"},{"key":"1127_CR11","unstructured":"Do M, Wang Z, O\u2019Gorman B, et\u00a0al (2020) Planning for compilation of a quantum algorithm for graph coloring. ArXiv abs\/2002.10917"},{"key":"1127_CR12","doi-asserted-by":"crossref","unstructured":"Dorigo M, St\u00fctzle T (2004) Ant colony optimization. Bradford Company, USA","DOI":"10.7551\/mitpress\/1290.001.0001"},{"key":"1127_CR13","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s P, R\u00e9nyi A (1960) On the evolution of random graphs. Publ Math Inst Hungary Acad Sci 5:17\u201361","journal-title":"Publ Math Inst Hungary Acad Sci"},{"key":"1127_CR14","unstructured":"Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028"},{"key":"1127_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2021.3053921","volume":"2","author":"D Ferrari","year":"2021","unstructured":"Ferrari D, Cacciapuoti AS, Amoretti M et al (2021) Compiler design for distributed quantum computing. IEEE Trans Quant Eng 2:1\u201320. https:\/\/doi.org\/10.1109\/TQE.2021.3053921","journal-title":"IEEE Trans Quant Eng"},{"key":"1127_CR16","unstructured":"Guerreschi GG, Park J (2017) Gate scheduling for quantum algorithms. arXiv preprint arXiv:1708.00023"},{"issue":"1","key":"1127_CR17","doi-asserted-by":"publisher","first-page":"4543","DOI":"10.1038\/s41598-020-61316-4","volume":"10","author":"L Gyongyosi","year":"2020","unstructured":"Gyongyosi L (2020) Quantum state optimization and computational pathway evaluation for gate-model quantum computers. Sci Rep 10(1):4543. https:\/\/doi.org\/10.1038\/s41598-020-61316-4","journal-title":"Sci Rep"},{"issue":"1","key":"1127_CR18","doi-asserted-by":"publisher","first-page":"11229","DOI":"10.1038\/s41598-020-67014-5","volume":"10","author":"L Gyongyosi","year":"2020","unstructured":"Gyongyosi L, Imre S (2020) Circuit depth reduction for gate-model quantum computers. Sci Rep 10(1):11229. https:\/\/doi.org\/10.1038\/s41598-020-67014-5","journal-title":"Sci Rep"},{"issue":"1","key":"1127_CR19","doi-asserted-by":"publisher","first-page":"5172","DOI":"10.1038\/s41598-020-76728-5","volume":"11","author":"L Gyongyosi","year":"2021","unstructured":"Gyongyosi L, Imre S (2021) Scalable distributed gate-model quantum computers. Sci Rep 11(1):5172. https:\/\/doi.org\/10.1038\/s41598-020-76728-5","journal-title":"Sci Rep"},{"issue":"8","key":"1127_CR20","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/3524455","volume":"65","author":"L Gyongyosi","year":"2022","unstructured":"Gyongyosi L, Imre S (2022) Advances in the quantum internet. Commun ACM 65(8):52\u201363. https:\/\/doi.org\/10.1145\/3524455","journal-title":"Commun ACM"},{"issue":"2","key":"1127_CR21","doi-asserted-by":"publisher","first-page":"34","DOI":"10.3390\/a12020034","volume":"12","author":"S Hadfield","year":"2019","unstructured":"Hadfield S, Wang Z, O\u2019Gorman B et al (2019) From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12(2):34. https:\/\/doi.org\/10.3390\/a12020034","journal-title":"Algorithms"},{"key":"1127_CR22","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0167-6377(87)90021-6","volume":"6","author":"J Hart","year":"1987","unstructured":"Hart J, Shogan A (1987) Semi-greedy heuristics: an empirical study. Oper Res Lett 6:107\u2013114","journal-title":"Oper Res Lett"},{"key":"1127_CR23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.82.032332","volume":"82","author":"DA Herrera-Mart\u00ed","year":"2010","unstructured":"Herrera-Mart\u00ed DA, Fowler AG, Jennings D et al (2010) Photonic implementation for the topological cluster-state quantum computer. Phys Rev A 82:032332. https:\/\/doi.org\/10.1103\/PhysRevA.82.032332","journal-title":"Phys Rev A"},{"issue":"1","key":"1127_CR24","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1109\/JETCAS.2016.2528720","volume":"6","author":"A Kole","year":"2016","unstructured":"Kole A, Datta K, Sengupta I (2016) A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using $$n$$-gate lookahead. IEEE J Emerg Select Topics Circuits Syst 6(1):62\u201372. https:\/\/doi.org\/10.1109\/JETCAS.2016.2528720","journal-title":"IEEE J Emerg Select Topics Circuits Syst"},{"issue":"1","key":"1127_CR25","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/TCAD.2017.2693284","volume":"37","author":"A Kole","year":"2018","unstructured":"Kole A, Datta K, Sengupta I (2018) A new heuristic for $$n$$ -dimensional nearest neighbor realization of a quantum circuit. IEEE Trans Comput Aided Des Integr Circuits Syst 37(1):182\u2013192. https:\/\/doi.org\/10.1109\/TCAD.2017.2693284","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"key":"1127_CR26","unstructured":"Li G, Ding Y, Xie Y (2018) Tackling the qubit mapping problem for nisq-era quantum devices. CoRR abs\/1809.02573. http:\/\/arxiv.org\/abs\/1809.02573"},{"key":"1127_CR27","doi-asserted-by":"publisher","unstructured":"Maslov D, Falconer SM, Mosca M (2007) Quantum circuit placement: Optimizing qubit-to-qubit interactions through mapping quantum circuits into a physical experiment. In: Proceedings of the 44th Annual Design Automation Conference. ACM, New York, NY, USA, DAC \u201907, pp 962\u2013965, https:\/\/doi.org\/10.1145\/1278480.1278717","DOI":"10.1145\/1278480.1278717"},{"issue":"4","key":"1127_CR28","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1109\/TEVC.2002.802450","volume":"6","author":"D Merkle","year":"2002","unstructured":"Merkle D, Merkle M, Schmeck H (2002) Ant colony optimization for resource-constrained project scheduling. IEEE Trans Evol Comput 6(4):333\u2013346","journal-title":"IEEE Trans Evol Comput"},{"key":"1127_CR29","doi-asserted-by":"crossref","unstructured":"Nau D, Ghallab M, Traverso P (2004) Automated Planning: Theory & Practice. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA","DOI":"10.1016\/B978-155860856-6\/50021-1"},{"key":"1127_CR30","doi-asserted-by":"crossref","unstructured":"Nielsen MA, Chuang IL (2011) Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th edn. Cambridge University Press, New York, NY, USA","DOI":"10.1017\/CBO9780511976667"},{"key":"1127_CR31","doi-asserted-by":"crossref","unstructured":"Oddi A, Rasconi R (2018) Greedy randomized search for scalable compilation of quantum circuits. In: van Hoeve WJ (ed) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer International Publishing, Cham, pp 446\u2013461","DOI":"10.1007\/978-3-319-93031-2_32"},{"key":"1127_CR32","doi-asserted-by":"publisher","unstructured":"Oddi A, Rasconi R, Baioletti M, et\u00a0al (2023) Quantum circuit compilation for the graph coloring problem. In: AIxIA 2022 \u2013 Advances in Artificial Intelligence: XXIst International Conference of the Italian Association for Artificial Intelligence, AIxIA 2022, Udine, Italy, November 28 \u2013 December 2, 2022, Proceedings. Springer-Verlag, Berlin, Heidelberg, p 374\u2013386, https:\/\/doi.org\/10.1007\/978-3-031-27181-6_26","DOI":"10.1007\/978-3-031-27181-6_26"},{"key":"1127_CR33","doi-asserted-by":"crossref","unstructured":"Rasconi R, Oddi A (2019) An innovative genetic algorithm for the quantum circuit compilation problem. In: Proceeding of the Thirty-Third Conference on Artificial Intelligence AAAI-2019. AAAI Press, pp 7707\u20137714","DOI":"10.1609\/aaai.v33i01.33017707"},{"issue":"1","key":"1127_CR34","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1023\/B:HEUR.0000019986.96257.50","volume":"10","author":"MG Resende","year":"2004","unstructured":"Resende MG, Werneck RF (2004) A hybrid heuristic for the p-medianproblem. J Heurist 10(1):59\u201388. https:\/\/doi.org\/10.1023\/B:HEUR.0000019986.96257.50","journal-title":"J Heurist"},{"key":"1127_CR35","doi-asserted-by":"publisher","unstructured":"Sete EA, Zeng WJ, Rigetti CT (2016) A functional architecture for scalable quantum computing. In: 2016 IEEE International Conference on Rebooting Computing (ICRC), pp 1\u20136, https:\/\/doi.org\/10.1109\/ICRC.2016.7738703","DOI":"10.1109\/ICRC.2016.7738703"},{"issue":"1","key":"1127_CR36","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8e92","volume":"6","author":"S Sivarajah","year":"2020","unstructured":"Sivarajah S, Dilkes S, Cowtan A et al (2020) t\u2758ket\u27e9: a retargetable compiler for NISQ devices. Quant Sci Technol 6(1):014003. https:\/\/doi.org\/10.1088\/2058-9565\/ab8e92","journal-title":"Quant Sci Technol"},{"key":"1127_CR37","doi-asserted-by":"publisher","unstructured":"Venturelli D, Do M, Rieffel E, et\u00a0al (2017) Temporal planning for compilation of quantum approximate optimization circuits. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp 4440\u20134446, https:\/\/doi.org\/10.24963\/ijcai.2017\/620","DOI":"10.24963\/ijcai.2017\/620"},{"key":"1127_CR38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.101.012320","volume":"101","author":"Z Wang","year":"2020","unstructured":"Wang Z, Rubin NC, Dominy JM et al (2020) $$xy$$ mixers: Analytical and numerical results for the quantum alternating operator ansatz. Phys Rev A 101:012320. https:\/\/doi.org\/10.1103\/PhysRevA.101.012320","journal-title":"Phys Rev A"},{"key":"1127_CR39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.022306","volume":"87","author":"NY Yao","year":"2013","unstructured":"Yao NY, Gong ZX, Laumann CR et al (2013) Quantum logic between remote quantum registers. Phys Rev A 87:022306. https:\/\/doi.org\/10.1103\/PhysRevA.87.022306","journal-title":"Phys Rev A"},{"key":"1127_CR40","unstructured":"Zahedinejad E, Zaribafiyan A (2017) Combinatorial optimization on gate model quantum computers: a survey. ArXiv1708.05294. https:\/\/api.semanticscholar.org\/CorpusID:6577991"}],"container-title":["Evolutionary Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12065-025-01127-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12065-025-01127-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12065-025-01127-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T04:34:54Z","timestamp":1777091694000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12065-025-01127-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,28]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1127"],"URL":"https:\/\/doi.org\/10.1007\/s12065-025-01127-6","relation":{},"ISSN":["1864-5909","1864-5917"],"issn-type":[{"value":"1864-5909","type":"print"},{"value":"1864-5917","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,28]]},"assertion":[{"value":"3 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"41"}}