Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm

The standard quantum annealing algorithm tries to approach the ground state of a classical system by slowly decreasing the hopping rates of a quantum random walk in the configuration space of the problem, where the on-site energies are provided by the classical energy function. In a quantum reinforcement algorithm, the annealing works instead by increasing gradually the strength of the on-site energies according to the probability of finding the walker on each site of the configuration space. Here, by using the path-integral Monte Carlo simulations of the quantum algorithms, we show that annealing via reinforcement can significantly enhance the success probability of the quantum walker. More precisely, we implement a local version of the quantum reinforcement algorithm, where the system wave function is replaced by an approximate wave function using the local expectation values of the system. We use this algorithm to find solutions to a prototypical constraint satisfaction problem (XORSAT) close to the satisfiability to unsatisfiability phase transition. The study is limited to small problem sizes (a few hundreds of variables), nevertheless, the numerical results suggest that quantum reinforcement may provide a useful strategy to deal with other computationally hard problems and larger problem sizes even as a classical optimization algorithm.

Figure 1

Comparing the success probabilities $P_{\text{success}}$ of the standard quantum annealing (QA) algorithm and the local quantum reinforcement (1-lQR) algorithm. The algorithm parameters, unless mentioned otherwise, are $N_s=20$, $\beta =30$, $\mathrm{\Gamma }=2$, $t_{\text{max}}=200$, $t_{\text{eq}}=100$ with $t_{\text{av}}=t_{\text{eq}}/2$ and $\delta r=0.002$ for the QR algorithm. $P_{\text{success}}$ vs (a) the number of variables $N$, (b) the number of imaginary-time slices $N_s$, (c) the maximum number of time steps $t_{\text{max}}$, and (d) the equilibration time $t_{\text{eq}}$. The data are obtained from (depending on the problem size) 2000 to 10 000 runs of the algorithm on independent realizations of the problem.

Figure 2

Success probabilities of the 1-local QR algorithm. $P_{\text{success}}$ vs the problem size $N$ for different (a) transverse fields $\mathrm{\Gamma }$, (b) inverse temperatures $\beta$, and (c) rates of increasing the reinforcement parameter. The algorithm parameters are $N_s=20$, $t_{\text{max}}=100$, $t_{\text{eq}}=500$, $t_{\text{av}}=400$, $\mathrm{\Gamma }=2$, $\beta =30$, and $\delta r=0.002$, unless it is explicitly mentioned.

Figure 3

The algorithms performances for larger real and imaginary times. Here, $t_{\text{max}}=400$, $N_s=60$, $\beta =90$, $\mathrm{\Gamma }=2$, and $t_{\text{eq}}=500$. The success probability (a) and the percentile value of the computation time (number of time steps) in the 1-lQR and K-lQR algorithms for $N=200$ (b), and $N=240$ (c). In the QR algorithms $\delta r=0.001$ and $t_{\text{av}}=400$. The computation times are obtained from 2000 independent problem instances.

Figure 4

Success probability of the classical reinforced BP algorithm. $P_{\text{success}}$ for different (a) rates of increasing the reinforcement parameter $\delta r$, (b) damping parameters $\lambda$ in updating the messages, and (c) noise levels $\delta h$ in the external fields to break the problem symmetry. The data are obtained from ${10}^4$ runs of the algorithm on independent realizations of the problem. The maximum number of iterations is $t_{\text{max}}={10}^5$. The other parameters (if not fixed) are $\delta r=0.0001$, $\lambda =0.5$, $\delta h=0.001$.