{'fraction_non_alphanumeric': 0.03693556570268899, 'fraction_numerical': 0.010248604769152715, 'mean_word_length': 4.270320855614973, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A comparison of classical and quantum annealing dynamics

Simulated annealing and quantum annealing are algorithms for combinatorial optimization problems. The former brings solutions using thermal fluctuations and through classical dynamics, while the latter does using quantum fluctuations and through quantum dynamics. In this paper, dynamics of these two algorithms are compared by means of the Kibble-Zurek argument, employing a one-dimensional random Ising model as an exercise for algorithms. We reveal that quantum annealing reduces residual errors faster than simulated annealing with decreasing annealing rate. The result implies the advantage of quantum annealing over simulated annealing.


Introduction
Physics has inspired algorithms of computation. A celebrated example is simulated annealing [1]. Simulated annealing is an algorithm for general combinatorial optimization problems. In simulated annealing, we consider a system representing the problem and put it in finite temperature. The problem is translated into finding the ground state of the system. To this end, we initially require that the temperature is sufficiently high. It is easy to obtain the equilibrium state of the system in high temperature. Suppose that the system is in the equilibrium initially. Then we lower the temperature toward zero according to a certain schedule. If the speed of temperature change is slow enough, the system maintains equilibrium state and reaches the ground state when the temperature becomes zero. We thus obtain the solution. Obviously simulated annealing produces the solution through the physical dynamics of the classical statistical mechanics. The idea of simulated annealing has developed into more elaborate algorithm such as the parallel tempering [2,3] these days.
Algorithms using quantum mechanics have also attracted a lot of attentions. Quantum annealing is one of quantum mechanical algorithms for general combinatorial optimization problems [4,5,6,7,8,9,10]. Instead of thermal fluctuations in simulated annealing, quantum annealing introduces quantum fluctuations. If the problem is encoded in the interacting Isingspin model, quantum fluctuations are induced by the transverse field typically. We note that the Hamiltonian of the transverse field and that of Ising spins do not commute. We assume that the transverse field is strong enough initially and the initial state is the ground state of the initial Hamiltonian. The ground state of the system with strong transverse field is easily obtained. Then we lower the transverse field gradually with time. The time evolution of the state is governed by the Schrödinger's dynamics. If the change of the transverse field is slow enough, the state evolves adiabatically and reaches the ground state of the Ising model when the transverse field vanishes. Quantum annealing produces the solution using quantum fluctuations through the dynamics of quantum mechanics.
One may hold a hope that quantum mechanics is outstanding from classical mechanics in the search of the ground state of classical system. Several studies have compared simulated annealing and quantum annealing numerically [11,12,13,14] and experimentally [15]. Most of them have reported results in favor of the advantage of quantum annealing. However we have had no analytic evidence that shows the outstanding power of quantum annealing over simulated annealing. To understand the feature of algorithms deeply, it is significant to reveal the difference between quantum annealing and simulated annealing analytically. The purpose of this paper is to provide an analytical evidence that quantum annealing has an advantage over simulated annealing.
In order to discuss dynamics of the system with time-dependent parameter, one has to care about the phase transition. In both simulated annealing and quantum annealing, the initial state is a disordered state and the target ground state is usually a state with a certain order. The phase transition lies between the initial state and the target state. If the temperature is lowered, it is the thermal phase transition. If the transverse field applied to the Ising model is weakened, the quantum phase transition takes place. The state evolved from the disordered state cannot become the ordered state completely as far as the parameter is changed with finite rate. This is because the characteristic time diverges at the critical point. Thus the final state inevitably contains spatial defects. This mechanism of the defect formation is called the Kibble-Zurek mechanism [19,20]. We explain the Kibble-Zurek mechanism in the next section more in detail. Errors of simulated annealing and quantum annealing are associated with the Kibble-Zurek mechanism. In our study, we compare errors of simulated annealing and quantum annealing estimated by means of the argument for the Kibble-Zurek mechanism.
The model we employ is the random ferromagnetic Ising model in one dimension: where we assume that the coupling constant J i is drawn from the uniform distribution between 0 and 1, namely The ground state of this model is the complete ferromagnetic state. However the first excited state reflects the randomness. Hence this model is trivial as the optimization problem but possesses non-trivial dynamics. In our model, the error of the obtained state can be measured by density of kinks: as well as residual energy per spin: where N (→ ∞) is the number of spins and · · · denotes the expectation value with respect to the state after simulated or quantum annealing. We remark that 1 2 in eq. (4) stands for the minus of the true ground energy per spin.
Quantum annealing dynamics of the present model has been studied by Dziarmaga on the basis of the Kibble-Zurek mechanism a couple of years ago [16]. He revealed that density of kinks decays with annealing rate 1/τ of the transverse field as for large τ . Caneva et al. [17] arrived at the same result by the Landau-Zener formula and scaling of the distribution of energy gaps at the quantum critical point. In ref. [17], the decay rate of residual energy is also estimated numerically. Numerical result for large τ is written as As for simulated annealing of the same model, the author of the present paper revealed on the basis of the Kibble-Zurek mechanism that density of kinks decays as and residual energy per spin as for large τ [23]. The result of residual energy is the reproduction of the Huse-Fisher's law [18]. Comparison of residual energies, eqs. (6) and (8), might indicate the advantage of quantum annealing. However some ambiguity remains since analytic result has not obtained for quantum annealing. Comparing density of kinks after quantum annealing and that after simulated annealing, it is obvious that the former decays faster than the latter. This result gives a firm evidence that quantum annealing has an advantage over simulated annealing. The organization of the paper is as follows. We first explain the argument of the Kibble-Zurek mechanism in the next section. Then, according to ref. [16], we apply the Kibble-Zurek argument to quantum annealing of one-dimensional random Ising ferromagnet in sec. 3. We obtain the decay rate of density of kinks, eq. (5). Dynamics of simulated annealing is studied in sec. 4. We derive density of kinks and residual energy, eqs. (7) and (8), by means of the Kibble-Zurek argument. We also present the confirmation of analytic results by the Monte-Carlo simulation. The paper is concluded in sec. 5.

Kibble-Zurek argument
Let us consider a uniform Ising ferromagnet. We suppose that a parameter γ specifies static state of the system. It corresponds to the temperature or the transverse field. We assume that the static state exhibits the phase transition at γ = γ c . The order parameter of the system is zero for γ > γ c , while it is finite and uniform for γ < γ c . In the argument of the Kibble-Zurek mechanism, the correlation length and the characteristic (relaxation) time at fixed γ are important quantities. We write the correlation length and the characteristic time as ξ(γ) and τ r (γ) respectively. These quantities grow with decreasing γ toward γ c and diverge at γ c . Now we consider dynamics which follows quenching γ with time from γ > γ c to γ < γ c . We assume that γ is quenched linearly with time. As the initial condition, we assume that the system is in the static (equilibrium or ground) state of γ. Starting from the initial state, the state evolves with decreasing γ. If γ is still large enough, the state should maintain the static state of γ since the characteristic time τ r is small. However, as γ comes close to γ c , γ decreases further before the state attains the static state of γ. Hence the state cannot evolve into the static state of γ when γ comes below γ c as far as the quenching rate is finite. It follows that, after the evolution, the order parameter is not uniform and ferromagnetic domains are formed. This is the Kibble-Zurek mechanism of spatial defects formation.
In the Kibble-Zurek argument, one can derive the relation between the mean size of ferromagnetic domains and the quenching rate. We assume linear quenching of γ and introduce the dimensionless parameter as follows, where t is time and 1/τ is the quenching rate of γ. Time t is assumed to go forward from −∞ to τ . We here pose an equation: This equation defines the timet at which the characteristic time is equal to the remaining time to the critical point. Since the characteristic time is longer than the remaining time to the critical point, the system cannot attain the static state of γ(t) for t >t. We then assume that the state maintains the static state for t <t and the evolution of the state stops at t =t. This state possesses a finite correlation length. Hence this state consists of ferromagnetic domains.
Once the domain structure forms, it could scarcely develop into the complete ferromagnetic state. Therefore it is reasonable to consider that the state remains the state at t =t until t = τ . Thus the size of domain of the final state is estimated by the correlation length at γ =γ ≡ γ(t), namely ξ(γ) ≡ξ.
It is instructive to consider the standard phase transition of second order. Using the critical exponents ν and z, the correlation length and characteristic time obey the power law near the critical point: ξ ∼ | | −ν and τ r ∼ ξ z ∼ | | −zν , where dispensable factors are omitted. Applying the relation of τ r and eq. (9) to eq. (10), we obtain the equation ofˆ ≡ (t):ˆ −zν ∼ˆ τ , where we supposed thatt is negative and henceˆ is positive. It follows thatˆ ∼ 1/τ 1/(1+zν) . Using the relation between ξ and , we obtainξ ∼ τ ν/(1+zν) . Thus the domain size of the state after evolution obeys the power law of τ and its exponent is determined by z and ν.

Quantum annealing
In this section we derive the decay rate of density of kinks after quantum annealing of the random Ising ferromagnet in one dimension. Let us consider the following quantum Ising model: where H 0 is the Ising Hamiltonian defined by eq. (1) with replacing σ i by σ z i . σ x i and σ z i are the Pauli's spin operators at site i. h i is a positive factor randomly chosen from [0, 1]. It has been known that this model exhibits the quantum phase transition at Γ = Γ c = 1. We define here the dimensionless field ≡ (Γ − 1). According to the Fisher's analysis by the renormalization group, the correlation length behaves as and the characteristic time as where ξ 0 and τ 0 are the critical amplitudes. Note that the anomalous dynamical exponent, z = 1/2| |, represents the universality of the random system. Now we suppose that the transverse field is quenched linearly with time and with rate τ as eq. (9). According to the Kibble-Zurek argument, we pose eq. (10). Then we obtain the equation ofˆ as where we definedˆ by that satisfies this equation. For τ /τ 0 1, sinceˆ 1, the equation is reduced to 1 ln 1 ≈ ln τ τ 0 . The solution of this equation is approximately As mentioned in the previous section, the correlation length of the state after evolution is estimated byξ = ξ(ˆ ). From eqs. (12) and (15), we obtain The inverse of the correlation length is almost the same as the density of kinks in the state. Hence the density of kinks after quantum annealing is written as Thus, ignoring the double logarithm in the numerator, one obtains eq. (5). The decay rate of density of kinks derived here has been confirmed by the numerical simulation using the Jordan-Wigner transformation [16,17].

Simulated annealing
We consider the classical system represented by the Hamiltonian, eq. (1). To discuss the dynamics of the present system, we assume the Glauber model [21]. In the Glauber model with random coupling, the motion of the thermal average of spin at site i, S i (t), is governed by where C ± i is defined by In a following few paragraphs we give the correlation length, energy, and characteristic relaxation time at fixed temperature in the present model. The correlation function between sites i and i + k of the system with fixed {J i } is given by σ i σ i+k = i+k−1 j=i tanh βJ j . Taking the average over randomness, the correlation function in the thermodynamic limit is obtained as The correlation length ξ is defined by [ σ i σ i+k ] av = e −k/ξ , where the lattice constant is taken as the unit of the length. From the above equation, we obtain an explicit expression of ξ. In particular, an expression for low temperature limit (β 1) is given by The energy of the system with quenched {J i } is written as H = − i J i tanh βJ i . The average over randomness yields an expression of the energy per spin in the thermodynamic limit.
In the low temperature limit, this formula is reduced to We remark that the ground state energy is − 1 2 . The relaxation time is available in ref. [22] by Dhar and Barma. It is given by τ r = 1/ (1 − tanh 2β). The low temperature expression is Combination of this expression with eq. (21) yields relation between τ R and ξ: Now let us consider that the temperature is quenched according to the following schedule: where time t evolves from −∞ to 0. Remark that the critical temperature of the present system is T c = 0. This is because there is no long-range order in the equilibrium at any finite temperature, while the ground state is the complete ferromagnetic state. Anyway we pose eq. (10). We have the relation between t and ξ, |t| = τ /(ξ ln 2), derived by eqs. (21) and (26). Using this relation and eq. (25) in eq. (10), we obtain an equation ofξ ≡ ξ(T (t)): This equation cannot be solved analytically. However, since (lnξ)/ξ → 0 forξ → ∞,ξ is almost proportional to ln τ when τ 1. The inverse of correlation length corresponds to the density of kinks. Consequently the density of kinks in the state after simulated annealing is estimated as The second term in the denominator is negligible for sufficiently long τ as mentioned above. Hence eq. (7) is derived. Residual energy is also estimated from the energy at T = T (t). Using eqs. (24) and (26), eq. (10) is rewritten as where we definedβ ≡ 1/T (t). This equation is followed byβ = 1 4 ln τ − 1 4 ln(β/2). Substituting this for β in eq. (23), we obtain residual energy per spin as Since the second term in the denominator is negligible for large τ , hence eq. (8) is derived. We next consider a logarithmic schedule: where T 0 and a are positive numbers and t is assumed to evolve from −T 0 τ to 0. In this schedule, the temperature is reduced from T 0 at t = −T 0 τ to 0 at t = 0. Arranging eq. (31) as −t = T 0 τ e 1/a−(T 0 /a)β , one obtains the equation ofβ, 1 2 e 4β = T 0 τ e 1/a−(T 0 /a)β , from eqs. (10) and (24). This equation can be solved analytically and yieldβ = ln(2e 1/a T 0 τ )/(4 + T 0 /a). From eq. (21), one obtains the expression for density of kinks as This expression is reduced to eq. (7) for τ → ∞. The expression of residual energy per spin is obtained as which yields eq. (8) for τ → ∞. The asymptotic behaviors of density of kinks and residual energy for τ → ∞ are insensitive to the schedule of quenching temperature.

Monte-Carlo simulation
We confirm the results on the basis of the Kibble-Zurek argument by the Monte-Carlo simulation for systems with 500 spins. The temperature is quenched according to the linear schedule, eq. (26), and the logarithmic schedule, eq. (31). We choose the initial condition of the temperature as T = 5 at t = −5τ for both schedules. This condition is attained by T 0 = 5 and an arbitrary a in the logarithmic schedule. a is fixed at 10. To average over randomness of the system, we generated 100 configurations of coupling constants {J i } according to eq. (2). For each configuration, simulated annealing is carried out 500 times. Figures 1 and 2 are results for density of kinks and residual energy respectively. Square symbols are obtained by Monte-Carlo simulation. We have to care about units of quantities to interpret results of the simulation. At first, the unit of time in the Glauber's dynamics should be different from that in Monte-Carlo simulation. Then we bring up the relation, τ = cτ mc , between the inverse of annealing rate τ in the Glauber dynamics and that in Monte-Carlo simulation τ mc , where c is an unknown parameter. Next, the inverse of correlation length, 1/ξ is not exactly the same as the density of kinks defined by eq. (3). Then we introduce another parameter b and demand ξ = b/ρ. The curve for the linear schedule in Fig. 1 is given by ρ = 1/ξ withξ determined by eq. (27) and τ = cτ mc . Parameters, b and c, are determined by the Monte-Carlo results with the largest two τ mc 's. The fitting function for the logarithmic schedule is chosen as ρ = A/(ln τ mc + B). Parameters A and B are determined by means of the least square method. The obtained curves fit Monte-Carlo results nicely for both schedules.
In order to fit residual energies after simulated annealing with linear schedule in Fig. 2, we put forward an ansatz that residual energy is given with a parameter α by ε res = π 2 24 /(αβ) 2 , whereβ is determined by eq. (29) with τ = cτ mc . The parameter c is given from results for density of kinks. The other parameter α is determined by the Monte-Carlo result of residual energy for the largest τ mc . We assume the fitting function, ε res = D/(ln τ mc + B) 2 , for the logarithmic schedule. The fitting parameter D is averaged over values obtained from Monte-Carlo results ε (k) res for given τ mc (k) . B is given by the result of density of kinks. Evidently, these curves for residual energy are in good agreement with Monte-Carlo results.  Although there seems to be inconsistency in c, we attribute it to statistical errors of the Monte-Carlo simulation. Indeed, the curve taking this difference into account lies inside error bars of the Monte-Carlo simulation.

Conclusion
We compared quantum annealing and simulated annealing of the random Ising model in one dimension. Using the Kibble-Zurek argument, we can analytically obtain the estimation of residual errors after annealing. The results are summarized as follows. For quantum annealing, for large τ , where τ is the inverse of the annealing rate. Residual energy after quantum annealing has not been available so far. For simulated annealing, density of kinks decays as ρ SA ∼ 1/ ln τ, and residual energy as ε SA res ∼ 1/(ln τ ) 2 for large τ . The decay rate of residual energy after simulated annealing is the same as the Huse-Fisher law, but we reproduced it in the different manner. Comparing density of kinks, the decay rate of quantum annealing is faster than that of simulated annealing. This is the first analytic evidence that quantum annealing has an advantage over simulated annealing.