[en] Quantum computers have made significant progress in the last two decades showing great potential in tackling some of the most challenging problems in computing. This ongoing progress creates an opportunity to implement and evaluate quantum-inspired metaheuristics on real quantum devices, with the aim of uncovering potential computational advantages. Additionally, the practical constraints associated with current quantum computers have highlighted a critical need for classical heuristic methods to optimize the tunable parameters of quantum circuits. Nature-inspired metaheuristics have emerged as promising candidates for fulfilling this optimization role. In this paper, we discuss both of these potential directions at the intersection of evolutionary computing and quantum computing while surveying some of the most promising advancements in these directions. We start with the review of quantum-inspired metaheuristics and then explore implementations of some of these quantum-inspired algorithms on physical quantum devices, capitalizing on the progress in quantum computing technology. Furthermore, we investigate the role of nature-inspired metaheuristics in enhancing the performance of noisy intermediate-scale quantum computers by fine-tuning their parameters. Finally, we discuss some of the recent progress at the intersection of both computing frameworks to highlight the current status and potential of the currently available quantum computing hardware. Synergies between these two computing frameworks demonstrate the potential of a strongly symbiotic relation that can contribute to the simultaneous advancements in both of these computing paradigms.
Disciplines :
Computer science
Author, co-author :
Ur Rehman, Junaid ; King Fahd University of Petroleum and Minerals, Department of Electrical Engineering, Dhahran, Saudi Arabia ; Interdisciplinary Centre for Security, Reliability and Trust (SnT), Luxembourg City, Luxembourg ; King Fahd University of Petroleum and Minerals, Interdisciplinary Research Center for Intelligent Secure Systems, Dhahran, Saudi Arabia
Ulum, Muhammad Shohibul ; Kyung Hee University, Department of Electronics and Information Convergence Engineering, Yongin-si, South Korea
Shaffar, Abdurrahman Wachid ; Kyung Hee University, Department of Electronics and Information Convergence Engineering, Yongin-si, South Korea
Hakim, Amirul Adlil ; Kyung Hee University, Department of Electronics and Information Convergence Engineering, Yongin-si, South Korea
Mujirin ; Kyung Hee University, Department of Electronics and Information Convergence Engineering, Yongin-si, South Korea
ABDULLAH, Zaid ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SigCom ; Interdisciplinary Centre for Security, Reliability and Trust (SnT), Luxembourg City, Luxembourg
Al-Hraishawi, Hayder ; Interdisciplinary Centre for Security, Reliability and Trust (SnT), Luxembourg City, Luxembourg ; University of South Florida, Department of Electrical Engineering, Tampa, United States
CHATZINOTAS, Symeon ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SigCom ; Interdisciplinary Centre for Security, Reliability and Trust (SnT), Luxembourg City, Luxembourg
Shin, Hyundong ; Kyung Hee University, Department of Electronics and Information Convergence Engineering, Yongin-si, South Korea
External co-authors :
yes
Language :
English
Title :
Evolutionary Algorithms and Quantum Computing: Recent Advances, Opportunities, and Challenges
Original title :
[en] Evolutionary Algorithms and Quantum Computing: Recent Advances, Opportunities, and Challenges
Publication date :
28 January 2025
Journal title :
IEEE Access
ISSN :
2169-3536
Publisher :
Institute of Electrical and Electronics Engineers Inc.
The work of Hyundong Shin was supported in part by the National Research Foundation of Korea (NRF) grant funded by Korean Government (MSIT) under Grant NRF-2022R1A4A3033401; and in part by the Ministry of Science and ICT (MSIT), South Korea, under the Information Technology Research Center (ITRC) Support Program supervised by the Institute for Information & Communications Technology Planning & Evaluation (IITP) under Grant IITP-2024-2021-0-02046.
R. P. Feynman, "Simulating physics with computers," Int. J. Theor. Phys., vol. 21, nos. 6-7, pp. 467-488, Jun. 1982.
P. Benioff, "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines," J. Stat. Phys., vol. 22, no. 5, pp. 563-591, May 1980.
Y. Manin, "Computable and uncomputable," Sovetskoye Radio, vol. 128, p. 28, Apr. 1980.
D. Deutsch, "Quantum theory, the church-turing principle and the universal quantum compute," Proc. R. Soc. Lond. A, vol. 400, no. 18, pp. 97-117, Dec. 1985.
D. Deutsch and R. Jozsa, "Rapid solution of problems by quantum computation," Proc. Roy. Soc. London A, Math. Phys. Sci., vol. 439, no. 1907, pp. 553-558, Dec. 1992.
P. W. Shor, "Algorithms for quantum computation: Discrete logarithms and factoring," in Proc. 35th Annu. Symp. Found. Comput. Sci., 1994, pp. 124-134.
C. Gidney and M. Ekera, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits," Quantum, vol. 5, p. 433, Apr. 2021.
M. Webber, V. Elfving, S. Weidt, and W. K. Hensinger, "The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime," AVS Quantum Sci., vol. 4, no. 1, Mar. 2022, Art. no. 013801.
J. Preskill, "Quantum computing in the NISQ era and beyond," Quantum, vol. 2, p. 79, Aug. 2018.
F. Arute, "Quantum supremacy using a programmable superconducting processor," Nature, vol. 574, no. 7779, pp. 505-510, Oct. 2019.
L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, A. E. Lita, T. Gerrits, S. W. Nam, V. D. Vaidya, M. Menotti, I. Dhand, Z. Vernon, N. Quesada, and J. Lavoie, "Quantum computational advantage with a programmable photonic processor," Nature, vol. 606, no. 7912, pp. 75-81, Jun. 2022.
H.-S. Zhong, "Quantum computational advantage using photons," Science, vol. 370, no. 6523, pp. 1460-1463, Dec. 2020.
E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, and R. Wisnieff, "Leveraging secondary storage to simulate deep 54-qubit sycamore circuits," 2019, arXiv:1910.09534.
B. Villalonga, M. Yuezhen Niu, L. Li, H. Neven, J. C. Platt, V. N. Smelyanskiy, and S. Boixo, "Efficient approximation of experimental Gaussian boson sampling," 2021, arXiv:2109.11525.
C. Oh, M. Liu, Y. Alexeev, B. Fefferman, and L. Jiang, "Classical algorithm for simulating experimental Gaussian boson sampling," 2023, arXiv:2306.03709.
K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W. Mok, S. Sim, L. C. Kwek, and A. Aspuru-Guzik, "Noisy intermediatescale quantum algorithms," Rev. Mod. Phys., vol. 94, no. 1, Feb. 2022, Art. no. 015004.
K. Sörensen, M. Sevaux, and F. Glover, "A history of metaheuristics," in Handbook of Heuristics. Cham, Switzerland: Springer, 2018, pp. 791-808.
E. Talbi, "Metaheuristics," Scholarpedia, vol. 10, p. 6532, Jun. 2009.
E. Tang, "A quantum-inspired classical algorithm for recommendation systems," in Proc. 51st Annu. ACM SIGACT Symp. Theory Comput., Jun. 2019, pp. 217-228.
O. H. M. Ross, "A review of quantum-inspired metaheuristics: Going from classical computers to real quantum computers," IEEE Access, vol. 8, pp. 814-838, 2020.
L. Huynh, J. Hong, A. Mian, H. Suzuki, Y. Wu, and S. Camtepe, "Quantum-inspired machine learning: A survey," 2023, arXiv:2308.11269.
F. S. Gharehchopogh, "Quantum-inspired Metaheuristic algorithms: Comprehensive survey and classification," Artif. Intell. Rev., vol. 56, no. 6, pp. 5479-5543, Jun. 2023.
L. Miguel Antonio and C. A. Coello Coello, "Coevolutionary multiobjective evolutionary algorithms: Survey of the state-of-the-art," IEEE Trans. Evol. Comput., vol. 22, no. 6, pp. 851-865, Dec. 2018.
Z.-H. Zhan, J.-Y. Li, and J. Zhang, "Evolutionary deep learning: A survey," Neurocomputing, vol. 483, pp. 42-58, Apr. 2022.
S. Hakemi, M. Houshmand, E. Kheirkhah, and S. A. Hosseini, "A review of recent advances in quantum-inspired metaheuristics," Evol. Intell., vol. 17, no. 2, pp. 627-642, Apr. 2024.
K.-H. Han and J.-H. Kim, "Quantum-inspired evolutionary algorithm for a class of combinatorial optimization," IEEE Trans. Evol. Comput., vol. 6, no. 6, pp. 580-593, Dec. 2002.
H.-P. Chiang, Y.-H. Chou, C.-H. Chiu, S.-Y. Kuo, and Y.-M. Huang, "A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems," Soft Comput., vol. 18, no. 9, pp. 1771-1781, Sep. 2014.
A. Malossini, E. Blanzieri, and T. Calarco, "Quantum genetic optimization," IEEE Trans. Evol. Comput., vol. 12, no. 2, pp. 231-241, Apr. 2008.
J. C. Bardin, D. Sank, O. Naaman, and E. Jeffrey, "Quantum computing: An introduction for microwave engineers," IEEE Microw. Mag., vol. 21, no. 8, pp. 24-44, Aug. 2020.
J. Ng and D. Abbott, "Introduction to solid-state quantum computation for engineers," Microelectron. J., vol. 33, nos. 1-2, pp. 1-177, Jan. 2002.
M. Bonilla-Licea, D. Bonilla-Licea, M. Bonilla-Estrada, A. Soria-López, and J. Carlos Martínez-García, "A primer on quantum mechanics for electrical engineers," IEEE Access, vol. 12, pp. 114658-114669, 2024.
D. Ferry, Quantum Mechanics: An Introduction for Device Physicists and Electrical Engineers. Boca Raton, FL, USA: CRC Press, Jan. 2001.
D. A. B. Miller, Quantum Mechanics for Scientists and Engineers. Cambridge, U.K.: Cambridge Univ. Press, Apr. 2008.
J. Watrous, The Theory of Quantum Information, 1st ed., Cambridge, U.K.: Cambridge Univ. Press, Apr. 2018.
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th ed., Cambridge, U.K.: Cambridge Univ. Press, Jan. 2011.
G. E. P. Box, "Evolutionary operation: A method for increasing industrial productivity," Appl. Statist., vol. 6, no. 2, p. 81, Jun. 1957.
R. M. Friedberg, "A learning machine: Part I," IBM J. Res. Develop., vol. 2, no. 1, pp. 2-13, Jan. 1958.
R. M. Friedberg, B. Dunham, and J. H. North, "A learning machine: Part II," IBM J. Res. Develop., vol. 3, no. 3, pp. 282-287, Jul. 1959.
T. Back, U. Hammel, and H.-P. Schwefel, "Evolutionary computation: Comments on the history and current state," IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 3-17, Apr. 1997.
P. A. Vikhar, "Evolutionary algorithms: A critical review and its future prospects," in Proc. Int. Conf. Global Trends Signal Process., Inf. Comput. Commun. (ICGTSPICC), Dec. 2016, pp. 261-265.
J.-Y. Li, Z.-H. Zhan, and J. Zhang, "Evolutionary computation for expensive optimization: A survey," Mach. Intell. Res., vol. 19, no. 1, pp. 3-23, Feb. 2022.
K. D. Jong, "Evolutionary computation," Nat. Rev. Genet., vol. 2, pp. 428-436, Jul. 2007.
T. Bäck and H. Schwefel, "Evolutionary computation: An overview," Annu. Rev. Ecol. Evol. Syst., vol. 30, pp. 20-29, Dec. 2002.
Z.-G. Chen, Z.-H. Zhan, S. Kwong, and J. Zhang, "Evolutionary computation for intelligent transportation in smart cities:Asurvey," IEEE Comput. Intell. Mag., vol. 17, no. 2, pp. 83-102, May 2022.
E. H. Houssein, A. G. Gad, K. Hussain, and P. N. Suganthan, "Major advances in particle swarm optimization: Theory, analysis, and application," Swarm Evol. Comput., vol. 63, Jun. 2021, Art. no. 100868.
K. Arulkumaran, A. Cully, and J. Togelius, "AlphaStar: An evolutionary computation perspective," in Proc. Genetic Evol. Comput. Conf. Companion, Jul. 2019, pp. 314-315.
K. Sörensen, "Metaheuristics-The metaphor exposed," Int. Trans. Oper. Res., vol. 22, no. 1, pp. 3-18, Jan. 2015.
J. Del Ser, E. Osaba, D. Molina, X.-S. Yang, S. Salcedo-Sanz, D. Camacho, S. Das, P. N. Suganthan, C. A. Coello Coello, and F. Herrera, "Bio-inspired computation: Where we stand and what's next," Swarm Evol. Comput., vol. 48, pp. 220-250, Aug. 2019.
C. Blum and A. Roli, "Metaheuristics in combinatorial optimization: Overview and conceptual comparison," ACM Comput. Surv., vol. 35, no. 3, pp. 268-308, Sep. 2003.
M. Gendreau and J.-Y. Potvin, Handbook of Metaheuristics. New York, NY, USA: Springer, 2018.
V. Tomar, M. Bansal, and P. Singh, "Metaheuristic algorithms for optimization: A brief review," Eng. Proc., vol. 59, no. 1, p. 238, Mar. 2024.
C.-W. Tsai and M.-C. Chiang, Handbook of Metaheuristic Algorithms. Amsterdam, The Netherlands: Elsevier, May 2023.
G. Zhang, "Quantum-inspired evolutionary algorithms: A survey and empirical study," J. Heuristics, vol. 17, no. 3, pp. 303-351, Jun. 2011.
S. Karmakar, A. Dey, and I. Saha, "Use of quantum-inspired metaheuristics during last two decades," in Proc. 7th Int. Conf. Commun. Syst. Netw. Technol. (CSNT), Nov. 2017, pp. 272-278.
K.-H. Han and J.-H. Kim, "Genetic quantum algorithm and its application to combinatorial optimization problem," in Proc. Congr. Evol. Computation. CEC00, vol. 2, 2000, pp. 1354-1360.
Y. Wang, X.-Y. Feng, Y.-X. Huang, D.-B. Pu, W.-G. Zhou, Y.-C. Liang, and C.-G. Zhou, "A novel quantum swarm evolutionary algorithm and its applications," Neurocomputing, vol. 70, nos. 4-6, pp. 633-640, Jan. 2007.
R. S. Pavithr and Gursaran, "Quantum inspired social evolution (QSE) algorithm for 0-1 knapsack problem," Swarm Evol. Comput., vol. 29, pp. 33-46, Aug. 2016.
O. Montiel, Y. Rubio, C. Olvera, and A. Rivera, "Quantum-inspired acromyrmex evolutionary algorithm," Sci. Rep., vol. 9, no. 1, p. 12181, Aug. 2019.
Z. Chen and P. Luo, "QISA: Incorporating quantum computation into simulated annealing for optimization problems," in Proc. IEEE Congr. Evol. Comput. (CEC), Jun. 2011, pp. 2480-2487.
G. Acampora and A. Vitiello, "Implementing evolutionary optimization on actual quantum processors," Inf. Sci., vol. 575, pp. 542-562, Oct. 2021.
C. Durr and P. Hoyer, "A quantum algorithm for finding the minimum," 1996, arXiv:9607014v2.
K. Kaparis, A. N. Letchford, and I. Mourtos, "Generalised 2-circulant inequalities for the max-cut problem," Oper. Res. Lett., vol. 50, no. 2, pp. 122-128, Mar. 2022.
R. Hassin and N. Leshenko, "Greedy differencing edge-contraction heuristic for the max-cut problem," Oper. Res. Lett., vol. 49, no. 3, pp. 320-325, May 2021.
C. Lu and Z. Deng, "A branch-and-bound algorithm for solving max-kcut problem," J. Global Optim., vol. 81, no. 2, pp. 367-389, Feb. 2021.
S. S. Gill, A. Kumar, H. Singh, M. Singh, K. Kaur, M. Usman, and R. Buyya, "Quantum computing: A taxonomy, systematic review and future directions," Software, Pract. Exper., vol. 52, no. 1, pp. 66-114, Oct. 2021.
H. Al-Hraishawi, J. U. Rehman, M. Razavi, and S. Chatzinotas, "Characterizing and utilizing the interplay between quantum technologies and non-terrestrial networks," IEEE Open J. Commun. Soc., vol. 5, pp. 1937-1957, 2024.
J. Kelly, "State preservation by repetitive error detection in a superconducting quantum circuit," Nature, vol. 519, no. 7541, pp. 66-69, Mar. 2015.
Y. Rubio, C. Olvera, and O. Montiel, "Quantum-inspired evolutionary algorithms on IBM quantum experience," Eng. Lett., vol. 29, no. 4, pp. 1573-1584, Nov. 2021.
E. T. Campbell, B. M. Terhal, and C. Vuillot, "Roads towards faulttolerant universal quantum computation," Nature, vol. 549, no. 7671, pp. 172-179, Sep. 2017.
A. Yu. Kitaev, "Quantum measurements and the Abelian stabilizer problem," 1995, arXiv: quant-ph/9511026.
L. K. Grover, "A fast quantum mechanical algorithm for database search," in Proc. 28th Annu. ACM Symp. Theory Comput., 1996, pp. 212-219.
F. M. Creevey, C. D. Hill, and L. C. L. Hollenberg, "GASP: A genetic algorithm for state preparation on quantum computers," Sci. Rep., vol. 13, no. 1, p. 11956, Jul. 2023.
M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, and P. J. Coles, "Variational quantum algorithms," Nat. Rev. Phys., vol. 3, no. 9, pp. 625-644, Aug. 2021.
L. Arufe, M. A. González, A. Oddi, R. Rasconi, and R. Varela, "Quantum circuit compilation by genetic algorithm for quantum approximate optimization algorithm applied to MaxCut problem," Swarm Evol. Comput., vol. 69, Mar. 2022, Art. no. 101030.
T. Rindell, B. Yenilen, N. Halonen, A. Pönni, I. Tittonen, and M. Raasakka, "Exploring the optimality of approximate state preparation quantum circuits with a genetic algorithm," Phys. Lett. A, vol. 475, Jul. 2023, Art. no. 128860.
A. G. Rattew, S. Hu, M. Pistoia, R. Chen, and S. Wood, "A domainagnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver," 2019, arXiv:1910.09694.
A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O'Brien, "A variational eigenvalue solver on a photonic quantum processor," Nature Commun., vol. 5, no. 1, p. 4213, Jul. 2014.
J. ur Rehman, H. Al-Hraishawi, and S. Chatzinotas, "Quantum approximate optimization algorithm for knapsack resource allocation problems in communication systems," in Proc. IEEE Int. Conf. Commun., May 2023, pp. 2674-2679.
H. Al-Hraishawi, J. U. Rehman, and S. Chatzinotas, "Quantum optimization algorithm for LEO satellite communications based on cellfree massive MIMO," in Proc. IEEE Int. Conf. Commun. Workshops, May 2023, pp. 1759-1764.
E. Farhi, J. Goldstone, and S. Gutmann, "A quantum approximate optimization algorithm," 2014, arXiv:1411.4028.
A. Pérez-Salinas, A. Cervera-Lierta, E. Gil-Fuster, and J. I. Latorre, "Data re-uploading for a universal quantum classifier," Quantum, vol. 4, p. 226, Feb. 2020.
J. Biamonte, P.Wittek, N. Pancotti, P. Rebentrost, N.Wiebe, and S. Lloyd, "Quantum machine learning," Nature, vol. 549, no. 7671, pp. 195-202, Sep. 2017.
D. Faílde, J. D. Viqueira, M. M. Juane, and A. Gómez, "Using differential evolution to avoid local minima in variational quantum algorithms," Sci. Rep., vol. 13, no. 1, p. 16230, Sep. 2023.
G. Acampora, A. Chiatto, and A. Vitiello, "Genetic algorithms as classical optimizer for the quantum approximate optimization algorithm," Appl. Soft Comput., vol. 142, Jul. 2023, Art. no. 110296.
S. Chand, H. K. Singh, T. Ray, and M. Ryan, "Rollout based heuristics for the quantum circuit compilation problem," in Proc. IEEE Congr. Evol. Comput. (CEC), Jun. 2019, pp. 974-981.
A. Oddi and R. Rasconi, "Greedy randomized search for scalable compilation of quantum circuits," in Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Cham, Switzerland: Springer, 2018, pp. 446-461.
S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, "Noise-induced barren Plateaus in variational quantum algorithms," Nature Commun., vol. 12, no. 1, p. 6961, Nov. 2021.
M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, "Cost function dependent barren Plateaus in shallow parametrized quantum circuits," Nature Commun., vol. 12, no. 1, p. 1791, Mar. 2021.
E. R. Anschuetz and B. T. Kiani, "Quantum variational algorithms are swamped with traps," Nature Commun., vol. 13, no. 1, p. 7760, Dec. 2022.
M. Ragone, B. N. Bakalov, F. Sauvage, A. F. Kemper, C. O. Marrero, M. Larocca, and M. Cerezo, "A lie algebraic theory of barren Plateaus for deep parameterized quantum circuits," 2023, arXiv:2309.09342.
M. Cerezo, M. Larocca, and D. García-Martín, "Does provable absence of barren Plateaus imply classical simulability? Or, why we need to rethink variational quantum computing," arXiv:2312.09121, Dec. 2023.
J. Nádori, G. Morse, Z. Majnay-Takács, Z. Zimborás, and P. Rakyta, "Line search strategy for navigating through barren Plateaus in quantum circuit training," 2024, arXiv:2402.05227.
L. Franken, B. Georgiev, S. Mucke, M. Wolter, R. Heese, C. Bauckhage, and N. Piatkowski, "Quantum circuit evolution on NISQ devices," in Proc. IEEE Congr. Evol. Comput. (CEC), Jul. 2022, pp. 1-8.
X. Yang, J. Li, and X. Peng, "An improved differential evolution algorithm for learning high-fidelity quantum controls," Sci. Bull., vol. 64, no. 19, pp. 1402-1408, Oct. 2019.
