Quantum-Assisted Genetic Algorithm

James King, Masoud Mohseni, William Bernoudy, Alexandre Fréchette, Hossein Sadeghi, Sergei V. Isakov, Hartmut Neven, Mohammad H. AminarXiv 2019 · OpenReview

Abstract

Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Reverse annealing enables the development of genetic algorithms that use quantum fluctuation for mutations and classical mechanisms for the crossovers -- we refer to these as Quantum-Assisted Genetic Algorithms (QAGAs). We describe a QAGA and present experimental results using a D-Wave 2000Q quantum annealing processor. On a set of spin-glass inputs, standard (forward) quantum annealing finds good solutions very quickly but struggles to find global optima. In contrast, our QAGA proves effective at finding global optima for these inputs. This successful interplay of non-local classical and quantum fluctuations could provide a promising step toward practical applications of Noisy Intermediate-Scale Quantum (NISQ) devices for heuristic discrete optimization.

Introduction

Discrete optimization—the task of finding the optimal configuration among a vast number of possibilities—is a fundamental challenge in computer science. Two prominent approaches to this problem are Genetic Algorithms (GAs), which excel at global exploration through evolutionary mechanisms, and Quantum Annealing (QA), which leverages quantum tunneling to navigate complex energy landscapes.

However, standard "forward" QA often acts as a black box: it begins in a total quantum superposition and evolves toward a solution, offering no mechanism to refine a pre-existing "good" solution. This paper introduces the Quantum-Assisted Genetic Algorithm (QAGA), which addresses this limitation by integrating reverse quantum annealing as a mutation operator within a classical GA framework. This allows the algorithm to start from a known classical state and use quantum fluctuations to "tunnel" into nearby, lower-energy states.

Methodology

The QAGA framework follows a standard evolutionary loop but replaces traditional random bit-flips with quantum-mechanical local searches.

1. Recombination (Crossover)

The algorithm utilizes isoenergetic cluster moves (Houdayer moves) for recombination. By comparing two "parent" solutions and identifying clusters of differing variables, the algorithm flips these clusters to produce offspring. This method is particularly effective for the planar-like graphs used in this study.

2. Mutation: Reverse Quantum Annealing

Instead of stochastic noise, mutation is performed via reverse quantum annealing on a D-Wave 2000Q processor. A classical solution is loaded onto the QPU, and the transverse field (quantum fluctuation) is increased to a mid-point. This allows the system to explore the local energy landscape before the field is decreased, settling the system into a new, potentially improved classical state.

Conceptual diagram of the reverse quantum annealing process used for mutation.

3. Selection

To maintain population diversity and prevent premature convergence, the authors employ implicit fitness sharing and Pareto selection. These mechanisms reward solutions that are both low-energy and structurally unique compared to the rest of the population.

Experimental Setup

The QAGA was evaluated on three classes of Ising spin-glass problems, each comprising approximately 2,000 variables mapped to the D-Wave "Chimera" hardware graph:

  • RAN1 (Bimodal Spin Glasses): Difficult for standard QA due to high state degeneracy.
  • AC3 (Anticluster Inputs): Designed with strong inter-tile connections to require more global search.
  • DCL (Deceptive Cluster Loops): Engineered to mislead classical solvers, requiring quantum tunneling to reach the global optimum.

Key Results and Discussion

The performance of QAGA was benchmarked against standard QA, Simulated Annealing (SA), and Parallel Tempering with Isoenergetic Cluster Moves (PT-ICM).

Time-to-solution (TTS) distributions across RAN1, AC3, and DCL problem instances for various solvers.

As shown in the results, QAGA demonstrates a significant advantage in specific problem domains. On DCL inputs, QAGA outperformed the best classical solver (PT-ICM) by over two orders of magnitude. On AC3 inputs, it maintained a lead of roughly one order of magnitude. While classical solvers remained superior for RAN1 inputs, QAGA significantly outperformed standard QA in all categories.

A critical observation is the reduction of the "heavy tail" in the time-to-solution (TTS) distribution. Standard QA often struggles with a small subset of extremely difficult instances; QAGA produces a much tighter distribution, making performance more predictable and reliable.

Conclusion

The QAGA demonstrates that quantum annealing is most effective when used as a sophisticated local search engine within a broader classical metaheuristic. By combining non-local classical moves (crossovers) with local quantum fluctuations (mutations), the hybrid approach overcomes the limitations of either method used in isolation. Future work will focus on reducing the wall-clock overhead associated with QPU programming and automating the tuning of the reverse annealing pause points to further enhance performance on NISQ devices.

Summary updated

Abstract

Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Reverse annealing enables the development of genetic algorithms that use quantum fluctuation for mutations and classical mechanisms for the crossovers -- we refer to these as Quantum-Assisted Genetic Algorithms (QAGAs). We describe a QAGA and present experimental results using a D-Wave 2000Q quantum annealing processor. On a set of spin-glass inputs, standard (forward) quantum annealing finds good solutions very quickly but struggles to find global optima. In contrast, our QAGA proves effective at finding global optima for these inputs. This successful interplay of non-local classical and quantum fluctuations could provide a promising step toward practical applications of Noisy Intermediate-Scale Quantum (NISQ) devices for heuristic discrete optimization.
BibTeX
@misc{king2019quantum,
  author = {James King and Masoud Mohseni and William Bernoudy and Alexandre Fréchette and Hossein Sadeghi and Sergei V. Isakov and Hartmut Neven and Mohammad H. Amin},
  title = {{Quantum-Assisted Genetic Algorithm}},
  year = {2019},
  eprint = {1907.00707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.00707},
}
Figure