Noise can speed Markov chain Monte Carlo estimation and quantum annealing

Carefully injected noise can speed the average convergence of Markov chain Monte Carlo (MCMC) estimates and simulated annealing optimization. This includes quantum annealing and the MCMC special case of the Metropolis-Hastings algorithm. MCMC seeks the solution to a computational problem as the equilibrium probability density of a reversible Markov chain. The algorithm must cycle through a long burn-in phase until it reaches equilibrium because the Markov samples are statistically correlated. The special injected noise reduces this burn-in period in MCMC. A related theorem shows that it reduces the cooling time in simulated annealing. Simulations showed that optimal noise gave a 76% speed-up in finding the global minimum in the Schwefel optimization benchmark. The noise-boosted simulations found the global minimum in 99.8% of trials compared with only 95.4% of trials in noiseless simulated annealing. Simulations also showed that the noise boost is robust to accelerated cooling schedules and that noise decreased convergence times by more than 32% under aggressive geometric cooling. Molecular dynamics simulations showed that optimal noise gave a 42% speed-up in finding the minimum potential energy configuration of an eight-argon-atom gas system with a Lennard-Jones 12-6 potential. The annealing speed-up also extends to quantum Monte Carlo implementations of quantum annealing. Noise improved ground-state energy estimates in a 1024-spin simulated quantum annealing simulation by 25.6%. The quantum noise flips spins along a Trotter ring. The noisy MCMC algorithm brings each Markov step closer on average to equilibrium if an inequality holds between two expectations. Gaussian or Cauchy jump probabilities reduce the noise-benefit inequality to a simple quadratic inequality. Simulations show that noise-boosted simulated annealing is more likely than noiseless annealing to sample high probability regions of the search space and to accept solutions that increase the search breadth.

Figure 1

Schwefel function $f\left(x\right)=419.9829d-{\sum }_{i=1}^d{x}_{i}sin\left(\sqrt{\left|x\right|}\right)$ is a $d$-dimensional optimization benchmark on the hypercube $-512\le x_i\le 512$ [30, 31, 32, 33]. It has a single global minimum $f\left(x_{min}\right)=0$ at $x_{min}=\left(420.9687,...,420.9687\right)$. Energy peaks separate irregular troughs on the surface. This leads to estimate capture in search algorithms that emphasize local search.

Figure 2

Time evolution of a two-dimensional (2D) histogram of MCMC samples from the 2D Schwefel function in Fig. 1. (a) The simulation has explored only a small region of the space after 1000 samples. The simulation has not sufficiently burned in. The samples remain close to the initial state because the MCMC random walk proposed new samples near the current state. This early histogram did not match the Schwefel density. (b) The 10 000 sample histogram better matched the target density but there were still large unexplored regions. (c) The 100 000 sample histogram shows that the simulation explored most of the search space. The tallest (red) peak shows that the simulation found the global minimum. The histogram peaks corresponded to energy minima on the Schwefel surface.

Figure 3

Noise increased the breadth of search for simulated-annealing sample sequences from a five-dimensional (projected to two dimensions) Schwefel surface with logarithmic cooling schedule. Noisy simulated annealing visited more local minima and quickly moved out of those minima that trapped nonnoisy SA. Both figures show sample sequences with initial condition $x_0=\left(0,0\right)$ and $N={10}^6$. The red circle (lower left) locates the global minimum at $x_{min}=\left(-420.9687,-420.9687\right)$. (a) The noiseless algorithm found the $\left(205,205\right)$ local minimum within the first 100 time steps. Thermal noise did not induce the noiseless algorithm to search the space beyond three local minima. (b) The noisy simulation followed the noiseless simulation at the simulation start. It also sampled the same regions but in accord with Algorithm 2. The noise injected in accord with Theorem t7 both enhanced the thermal jumps and increased the breadth of the simulation. The noise-injected simulation visited the same three minima as in (a) but it performed a local optimization for only a few hundred steps before it jumped to the next minimum. The estimate settled at $\left(-310,-310\right)$. This was just one hop away from the global minimum $x_{min}$.

Figure 4

