Modification of a Quantum-inspired Genetic Algorithm for Numerical Optimization Using Qudit under Conditions of Simulating Quantum Decoherence

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

The genetic algorithm for numerical optimization (GA) of the metaheuristic class is a method for finding optimal solutions based on the biological principles of natural selection and variability. GA is characterized by high operating speed, resistance to noise in the data, low probability of hitting the local extremum of the multimodal objective function, as well as the simultaneous application of probabilistic and deterministic rules for generating search space points. An alternative to the classical GA is the quantum-inspired genetic algorithm for numerical optimization (QIGA), which has advantages that are unattainable for GA by using the concepts and principles of quantum computing. The article proposes a new approach to the implementation of a quantum-inspired genetic numerical optimization algorithm for searching for the global maximum of the objective function, based on modeling the functioning of the GA by simulating the execution of quantum calculations based on qudit in the conditions of the existence of quantum decoherence in the era of noisy medium-scale quantum algorithms. For this purpose, to carry out quantum operations of rotating the states of multilevel quantum systems, the paper presents a density matrix based on Heisenberg–Weyl operators as an analogue of the Bloch sphere for qudits. The simulation of quantum decoherence is interpreted from the point of view of the influence of extraneous noise emanating from the environment on the qudit and is presented as the use of a normal random variable with zero mathematical expectation and unit variance in quantum gates. At the same time, the work presents detailed pseudocodes of the functioning of both the most modified quantum-inspired genetic algorithm for numerical optimization and its individual operations. Testing is carried out by conducting computational experiments with the implementation of a modified algorithm on two-dimensional and multidimensional functions of test optimization problems, as well as when solving an applied optimization problem of planning hybrid flow production in the manufacturing industry based on financial costs and solving the problem of increasing forecasting accuracy based on compact extreme learning machines. The experimental results demonstrate the superiority of the new algorithm over QIGA and classical optimization algorithms in the accuracy of the solution, the speed of convergence with the target value of the global maximum and the execution time of the algorithm.

Full Text

Restricted Access

About the authors

Vladimir V. Maslennikov

MIREA – Russian Technological University

Author for correspondence.
Email: vldmsn@yahoo.com
ORCID iD: 0000-0003-3201-2228

senior lecturer, Department of Corporate Information Systems, Institute of Information Technology

Russian Federation, Moscow

Liliya A. Demidova

MIREA – Russian Technological University

Email: liliya.demidova@rambler.ru
ORCID iD: 0000-0003-4516-3746

Dr. Sci. (Eng.), Professor, professor, Department of Corporate Information Systems, Institute of Information Technology

Russian Federation, Moscow

