Genetic optimization of quantum annealing

The study of optimal control of quantum annealing by modulating the pace of evolution and by introducing a counterdiabatic potential has gained significant attention in recent times. In this work, we present a numerical approach based on genetic algorithms to improve the performance of quantum annealing, which evades the Landau-Zener transitions to navigate to the ground state of the final Hamiltonian with high probability. We optimize the annealing schedules starting from the polynomial ansatz by treating their coefficients as chromosomes of the genetic algorithm. We also explore shortcuts to adiabaticity by computing a practically feasible $k$-local optimal driving operator, showing that even for $k=1$ we achieve substantial improvement of the fidelity over the standard annealing solution. With these genetically optimized annealing schedules and/or optimal driving operators, we are able to perform quantum annealing in relatively short timescales and with higher fidelity compared to traditional approaches.

Figure 1

Cartoon of our genetic algorithm. (a) The free parameters of the annealing schedules are stored in a chromosome. (b) We first randomly generate $N_{\text{pop}}$ individuals. (c) Then random gene mutation occurs in each individual. (d) Then we apply two individual crossovers. (e) We select the fittest individuals and start again from (c) until convergence. The azure bars identify the fitness values: the larger the better.

Figure 2

Summary of the results obtained by using the optimized annealing schedules for solving the $p$-spin model using SOGAs: (a) instantaneous energy gaps during the dynamics of the adiabatic evolution, (b) instantaneous ground-state probability using the optimized schedules and using a simple linear schedule, (c) annealing schedules $A\left(s\right)$ and $B\left(s\right)$, and (d) histogram of the fidelities for 50 runs of the algorithm. We investigate the system with 15 spins with both annealing schedules $A\left(s\right)$ and $B\left(s\right)$ expanded up to a degree of 3. In other words, $k_a=k_b=2$.

Figure 3

Box plot of fidelities of the states of systems with different sizes. Each box represents the first quartile and the third quartile and the red (gray) dashed line represents the median of the data for 50 runs of the SOGA which optimizes the annealing schedules $A\left(s\right)$ and $B\left(s\right)$, each of which is expanded up to a third-degree polynomial.

Figure 4

Results obtained by optimizing the time-independent part of the local OD operator for the ferromagnetic $p$-spin model with 15 spins and $p=3$. The OD operator chosen is $H_{\text{OD}}{(s,\gamma )}_{d=3}$. The plots depict the data for 50 runs of the SOGA and the corresponding results obtained by adiabatic quantum computation. (a) Instantaneous energy gaps between the ground state and the first excited state. (b) Instantaneous ground-state probabilities. (c) Histogram of the fidelities for 50 instances.

Figure 5

Box plot of fidelities of the states of systems with different sizes. Each box represents the data for 50 runs of the SOGA iterated for 1000 generations, which optimizes the time-independent part of the OD operator with $d=3$.

Figure 6

Results obtained by optimizing the annealing schedules $A\left(s\right)$ and $B\left(s\right)$ and time-dependent local OD operator for the ferromagnetic $p$-spin model with 15 spins and $p=3$. The OD operator chosen is $H_{\text{OD}}{(s,\gamma )}_{d=3}, k_a=k_b=2$, and $k_c=3$. The plots depict the data for 50 runs of the SOGA and the corresponding results obtained by adiabatic evolution. (a) Instantaneous energy gaps between the ground state and the first excited state. (b) Instantaneous ground-state probabilities. (c) Time schedule functions $A\left(s\right), B\left(s\right)$, and $C\left(s\right)$. (d) Histogram of the fidelities for 50 instances.

Figure 7

Box plot of fidelities of the states of systems with different sizes. Each box represents the data for 50 runs of the SOGA iterated for 1000 generations, which optimizes the annealing schedules $A\left(s\right)$ and $B\left(s\right)$ and the scheduling of the local OD operator [$H_{\text{OD}}{(s,\gamma )}_{d=3}$], with $k_a=k_b=2$ and $k_c=3$.

Figure 8

Graph of the Ising model discussed in Sec. 5

Figure 9

Results of genetic optimization of quantum annealing of a random Ising model [Eq. (13)] for a typical random instance. The plot shows the data of 30 genetic optimizations of the considered random instance. (a)–(c) Optimization of annealing schedules alone, with the parameters $k_a=k_b=3$: (a) instantaneous total probability of obtaining degenerate ground states using optimized polynomial schedules vs using linear schedules, (b) optimized annealing schedules $A\left(s\right)$ and $B\left(s\right)$, and (c) approximation ratios of 30 genetic optimizations of the given random instance. (d)–(f) Corresponding results obtained by optimizing annealing schedules and the OD operator [$H_{\text{OD}}{(s,\gamma )}_{d=3}$] together. The parameters considered in this case are $k_a=k_b=2$ and $k_c=3$.

Figure 10

Median approximation ratio distribution for $N_{\text{inst}}=50$ random instances over $N_{\text{rep}}=30$ repetitions of the SOGA for each instance. The histogram shows the approximation ratios of the traditional quantum annealing protocol. The inset shows the corresponding approximation ratios of quantum annealing with optimized time schedules and quantum annealing with optimized annealing schedules and the OD operator.

Figure 11

Results of the optimization of the local OD operator with 3-local operators for a $p$-spin model with 40 spins and $p=3$. We compare the performances of (a) SOGAs and (b) MOGAs. The red (dark gray) bold solid lines in the solutions obtained from SOGAs indicate the solutions where there are energy-level crossings. The corresponding results using MOGAs do not show this kind of solution.