Dual time scales in simulated annealing of a two-dimensional Ising spin glass

We apply a generalized Kibble-Zurek out-of-equilibrium scaling ansatz to simulated annealing when approaching the spin-glass transition at temperature $T=0$ of the two-dimensional Ising model with random $J=\pm 1$ couplings. Analyzing the spin-glass order parameter and the excess energy as functions of the system size and the annealing velocity in Monte Carlo simulations with Metropolis dynamics, we find scaling where the energy relaxes slower than the spin-glass order parameter, i.e., there are two different dynamic exponents. The values of the exponents relating the relaxation time scales to the system length, $\tau \sim L^z$, are $z=8.28\pm 0.03$ for the relaxation of the order parameter and $z=10.31\pm 0.04$ for the energy relaxation. We argue that the behavior with dual time scales arises as a consequence of the entropy-driven ordering mechanism within droplet theory. We point out that the dynamic exponents found here for $T\to 0$ simulated annealing are different from the temperature-dependent equilibrium dynamic exponent $z_{\mathrm{eq}}\left(T\right)$, for which previous studies have found a divergent behavior: $z_{\mathrm{eq}}(T\to 0)\to \infty$. Thus, our study shows that, within Metropolis dynamics, it is easier to relax the system to one of its degenerate ground states than to migrate at low temperatures between regions of the configuration space surrounding different ground states. In a more general context of optimization, our study provides an example of robust dense-region solutions for which the excess energy (the conventional cost function) may not be the best measure of success.

Figure 1

Convergence of PT results of the EA order parameter (a) and the excess energy (b) vs the number of sweeps for two system sizes. The lowest temperature was $T_0=0.1$ and $T_0=0.06$ for $L=16$ and 24, respectively, and in both cases the temperature spacing was ${\mathrm{\Delta }}_T=0.02$. The results represent averages over more than ${10}^5$ samples for both system size.

Figure 2

Temperature dependence of the squared EA order parameter for $L=24$ in PT simulations with ${10}^6$ sweeps for both equilibration and data collection.

Figure 3

Equilibrium results for (a) the ground-state energy graphed vs $L^{-2}$ and (b) the EA order parameter vs $L^{-1/2}$. In (a) the results for $L=14-32$ were fitted to $E_0=-1.401938$ [36] plus a correction $a{L}^{-2}$ with $a=1.230\left(2\right)$. The inset shows data for the larger systems on a more detailed scale (where the error bars are similar to the symbol size). In (b), there are significant even-odd effects and $L\ge 9$ data for even (blue circles) and odd (red squares) $L$ have been individually fitted to constants plus $L^{-1/2}$ corrections.

Figure 4

(a) EA order parameter squared vs the velocity in linear ($r=1$) SA runs for different system sizes. (b) Velocity scaling, where $\langle q^2\rangle$ has been rescaled by the size correction, $\langle q_{\mathrm{res}}^2\rangle =\langle q^2\rangle /(a+b{L}^{-1/2})$ with $a$ and $b$ the constants of the even-$L$ fit in Fig. 3, and the horizontal axis has been scaled with the optimal exponent $z+{\mathrm{\Theta }}_S=8.83\left(4\right)$ (obtained with a data-collapse procedure using many system sizes between $L=32$ and 128). The line has the expected slope $-2/(z+{\mathrm{\Theta }}_S)$ in the power-law scaling regime. (c) The same data scaled according to the third line of Eq. (15) along with a line with the same slope as in (b).

Figure 5

The KZ scaling exponent vs the exponent $r$ in the SA protocol Eq. (3), along with a fit giving $z=8.28\left(3\right)$ and ${\mathrm{\Theta }}_S=0.55\left(6\right)$. The $r=1$ point was obtained using the data analysis in Fig. 4 and similar data for $r=2$ and $r=4$ are presented in Appendix pp2.

Figure 6

Mean energy above the infinite-size ground-state energy $E_0$ in $r=1$ SA runs. The results have been divided by the $L^{-2}$ equilibrium size-dependence and the horizontal axis was rescaled according to the generalized KZ hypothesis Eq. (13), with $\kappa {\mathrm{\Theta }}_S=2$ and the optimum-collapse value $z^{\prime }+{\mathrm{\Theta }}_S=10.80\left(8\right)$ of the scaling exponent. The line shows the expected slope $2/(z^{\prime }+{\mathrm{\Theta }}_S)$ in the power-law regime.