MCMC noise benefit for an MCMC molecular dynamics simulation of eight argon atoms. Noise decreases the convergence time for an MCMC simulation to find the energy minimum by 42%. The plot shows the number of steps that an MCMC simulation needed to converge to the minimum energy in an eight-argon-atom gas system. The optimal noise had a standard deviation of 0.56. The plot shows 100 noise levels with variance noise powers that range between 0 (no noise) and ${\sigma }^2=3$. Each point averaged 200 simulations and shows the average number of MCMC steps required to estimate the minimum to within 0.01. The Lennard-Jones 12-6 model described the interaction between two argon atoms with $\epsilon =1.654\times {10}^{-21}\text{J}$ and $\sigma =3.405\times {10}^{-10}\text{m}=3.405\AA$ [41].

Figure 5

The Lennard-Jones 12-6 potential well approximating pairwise interactions between two neutral atoms. The figure shows the energy of a two-atom system as a function of the interatomic distance. The well results from two competing atomic effects: (1) overlapping electron orbitals causing strong Pauli repulsion to push the atoms apart at short distances and (2) van der Waals and dispersion attractions pulling the atoms together at longer distances. Three parameters characterize the potential: (1) $\epsilon$ is the depth of the potential well, (2) $r_m$ is the interatomic distance corresponding to the minimum energy, and (3) $\sigma$ is the zero-potential interatomic distance. Table 1 lists parameter values for argon.

Figure 6

Simulated-annealing noise benefits with a five-dimensional Schwefel energy surface and a logarithmic cooling schedule. Noise improved three distinct performance metrics when using Algorithm 2. (a) Noise reduced convergence time by 76%. We defined convergence time as the number of steps the simulation took to estimate the global minimum energy with error $<{10}^{-3}$. Simulations with faster convergence will in general find better estimates given the same computational time. (b) Noise improved the estimated minimum system energy by two orders of magnitude in simulations with a fixed run time ($t_{max}={10}^6$). Figure 3 shows how the estimated minimum corresponds to samples. Noise increased the breadth of the search and pushed the simulation to make good jumps toward new minima. (c) Noise decreased the likelihood of failure in a given trial by almost 100%. We defined a simulation failure if it did not converge by $t={10}^7$. This was about 20 times longer than the average convergence time. 4.5% of noiseless simulations failed. The simulation produced no sign of failure except an increased estimated variance between trials. Noisy simulated annealing produced only two failures in 1000 trials (0.2%).

Figure 7

Noise benefits decreased convergence time under accelerated cooling schedules. Simulated annealing algorithms often use accelerated cooling schedules such as exponential cooling $T_{\exp }\left(t\right)=T_0{A}^t$ or geometric cooling $T_{\mathrm{geom}}\left(t\right)=T_{0}exp\left(-A{t}^{1/d}\right)$ where $A<1$ and $T_0$ are user parameters and $d$ is the sample dimension. Accelerated cooling schedules do not have convergence guarantees as do log cooling $T_{\log }\left(t\right)=ln\left(t+1\right)$ but often provide better estimates given a fixed run time. Noise enhanced simulated annealing reduced convergence time under an (a) exponential cooling schedule by 40.5% and under a (b) geometric cooling schedule by 32.8%.

Figure 8

Quantum annealing (QA) uses quantum tunneling to burrow through energy peaks (yellow). Classical simulated annealing (SA) instead generates a sequence of states to scale the peak (blue). The figures shows that a local minimum has trapped the estimate (green). SA would require a sequence of unlikely jumps to scale the potential energy hill. This may not be realistic at low SA temperatures. So the estimate gets trapped in the suboptimal valley. QA uses quantum tunneling to burrow through the mountain. This explains why QA can give better estimates than SA gives while optimizing complex potential energy surfaces that contain many high energy states.

Figure 9

The noisy quantum annealing algorithm propagates noise along a Trotter ring. The algorithm inspects the local energy landscape after each time step. It then injects noise by conditionally flipping the spin of neighbors. These spin flips diffuse the noise across the network because quantum correlations between neighbors encourage convergence to the optimal solution.

Figure 10

Simulated quantum annealing noise benefit in a 1024 Ising spin simulation. The pink line shows that noise improved the estimated ground-state energy of a $32\times 32$ spin lattice by 25.6%. The plot shows the ground state energy after 100 path-integral Monte Carlo steps. The true ground state energy (red) was $E_0=-1591.92$. Each plotted point shows the average calculated ground state from 100 simulations at each noise power. The blue line shows that blind (independent and identically distributed sampling) noise did not benefit the simulation. Blind noise only made the estimates worse. So the N-MCMC noise-benefit condition is central to the S-QA noise benefit.