Advances in quantum genetic algorithms

Quantum Genetic Algorithms (QGA) are an emerging field of multivariate quantum optimization that emulate Darwinian evolution and natural selection, with vast applications in chemistry and engineering. The appropriate application of fitness functions and fitness selection is the problem-encoding step and the slowest step in designing QGAs for specific physical applications. In this paper, we provide a comprehensive review of these crucial steps. Our survey maps cases of quantum advantage, classifies and illustrates QGAs and their subroutines, and discusses the two main physical problems tackled by QGAs: potential energy minimization of particles on a sphere and molecular eigensolving. We conclude that the encoding used by the Thomson problem is a decisive step toward the use of QGAs in a variety of physical applications, while Grover’s search as a selection step in Reduced QGAs is the main driver of speedup. Although the small scale of simulations and the emergent nature of QGA optimizations make their complexity analyses difficult, recent studies are focusing on strategies to scale QGAs up.