Figure 7

Generalized KZ scaling analysis of the kind presented in Figs. 4 and 6 but for smaller systems for which the crossover toward equilibrium can be more clearly observed. The velocity scaling exponents are $\sigma =z+{\mathrm{\Theta }}_s=9.01$ and ${\sigma }^{\prime }=z^{\prime }+{\mathrm{\Theta }}_S=10.8$ for the EA order parameter (upper panel) and the excess energy (lower panel), respectively. The lines have slopes $2/\sigma$ and $2/{\sigma }^{\prime }$, corresponding to the expected exponents in the power-law scaling regime.

Figure 8

Scaling of the minimum energy reached during any time in $r=1$ SA runs for $L=8,16,24,32,48,64,72,96,128$. The exponents used for the rescaling of both the axes are the same as those in Fig. 6. The solid line has the expected slope $2/(z^{\prime }+{\mathrm{\Theta }}_S)$ and is drawn in close proximity to the data for the largest system sizes. The dashed line has the same parameters as the line in Fig. 6.

Figure 9

Scaling function for the mean energy and the mean lowest energy in $r=1$ SA runs. Data points $(v,L)$ for system sizes in the range $L=8$ to 128 were used, for each size excluding $v$ points that deviate from the common data collapsed form. The value of the scaling exponent is the same as in Fig. 6: $z^{\prime }+{\mathrm{\Theta }}_s=10.8$.

Figure 10

Conceptual illustration of the essential features of the energy landscape of the $J=\pm 1$ model, as suggested by droplet theory and our study. Ground states (red solid circles) are clustered and typical states fall within a small region (large circle) of the configuration space. Low-energy excitations (black open circles) are predominantly located in the same region.

Figure 11

Conceptual one-dimensiomal analog of our proposal for the difference between equilibrium and nonequilibrium dynamics of the spin glass. In the equilibrium at low temperatures, the slowest dynamic time scale corresponds to fluctuations between regions surrounding different low-energy states. In a nonequilibrium SA simulation, at some point the system locks into one such funnel. The dynamic order-parameter exponent $z$ characterizes the process of reaching a funnel, while the energy exponent $z^{\prime }$ governs the eventual relaxation to the bottom of the funnel.

Figure 12

Example for $r=1$ of the goodness of the linear fit of $ln\langle q_{\mathrm{res}}^2\rangle$ versus $ln\left(v{L}_r^{\sigma }\right)$ when the slope of the line is fixed at $-2/\sigma$. The data used here is shown as the middle set (triangles) in Fig. 13. A scan is performed as a function of the exponent $\sigma =z+{\mathrm{\Theta }}_s$ and the minimum of ${\chi }^2$ is identified for the optimum $\sigma$.

Figure 13

Three different rescaled sets of data (indicated by different shapes of the graph symbols) obtained by bootstrap sampling of a large number of data bins for system sizes $L=72$ (black), 80 (red), and 96 (blue). The three lines are the best fits to the form $ln\langle q_{\mathrm{res}}^2\rangle =-(2/\sigma )ln\left(v{L}^{\sigma }\right)+b$, and the values of $\sigma ,b$ shown for each case corresponds to a ${\chi }^2$-minimum such as the one in Fig. 12.

Figure 14

The exponent $\sigma \left(r\right)$ for $r=1,2,4$ along with a fit to the form Eq. (17). The individual exponents (fitting parameters) are $z=8.35\left(7\right)$, and ${\mathrm{\Theta }}_S=0.42\left(8\right)$, where the error bars were computed by repeated fits with Gaussian noise added [with standard deviation equal to the error bars on $\sigma \left(r\right)$].

Figure 15

Scaling collapse of the EA order parameter for $r=2$ and $r=4$. The scaling exponents are $\sigma (r=2)=8.57\left(3\right)$ and $\sigma (r=4)=8.42\left(2\right)$.

Figure 16

Scaling collapse of the excess energy for $r=2$ and $r=4$. The scaling exponents are ${\sigma }^{\prime }(r=2)=10.57\left(10\right)$ and ${\sigma }^{\prime }(r=4)=10.44\left(6\right)$.