Optimization by a quantum reinforcement algorithm

A reinforcement algorithm solves a classical optimization problem by introducing a feedback to the system, which slowly changes the energy landscape and converges the algorithm to an optimal solution in the configuration space. Here, we use this strategy to concentrate (localize) the wave function of a quantum particle, which explores the configuration space of the problem, preferentially on an optimal configuration. We examine the method by solving numerically the equations governing the evolution of the system, which are similar to the nonlinear Schrödinger equations, for small problem sizes. In particular, we observe that reinforcement increases the minimal energy gap of the system in a quantum annealing algorithm. Our numerical simulations and the latter observation show that such kind of quantum feedback might be helpful in solving a computationally hard optimization problem by a quantum reinforcement algorithm.

Figure 1

Success probability $P_{\mathrm{opt}}$ of the algorithms for different number of spins $\left(N\right)$ in the SK model. (a)–(c) show the results obtained by the quantum annealing (QA), quantum reinforcement (QR), and reinforced quantum annealing (rQA) algorithms. (d)–(f) compare the results obtained by the QR algorithm for different initial conditions and the local quantum reinforcement (lQR) algorithm. (g)–(i) display the percentile values of the success probability at the end of the process $\left(t=T\right)$. The initial states are indicated by $(\times )$ for the equal superposition of all spin configurations, and (+) for the all-positive spin configuration. The data are results of 2000 independent realizations of the random spin model. The statistical errors are about 0.01. For the $\text{QA}(\times )$ we used $\mathrm{\Gamma }=0.3$ (a), (b), (g), (h) and $\mathrm{\Gamma }=0.5$ (c), (i). For the $\text{QR}(\times )$ we used $\mathrm{\Gamma }=0.8,r_0=1$ (a), (g), $\mathrm{\Gamma }=1.2,r_0=1$ (b), (h), $\mathrm{\Gamma }=1.3,r_0=0.5$ (c), (f), (i), $\mathrm{\Gamma }=1,r_0=2.5$ (d), and $\mathrm{\Gamma }=1.5,r_0=2.5$ (e). For the $\text{rQA}(\times )$ we used $\mathrm{\Gamma }=0.5,r_0=1$ (a), $\mathrm{\Gamma }=0.9,r_0=1$ (b), and $\mathrm{\Gamma }=1.2,r_0=1$ (c). For the QR(+) we used $\mathrm{\Gamma }=3,r_0=3.5$ (d), $\mathrm{\Gamma }=2.5,r_0=2.5$ (e), and $\mathrm{\Gamma }=2.5,r_0=2.0$ (f). For the $\text{lQR}(\times )$ we used $\mathrm{\Gamma }=3,r_0=1$ (d), $\mathrm{\Gamma }=3.5,r_0=0.5$ (e), and $\mathrm{\Gamma }=2.5,r_0=0.2$ (f).

Figure 2

Success probabilities $P_{QR},P_{QA}$ of the QR and QA algorithms in the SK model. (a) $P_{QR}\left(T\right)$ vs $P_{QA}\left(T\right)$ at the end of the process $t=T$ for 2000 independent realizations of the problem. The parameters and initial conditions are similar to the ones in Fig. 1. (b) Comparing the percentile values of the success probability in the one- and two-stage quantum reinforcement algorithms $({\mathrm{QR}}_1,{\mathrm{QR}}_2)$ starting from the equal superposition of all the spin states. The parameters in the two stages are $r_1\left(t\right)=0.5(t/T)2^N,{\mathrm{\Gamma }}_1=1.3$ and $r_2\left(t\right)=r_1\left(t\right)+0.15,{\mathrm{\Gamma }}_2={\mathrm{\Gamma }}_1$ with $T=5N$ for each stage. Here ex-${\mathrm{QR}}_1$ denotes the one-stage QR algorithm with parameters $r\left(t\right)=0.5(t/T)(1-t/T)2^N,\mathrm{\Gamma }\left(t\right)=2(1-t/T)$, which go to zero at the end of the process. The data are results of 2000 independent realizations of the random spin model.

Figure 3

Time evolution of the two-level system in the quantum reinforcement algorithm. (a) The probabilities ${\left|\psi (-;t)\right|}^2$ and ${\left|\psi (+;t)\right|}^2$, and (b) the effective energy $E(\sigma ;t)=h\sigma -{r\left(t\right)\left|\psi (\sigma ;t)\right|}^2$. The parameters are $h=\mathrm{\Gamma }=1$, and $r\left(t\right)=2(t/T)$ with $T=5$.

Figure 4

(a) The energy gap of the two-level system $\mathrm{\Delta }E\left(h\right)$ for different values of $\mathrm{\Gamma }$ and $r$ in the reinforced Hamiltonian $H_R^{\left(2\right)}$. (b) Energy gap of the local reinforced Hamiltonian for given values of $\mathrm{\Gamma }$ and $r$. (c) Time dependence of the energy gap $\mathrm{\Delta }E\left(t\right)$ for given values of $h,\mathrm{\Gamma }$, and $r$ in the quantum annealing (QA), reinforced quantum annealing (rQA), and the local version of reinforced quantum annealing (rQA-local).

Figure 5

The energy gap of the SK model in presence of random fields in the quantum annealing (QA) and reinforced quantum annealing (rQA) with $r_0=1$. (a) The average energy gap $\mathrm{\Delta }E\left(t\right)$ vs the evolution time, and (b) the percentile values of the minimum energy gap $\mathrm{\Delta }{E}_{min}$, for a given number of spins $N$ and $\mathrm{\Gamma }$. (c) The average of the minimal energy gap encountered in the annealing process, and (d) the percentile values of $\mathrm{\Delta }{E}_{min}$, vs the number of spins. The data are results of 2000 independent realizations of the random model.