We prefer to find the most appropriate choice in daily life for convenience and efficiency. When we go to a destination, we often use a searching program to find the fastest way, the minimum-length path, or most-reasonable one in cost. In such a searching problem, we mathematically design our benefit as a multivariable function (cost function) depending on many candidates and intend to maximize it. Such a mathematical issue is called the optimization problem. Simulated annealing (SA) is one of the generic solvers for the optimization problem . We design the lowest-energy state in a physical system, which corresponds to the minimizer/maximizer of the cost function. The cost function to describe the instantaneous energy of the system is called as the Hamiltonian, where is the degrees of freedom in the system and is the number of components related with the problem size. The typical instance of the Hamiltonian is a form of the spin glass, which is the disordered magnetic material, since most of the optimization problems with discrete variables can be rewritten in terms of such a physical system,
where indicates the direction of the spin located at the site in the magnetic material as. The summation is taken over all the connected bonds through the interaction. The configuration of depends on the details of the optimization problem.
Then we introduce an artificial design of stochastic dynamics governed by the master equation.
where is the probability with a specific configuration of simply denoted as at time. The transition matrix is written as, which obeys the conservation of probability and the detailed balance condition
Here we denote the instantaneous equilibrium distribution (Gibbs-Boltzmann distribution) as
where the instantaneous energy is the value of the Hamiltonian and denotes a normalization factor termed as the partition function. In order to satisfy these conditions, we often use the transition matrix with Metropolis rule as
or heat-bath rule as
The master equation simulates behavior of relaxation toward a specific distribution associated with the energy of the system. If we evolve the system for a long time with a virtual parameter being a constant, which is the inverse temperature in context of physics, the probability distribution converges to the equilibrium distribution. To generate lower energy state, let us set. Unfortunately, the spin-glass system in the low-temperature often exhibits the extremely long time for equilibration of the system. The most relevant reason is on the complicated structure of the energy of the spin-glass system as schematically depicted in Fig. 1.
There are barriers between the valleys to avoid hopping from state to state in the low-temperature, where the energy effect is dominant. Therefore it is difficult to reach the equilibrium distribution by a direct simulation with a constant temperature. Instead, by tuning a virtual parameter from zero to a large number, we perform stochastic searching while keeping to trace the instantaneous equilibrium distribution. The mathematical guarantee to converge to the instantaneous equilibrium state by gradually changing the inverse temperature has been proved by Geman and Geman based on the classical inhomogenious (time-dependent) Markov chain representing nonequilibrium processes . The convergence theorem states that we reach the equilibrium distribution, if we obey the following schedule or slower rate to change the inverse temperature as
where is exponentially small in and is a constant independence of. An intuitive way to understand the performance of SA is as follows. The inverse temperature controls the range of searching, roughly speaking. The instantaneous state keeps hopping from state to state in a relatively high-temperature region as depicted in Fig. 2.
By gradually decrease of the inverse temperature, we narrow the range of searching. The lower energy state means its realization with a higher possibility following the instantaneous equilibrium distribution as in Fig. 2. Demand of a sufficiently slow control of the inverse temperature implies that we need enough time to find the states with relatively lower energies by the stochastic searching before the barrier avoids globally searching for the lower energy state.
Basically, SA is based on the behavior closely to the instantaneous equilibrium state. Therefore we need to perform the change of the inverse temperature with a sufficiently slow control. In order to improve the performance, in particular to shorten the necessary time, we need to consider the protocol away from the equilibrium state, that is nonequilibrium process.
In this chapter, we show a novel direction to solve efficiently the optimization problem by use of the nature in nonequilibrium physics. In statistical physics, the interest of researchers in nonequilibrium dynamical behavior has increased. Among several remarkable developments, the Jarzynski equality (JE), which is known as a generalization of the second law of thermodynamics, might be possible to change the paradigm in optimization problem by use of the physical nature. The Jarzynski equality relates an average over all realizations during a predetermined nonequilibrium process with an expectation in an equilibrium state. As seen later, the mathematical structure of JE does not depend on the schedule and the rate of changing the external parameter. It means that, if we implement JE to solve the optimization problem, we do not need to demand slow control of the driver of the system. The challenge of the implementation of JE have been performed in several researchers. Although not yet have been studied the performance in the actual application to the optimization problem, we show the possibility of the novel method from several analyses.
2. Population annealing
We introduce a couple of theories in nonequilibrium statistical physics in short, before we show the actual application. They provide the supplement to make the protocol of SA faster. The Jarzynski equality is the most important key.
2.1. Jarzynski equality
Among several recent developments in nonequilibrium statistical mechanics, we take JE as an attempt to improve the performance of SA. The Jarzynski equality relates quantities at two different thermal equilibrium states with those of nonequilibrium processes from to connecting these two states as [10,11]
where the partition functions appearing in the ratio on the right-hand side are for the initial () and final Hamiltonians (). The quantity on the right-hand side can be represented by the exponentiated difference of the free energy between the initial and final conditions. The brackets on the left-hand side express the nonequilibrium average over all the instantaneous realizations of the degrees of freedom, for instance spin configurations, during the nonequilibrium process with the following path probability defined as
It implies that the observations of the nonequilibrium behavior can estimate the equilibrium quantity represented by the partition functions, that is the free energy. This equality is regarded as a generalization of the well-known inequality, the second law of thermodynamics, which can be reproduced by the Jensen inequality. One of the important features is that JE holds independently of the pre-determined schedule of the nonequilibrium process.
In order to consider the improvement of SA, let us apply the nonequilibrium process with change of the temperature. We then have to employ the pseudo work instead of the ordinary performed work due to the energy difference as
where we use discrete time expressions as and for simplicity and we assume that the instantaneous energy does not depend on the time as. The Jarzynski equality holds formally in the case with change of temperature,
We show a simple proof of JE for the particular dynamics in SA. Let us consider a nonequilibrium process in a finite-time schedule governed by the master equation. The left-hand side of JE is written as
where we use the formal solution of the master equation by the exponentiated transition matrix. We take the first product of the above equation as,
Repetition of the above manipulation in Eq. (14) yields the quantity in the right-hand side of JE as,
2.2. Fluctuation theorem
This leads to the more generic result, for an observable depending on the instantaneous spin configurations,
where denotes the observable which depends on the backward process. The brackets with subscript express the average with the weight over possible realizations. For, Eq. (18) reduces to JE.
If we choose an observable depending only on the final state, which is denoted as, instead of, reads an observable at the initial state in the backward process. Then equals to the ordinary thermal average at the initial equilibrium state with represented by, and Eq. (18) leads to
By looking over the above calculations, we can understand the roll of the exponentiated pseudo work. The resultant distribution after SA is given by. The biased distribution with the exponentiated pseudo work, always gives the equilibrium one. In this sense, the exponentiated pseudo work plays a roll to fill the gap between the equilibrium distribution and the resultant one after SA. Therefore, if we skillfully use the exponentiated pseudo work to keep the instantaneous distribution close to the equilibrium one, we can invent the improved version of SA.
2.3. Population annealing
We introduce an improvement of SA by use of the property of JE. Let us consider to implement JE in numerical simulation. We parallelize the instantaneous spin configurations as. Each of the configuration independently will be evolved by the master equation. We regard the exponentiated pseudo work on the left-hand side of JE, Eq. (14), as the weight for each realization of the configuration. By computing the pseudo work for each realization and multiplying the weight given by the exponentiated pseudo work, we simultaneously perform the stochastic dynamics governed by the master equation. At the last stage of repetition of the above procedure, we obtain the ratio of the partition function as in the right-hand side of JE. In order to calculate its value, we estimate the empirical average as, after parallel computing of the master equation,
While estimating the ratio of the partition functions by JE, implementation of Eq. (19) gives the thermal average of the observable through their ratio. This is the typical implementation of JE in a numerical simulation, which is called as population annealing (PA) [7, 9, 17] as depicted in Fig. 3,
We remark that, as proposed in the literatures [7, 9], we have to employ a skillful technique, resampling, to efficiently generate the relevant copies to estimate the nonequilibrium average and maintain the stability of the method. The population annealing with resampling method indeed shows outstanding performance comparable to a standard technique to equilibrate the spin-glass system known as the exchange Monte Carlo method . If we successfully generate the equilibrium distribution in the low-temperature region, we efficiently find the lowest energy state, which corresponds to the optimal solution in context of the optimization problem. Therefore PA is also relevant for the improvement of SA as a solver for the optimization problem. The advantage of PA is cutting the computational time compared to SA, since PA follows the property of JE. It means that we find the optimal solution by use of PA faster than SA.
Below, we propose an ambitious use of PA to evaluate the equilibrium property in the low-temperature in spin glasses by use of the special symmetry .
2.4. Spin glass
At first we briefly review a useful analysis in several spin-glass systems, which provides a powerful technique to discuss the possibility of PA. Let us consider a simple model of spin glasses, the Ising model, on an arbitrary lattice. The Hamiltonian is the same form as Eq. (1) as
where we extract the sign of the interaction following the distribution function as
The partition function, which is the most important quantity through the free energy, is defined as
The free energy is then given by
where the product is rewritten as. Both of the above quantities depend on the specific configuration. In order to evaluate the physical property of spin glasses in equilibrium, we strive the difficult task to deal with the free energy depending on the non-uniform interactions. Instead of the direct manipulation, the averaged quantity over all the possible configurations of may be considered based on the self-averaging property as, in the large-limit,
where the square bracket denotes the average over all the combinations of (configurational average). The self-averaging property is valid for other observables, which can be obtained from the free energy per site like the internal energy.
2.5. Gauge transformation
This is called as the gauge transformation. Notice that the gauge transformation does not alter the value of the physical quantity given by the double average over and since it changes only the order of the summations. The Hamiltonian can not change its form after the gauge transformation since the right-hand side is evaluated as
As this case, if the physical quantity is invariant under the gauge transformation (gauge invariant), we can evaluate its exact value even for finite-dimensional spin glasses. The key point of the analyses by the gauge transformation is on the form of the distribution function. Before performing the gauge transformation, the distribution function can take the following form as
where. The gauge transformation changes this into
Let us evaluate the internal energy by aid of the gauge transformation here. The thermal average of the Hamiltonian is given by
We can use the self-averaging property here and thus take the configurational average as
where denotes the configurational average by the distribution function (29) with. Then we perform the gauge transformation, which does not change the value of the internal energy due to gauge invariance,
Therefore we here take the summation over all the possible configurations of and divide it by (the number of configurations) as
We take the summation over in advance of that over and then find the partition function with instead of.
where is the number of bonds. Going back to the definition (31), both of the partition functions on the denominator and numerator can be cancelled when as
Similarly, we can evaluate the rigorous upper bound on the specific heat. The condition confines the special subspace in which we can perform the exact analysis for spin glasses. This subspace is called as the Nishimori line (NL) [18, 19].
2.6. Jarzynski equality for spin glasses
By use of the gauge transformation as above introduced briefly, let us consider the application of the relations (18) and (19) to spin glasses, namely PA for such a complicated system in a tricky way. We analyze JE for the spin-glass model for several interesting quantities below.
2.6.1. Gauge-invariant quantities like internal energy
The quantity on the left-hand side is the configurational and nonequilibrium averages of the observable at final stage of PA, that is after the protocol with the factor. On the other hand, on the right-hand side expresses the configurational and thermal averages of the equilibrium state for the final Hamiltonian.
The gauge transformation leads us to
All the quantities in this equation are invariant under the gauge transformation. The summation over and division by gives
On the other hand, let us evaluate the quantity. Similarly to the above calculation, the following identity can be obtained by the gauge transformation,
By Setting in Eq. (40) and in the above equation, we reach the following nonequilibrium relation,
If we set in the resultant equation, the Jarzynski equality for spin glass is obtained,
Equation (43) leads to the lower bound on the pseudo work, using Jensen’s inequality for the average of,
By substituting into Eq. (42), we obtain
This equation shows that the internal energy after the cooling as in SA or heating process starting from a temperature on NL, which is in the present case, is proportional to the internal energy in equilibrium on NL corresponding to the final temperature as in Fig. 4. We here assume to perform PA and take an average over all results after many repetitions. The nonequilibrium process starts from NL and ends at the point away from NL. Notice that the ordinary procedure in PA gives the estimation of the equilibrium quantity at the last condition as. However the corresponding internal energy is at the different point but on NL as. It means that we can obtain the equilibrium quantities in the different amount of the randomness from the initial condition through the configurational average of the results from PA.
2.6.2. Gauge-non-invariant quantities
In statistical physics, it is important to detect the order of the instantaneous spin configuration in the system. For instance, as in Fig. 4, there are several phases, ferromagnetic, paramagnetic and spin-glass ones, involved in the spin-glass model. They have the characteristic quantities to distinguish themselves, termed as the order parameter. The order parameter to identify the phase boundary between the ferromagnetic and paramagnetic phases is the magnetization defined as
Therefore it is important to observe the behavior of the first momentum of spin variable in equilibrium. For this purpose, we choose for in Eq. (19) and consider the possibility of the application of PA. After the configurational average, we obtain
Gauge transformation for the right-hand side in this equation yields
We again sum both sides of this equation over all the possible configurations of and divide the obtained quantity by to find
The following relation can also be obtained in a similar manipulation,
As a result, we obtain a nonequilibrium relation,
The same method yields another relation for the correlation functions to similarly measure the magnitude of order in the system
The obtained relations (52) and (53) relate the equilibrium physical quantities away from NL (the right-hand sides) with other quantities measured during the nonequilibrium process from a point on NL to another point away from NL (the left-hand sides) as depicted in Fig. 5. The spin-glass system in the low-temperature region exhibits the extremely slow relaxation toward equilibrium. This feature hampers to observe the equilibrium behavior of spin glasses. However our results imply that the configurational average of PA would overcome the difficulty. One may attempts the heating process from NL in order to evaluate the low-temperature property through Eqs. (52) and (53) as depicted in Fig. 5. The Jarzynski equality holds irrespectively of the schedule to control the external field. It means that we can investigate the low-temperature behavior for spin glasses without suffering from critical slowing down.
Unfortunately, however, the exponentiated pseudo work does not hold the self-averaging property. It means that the sample-to-sample fluctuation between different configurations of remains to be relevant even in a large-system. Therefore, if we estimate the empirical average of realizations of following the obtained equalities, we do not correctly reproduce the quantity of the right-hand side. We describe the test results for estimation of the ratio of the partition functions as in Eq. (13) by PA for realizations of in Fig. 6. We perform PA for the Ising model on the square lattice with a linear size, and Monte-Carlo step. The number of copies is.
The population annealing can correctly estimate the ratio of the partition functions for each realization, but their simple average does not coincide with the quantity on the right-hand side of Eq. (43) as in Fig. 7. Both of the results are away from the exact solutions due to the sample-to-sample fluctuation and show nontrivial behavior depending on the linear size. These facts imply lack of self-averaging property. Therefore, if we exploit all the above results given by the configurational average of the exponentiated pseudo work, we have to overcome this violation due to lack of the self-averaging property. This is one of the remaining problem associated with this procedure with PA for spin glasses.
3. Quantum annealing
Observant readers may begin to recognize the possibility to use physical nature to drive the system in searching the lowest energy (ground state) instead of thermal fluctuation controlled by the inverse temperature. We show another strategy to find the ground state recently studied in a field of physics, quantum annealing (QA) .
3.1. Quantum adiabatic computation
In quantum-mechanical system, we can use a parallel way to drive all the candidates of the desired solution in optimization problem by use of superposition. Quantum annealing uses quantum fluctuation between superposed states to search for the ground state. One of the successful strategies is to use the adiabatic evolution known as quantum adiabatic computation (QAC) . In QAC, as the procedure of SA, we control to gradually decrease the strength of quantum fluctuations to drive the system. Similarly to SA, the convergence into the optimal solution of QAC (the ground state) is also guaranteed by a mathematical proof .
In QAC, we introduce a non-commutative operator to drive the system by quantum nature in addition to the original Hamiltonian, which is designed to represent the optimization problem to be solved, as
where is assumed to be a monotonically increasing function satisfying and. For instance, , where denotes the computation time for QAC. In order to exemplify the explicit instance, we again assume that is the spin glass Hamiltonian as
where is the component of the Pauli operators defined as
We take the computational basis of the eigenstates of the -component of the Pauli matrix (Ising variables) to represent the instantaneous state as. The transverse-field operator is often used as quantum fluctuations for implementing QAC for the spin-glass model
where is the strength of the transverse field. The whole Hamiltonian of QAC (although widely used also for QA) thus becomes
The quantum adiabatic computation starts from a trivial ground state of. In the present case, the ground state of the transverse-field operator is simply written by a uniform linear combination as.
The adiabatic theorem guarantees that the instantaneous state at time, , is very close to the instantaneous ground state for a sufficiently large (implying slow control) as, if the instantaneous ground state is non-degenerate. The condition for, to hold can be written as 
where is the instantaneous first excited state, and is the energy gap between the ground state and first excited one. The maximum and minimum should be evaluated between and. In the present case, since, the above adiabatic condition is reduced into
It means that if we desire to solve the optimization problems by use of QAC, which one of the specialized version of QA, we take the computational time proportional to the inverse square of the energy gap. If the problem involved with the exponential closure of the energy gap for increasing of, QAC must take extremely long time to obtain the ground state with a high probability [12, 25]. Interestingly, we can reproduce the convergence theorem of SA (9) from the above adiabatic condition with recourse to a mathematical mapping of the procedure of SA into the quantum dynamics [15, 23]. It implies that the nature of QAC can be understood through that of SA by the mathematical mapping technique.
Below, we would provide a new paradigm to solve faster than the ordinary scheme of SA. A fast sweep of the system yields nonequilibrium behavior. Although we have not yet understood deeply the nonequilibrium phenomena, there are a few well-established theories which rises to applications to the optimization problem. One possibility is PA for the quantum system by use of JE and its alternatives . Here we again employ JE to give another scheme of QA while considering the nonequilibrium behavior.
3.2. Jarzynski equality for isolated quantum system
To directly use JE in the protocol to find the ground state of the spin-glass Hamiltonian as in Eq. (55), we prepare the dynamical quantum system following the time-dependent Hamiltonian (58). In addition, we pick up a state from the canonical ensemble for at the initial stage of the procedure and then let it evolve following the time-dependent Schrödinger equation. We measure the performed work in the isolated quantum system as, which is simply given by the difference between the outputs of projective measurements of the initial and final energies. Here and denote the indices of the instantaneous eigenstates as and, respectively. The time-evolution operator is given by the following unitary operator as
where denotes the time ordered product. Therefore the transition probability between the initial and final stages is given as
The path probability for the nonequilibrium process starting from the equilibrium ensemble is then evaluated as
where we express the instantaneous partition function for the instantaneous Hamiltonian at each time as.
By directly evaluating the nonequilibrium average of the exponentiated work but for the isolated system, we reach JE applicable to non-adiabatic version of QA. We define the nonequilibrium average of the exponentiated work as
which becomes the left-hand side of JE. The quantity defined here is evaluated as
where we used the fact that the performed work was a classical number and
If we measure the physical observable at the last of the nonequilibrium process, we obtain another equation as, similarly to the classical version,
The resultant equation suggests that we can estimate the thermal average under the Hamiltonian on the right-hand side through the left-hand side of JE. This fact may be useful in the evaluation of equilibrium average, since the left-hand side is evaluated without slow adiabatic processes. Differently from QAC, we must sweep the quantum system repeatedly to correctly estimate the nonequilibrium average as in JE, but in short time. We propose such a procedure as the alternative of QAC, the non-adiabatic quantum annealing (NQA) based on the property of JE as above established. First we discuss the possibility as a solver of the optimization problem below.
4. Non-adiabatic quantum annealing
In order to investigate the property of the ground state, we tune the inverse temperature into a very large value. The nonequilibrium average on the left-hand side of JE involves a non-extensive quantity, the exponentiated work, whose value fluctuates significantly from process to process. Therefore the average on the left-hand side must be calculated by many trials of annealing processes. Thus, rare events with large values of the exponentiated work (i.e.) would contribute to the average significantly, and we have to repeat the annealing process very many, typically exponentially, times in order to reach the correct value of the average. This property would be a bottleneck of the simple implementation of NQA, instead of long time involved by the closure of the energy gap in QAC. What about PA in the classical counter part? In order to generate the relevant contributions in PA, we use the biased distribution with the exponentiated pseudo work through resampling technique [7, 9]. Without resampling technique, we cannot efficiently reproduce the prediction given by JE. In this fact, if we implement the biased distribution in the quantum system, we would use NQA without suffering from rare events. It means that we can perform NQA in order to find the ground state in a short time with several repetitions. So far, it is the very difficult task to realize the biased distribution in the quantum system. However it is worthwhile to consider its possibility in the future.
4.1. Several analyses of non-adiabatic quantum annealing
Unfortunately, we have not reached any positive answers on the performance of NQA. Instead let us here evaluate several properties in nonequilibrium process as in NQA for the particular spin glasses. We can exactly analyze nonequilibrium behavior by combination of JE with the gauge transformation, although there are few exact results in nonequilibrium quantum dynamical system with many components .
Following the prescription of JE, let us consider a repetition of NQA starting from the equilibrium ensemble. The initial Hamiltonian of NQA is given only by the transverse field. It turns out that the starting point of our analyses is the specialized JE to the case for NQA as
We assume that the interactions follow the distribution function for the Ising model (22), which is better to be rewritten as
where we do not use for transparency, and.
4.2. Gauge transformation for quantum spin systems
For several special spin glasses as the Ising model, the gauge transformation is available for analyses on the dynamical property even under quantum fluctuations. The time-dependent Hamiltonian as in Eq. (58) is invariant under the following local transformation,
where is called as a gauge variable. This transformation is designed to preserve the commutation relations between different components of Pauli matrices .
4.3. Relationship between two different paths of NQA
Below, we reveal several properties inherent in NQA by the gauge transformation. Let us take the configurational average of Eq. (68) over all the realizations of for the special case with and as
The right-hand side is written explicitly as
Let us here apply the gauge transformation as introduced above. Since the time-dependent Hamiltonian is invariant, we may sum over all possible configurations of the gauge variables and divide the result by in order to obtain the quantity on the left-hand side,
A similar quantity of the average of the exponentiated work for spin glass with the inverse temperature and the parameter for the quenched randomness gives
Comparing Eqs. (73) and (74), we find the following relation between two different non-adiabatic processes,
We describe the two different paths of NQA related by this equality in Fig. 8.
Setting in Eq. (75), (implying, the symmetric distribution), we find a nontrivial relation on the performed work during NQA
The symmetric distribution (on the left-hand side) makes it possible to reduce the right-hand side to the above trivial expression. It is remarkable that NQA, which involves very complex dynamics, satisfies such a simple identity irrespective of the speed of annealing. The Jensen inequality for the above equality leads us to the lower bound for the performed work as
where is the coordination number as. Here we generalize the inverse temperature to from the specific choice. This lower bound is loose, since the direct application of the Jensen inequality to JE for NQA yields, after the configurational average with the symmetric distribution,
where is the Kullback-Leibler divergence defined as
Here we defined the marginal distribution for the specific configuration summed over all the possible gauge transformations,
Since the Kullback-Leibler divergence does not become non-negative, the work performed by the transverse field during a nonequilibrium process in the symmetric distribution (i.e. the left-hand side of Eq. (78)) does not lower below the second quantity on the right-hand side of Eq. (78), namely Eq. (77). This fact means that Eq. (77) is a loose lower bound.
4.4. Exact relations involving inverse statistics
Beyond the above results, we can perform further non-trivial analyses for the nonequilibrium process in the special conditions. Let us next take the configurational average of the inverse of JE, Eq. (68), as
The application of the gauge transformation to the right-hand side yields
Summation of the right-hand side over all the possible configurations of and division of the result by give
This equation reduces to, by setting, namely on the Nishimori line,
Comparison of Eqs. (76) and (84) gives
As shown in Fig. 9, the resultant equation leads us to a fascinating relationship of the two completely different processes through the inverse statistics. One denotes NQA toward the Nishimori line, while the other expresses for the symmetric distribution.
We can find the exact results through the inverse statics of the inverse statics of Eq. (66). Let us further consider the case for the two-point correlation. Taking the configurational average of both sides under the condition, we find
which is another exact identity for processes of NQA.
We obtain several exact nontrivial relations between completely different paths in NQA as shown above by use of the gauge transformation, which is a specialized tool to analyze spin glasses. We should notice that such results are very rare for the nonequilibrium behavior in disordered quantum system. The importance of the above equalities is still not clear. We emphasize that, when we realize the quantum spin systems in experiments, the above results would be a valuable platform to confirm their precisions and conditions. The quantum annealing is originally intended to be a tool implemented in so-called quantum computer. Therefore we need theoretical studies not only on the performance in the application but also how to make good condition to implement the protocol. In this regard, our studies shed light on the future indicator to open the way to realize the generic solver in the quantum computer. We must continue the active studies in this direction. 1.04
We reviewed several recent active studies on the alternatives of SA with use of the novel substantial progress in statistical physics. The key point was to exploit the nonequilibrium behavior during performing the active control on the system. The Jarzynski equality states the possibility to estimate the equilibrium quantities by the average quantity through the nonequilibrium behavior. It means that we can invent several new strategies by use of JE away from the paradigm of the simulated annealing, which sticks to the quasi-static dynamics. The population annealing is a starting point of the studies in this direction. It is certain that population annealing find out the desired solution of the optimization problem from the property of JE faster than SA. Roughly speaking, the population annealing cuts the computational time (CPU) by use of the parallel dynamics (memory). The remaining problem is to evaluate its qualitative performance of PA for the optimization problem.
Not only the direct use of PA, we propose another type of its application in this chapter. Regarding on this type, we show skillful analyses by use of the special symmetry hidden in spin glasses to give several nontrivial exact relations. The resultant relations are useful to investigate the low-temperature region for spin glasses if we implement them by aid of PA, since we do not suffer from the critical slowing down peculiar in spin glass.
Meanwhile, if we employ a different rule to drive the system, we would be able to find the way to solve the optimization problem as SA. We reviewed QA, which was by use of quantum fluctuations as a driver. The specialized version of QA, QAC, is found to has a crucial bottleneck to solve a part of the optimization problem. Therefore we need to remove this problem while keeping its generality as a solver of the optimization problem. We again considered the application of JE to propose an alternative method, NQA. Although we do not assess its quantitative performance in the application to the optimization problem, our proposal gives a new paradigm to solve the optimization problem through the physical process like SA. We have to emphasize that QA was invented to solve the optimization problem in quantum computer. Therefore we must prepare the quantitative results to verify the precision and conditions in the actual experience on quantum computers. Along this line, we gave several results for the nonequilibrium behavior in the quantum system with gauge symmetry. These studies would be significant in the future development to realize the quantum computation.
Beyond the original version of SA, in order to find the desired solution as fast as possible, we must be away from the quasi-static procedure. The key point is to deal with nonequilibrium behavior. The further understanding of its peculiar behavior in statistical physics would be helpful to invent a genius and generic solver as PA and NQA.
The author thanks the fruitful discussions with Prof. Koji Hukushima of University of Tokyo and Prof. Hidetoshi Nishimori of Tokyo Institute of Technology. This work was partially supported by MEXT in Japan, Grant-in-Aid for Young Scientists (B) No.24740263.