References

  1. Arute F., Arya K., Babbush R. et al. Quantum supremacy using a programmable superconducting processor. Nature. 2019. No. 574. Pp. 505–510. doi: 10.1038/s41586-019-1666-5
  2. Arrazola J., Delgado A., Bardhan B., Lloyd S. Quantum-inspired algorithms in practice. Quantum. 2020. No. 4. P. 307. doi: 10.22331/q-2020-08-13-307
  3. Abs da Cruz A.V., Vellasco M.M.B.R., Pacheco M.A.C. Quantum-inspired evolutionary algorithm for numerical optimization. IEEE International Conference on Evolutionary Computation. 2006. Pp. 2630–2637. doi: 10.1109/CEC.2006.1688637
  4. Asadian A., Erker P., Huber M., Klöckl C. Heisenberg–Weyl observables: Bloch vectors in phase space. Physical Review A. 2016. No. 94. doi: 10.1103/PhysRevA.94.010301
  5. Aksenov M., Zalivako I., Semerikov I. et al. Realizing quantum gates with optically addressable Yb + 171 ion qudits. Physical Review A. 2023. No. 107. doi: 10.1103/PhysRevA.107.052612
  6. Ab Rashid M.F.F., Mutasim M.A.N. Modeling and optimization of cost-based hybrid flow shop scheduling problem using metaheuristics. International Journal of Global Optimization and Its Application. 2023. No. 2. Pp. 244–254. doi: 10.56225/ijgoia.v2i4.265
  7. Beiranvand V., Hare W., Lucet Y. Best practices for comparing optimization algorithms. Optimization and Engineering. 2017. No. 18. doi: 10.1007/s11081-017-9366-1
  8. Chen J., Zhang F., Chen M. et al. Classical simulation of intermediate-size quantum circuits. 2018. doi: 10.48550/arXiv.1805.01450.
  9. Chabaud U., Ferrini G., Grosshans F., Markham D. Classical simulation of Gaussian quantum circuits with non-Gaussian input states. Physical Review Research. 2021. No. 3. doi: 10.1103/PhysRevResearch.3.033018
  10. Carlier J., Néron E. An exact method for solving the multi-processor flow-shop. RAIRO – Operations Research. 2000. No. 34. Pp. 1–25. doi: 10.1051/ro:2000103
  11. Demidova L., Gorchakov A. A study of chaotic maps producing symmetric distributions in the fish school search optimization algorithm with exponential step decay. Symmetry. 2020. No. 12. P. 784. doi: 10.3390/sym12050784
  12. Demidova L., Nikulchev E., Sokolova Y. The SVM classifier based on the modified particle swarm optimization. International Journal of Advanced Computer Science and Applications. 2016. No. 7. Pp. 16–24. doi: 10.14569/IJACSA.2016.070203
  13. Fay M., Proschan M. Wilcoxon–Mann–Whitney or t-test? On assumptions for hypothesis test and multiple interpretations of decision rules. Statistics Surveys. 2010. No. 4. Pp. 1–39. doi: 10.1214/09-SS051
  14. Huang Q., Mendl C. Classical simulation of quantum circuits using a multiqubit Bloch vector representation of density matrices. Physical Review A. 2022. No. 105. doi: 10.1103/PhysRevA.105.022409
  15. Hao T., Huang X., Jia C., Peng C. A quantum-inspired tensor network algorithm for constrained combinatorial optimization problems. Frontiers in Physics. 2022. No. 10. P. 906590. doi: 10.3389/fphy.2022.906590
  16. Han K., Kim J. Genetic quantum algorithm and its application to combinatorial optimization problem. Proceedings of the IEEE Conference on Evolutionary Computation, ICEC. 2000. Vol. 2. Pp. 1354–1360. doi: 10.1109/CEC.2000.870809
  17. Hakemi S., Houshmand M., KheirKhah E., Hosseini S. A review of recent advances in quantum-inspired metaheuristics. Evolutionary Intelligence. 2022. No. 1-16. doi: 10.1007/s12065-022-00783-2
  18. Harrison D., Rubinfeld D. Hedonic housing prices and the demand for clean air. Journal of Environmental Economics and Management. 1978. No. 5. Pp. 81–102. doi: 10.1016/0095-0696(78)90006-2
  19. Kaul D., Raju H., Tripathy B.K. Quantum-computing-inspired algorithms in machine learning. 2018. doi: 10.4018/978-1-5225-5219-2.ch001
  20. Krysenko D., Prudnikov O. Laser cooling of 171Yb+ ion in polychromatic light field. Journal of Experimental and Theoretical Physics. 2023. No. 137. Pp. 239–245. doi: 10.1134/S1063776123080149
  21. Kibler D., Aha D.W., Albert M.K. Instance-based prediction of real-valued attributes. Computational Intelligence. 1989. No. 5 (2). Pp. 51–57. doi: 10.1111/j.1467-8640.1989.tb00315.x
  22. Moretti V. Mathematical foundations of quantum mechanics: An advanced short course. International Journal of Geometric Methods in Modern Physics. 2015. No. 13. doi: 10.1142/S0219887816300117
  23. Nowotniak R., Kucharski J. Building Blocks propagation in quantum-inspired genetic algorithm. Scientific Bulletin of Academy of Science and Technology, Automatics. 2010. No. 14.
  24. Preskill J. Quantum computing in the NISQ era and beyond. Quantum. 2018. No. 2. doi: 10.22331/q-2018-08-06-79
  25. Sabbar B.M., Rasool H.A. Quantum inspired genetic algorithm model based automatic modulation classification // Webology. 2021. Vol. 18. Special Issue. Pp. 1070–1085. doi: 10.14704/WEB/V18SI04/WEB18182. EDN: BNCEZA.
  26. Schlosshauer M. Decoherence, the measurement problem, and interpretations of quantum mechanics. Reviews of Modern Physics. 2003. No. 76. Pp. 1267–1305.
  27. Schlosshauer M. Quantum decoherence. Physics Reports. 2019. Vol. 831. Pp. 1–57. doi: 10.1016/j.physrep.2019.10.001. EDN PTXNOQ
  28. Sharma G., Ghosh S. Four-dimensional Bloch sphere representation of qutrits using Heisenberg–Weyl operators. 2021. URL: https://arxiv.org/abs/2101.06408
  29. Sofge D. Prospective algorithms for quantum evolutionary computation: Proceedings of the Second Quantum Interaction Symposium (QI-2008). College Publications, UK, 2008. URL: https://arxiv.org/pdf/0804.1133
  30. Song S.J., Wang Y., Lin X., Huang Q. Study on GA-based training algorithm for extreme learning machine: 7th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC). Hangzhou, China, 2015. Pp. 132–135. doi: 10.1109/IHMSC.2015.156.
  31. Thieu N.V., Mirjalili S. MEALPY: An open-source library for latest meta-heuristic algorithms in Python. Journal of Systems Architecture. 2023. No. 139. doi: 10.1016/j.sysarc.2023.102871
  32. Wang Y., Hu Z., Sanders B., Kais S. Qudits and High-Dimensional Quantum Computing. Frontiers in Physics. 2020. No. 8. doi: 10.3389/fphy.2020.589504
  33. Zhang G. Quantum-inspired evolutionary algorithms: A survey and empirical study. J. Heuristics. 2011. No. 17. Pp. 303–351. doi: 10.1007/s10732-010-9136-0
  34. Żurek W. Decoherence, einselection, and the quantum origins of the classical. Reviews of Modern Physics. 2001. No. 75. doi: 10.1103/RevModPhys.75.715
  35. Demidova L.A., Gorchakov A.V. Application of bioinspired global optimization algorithms to improve the accuracy of forecasts of compact extreme learning machines. Russian Technological Journal. 2022. Vol. 10. No. 2. Pp. 59–74. (In Rus.). doi: 10.32362/2500-316X-2022-10-2-59-74. EDN: WCFZVD.
  36. Korzh O.V., Chernyavsky A.Yu., Korzh A.A. Modeling of the quantum Fourier transform with noise on a Lomonosov supercomputer. In: Scientific service on the Internet: All facets of parallelism: Proceedings of the International Supercomputer Conference, Novorossiysk, September 23–28, 2013. Novorossiysk: Publishing House of the Moscow State University, 2013. Pp. 188–193. (In Rus.). EDN: SXFHSD.
  37. Maslennikov V.V. Quantum-inspired optimization algorithms in solving operational management problems. In: New information technologies in scientific research: Materials of the XXVIII All-Russian Scientific and Technical Conference of Students, Young Scientists and Specialists, Ryazan, November 22–24, 2023. Ryazan: Ryazan State Radio Engineering University named after V.F. Utkin, 2023. Pp. 42–44. (In Rus.). EDN: TTUMEJ.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Fig. 1. Representation of an elementary qubit in the form of a Bloch sphere

Download (22KB)
Indexing metadata
3. Fig. 2. Convergence graphs for test functions of dimension n = 2: a – f1; b – f2; c – f3; d – f4

Download (57KB)
Indexing metadata
4. Fig. 3. Convergence graphs for test functions of dimension n = 2: a – f5; b – f6; c – f7; d – f8

Download (51KB)
Indexing metadata
5. Fig. 4. Convergence graphs for test functions of dimension n = 15: a – f1; b – f2; c – f3; d – f4

Download (63KB)
Indexing metadata
6. Fig. 5. Convergence graphs for test functions of dimension n = 15: a – f5; b – f6; c – f7; d – f8

Download (71KB)
Indexing metadata