## 1. Introduction

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 [14]. 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

Then we introduce an artificial design of stochastic dynamics governed by the master equation.

where

Here we denote the instantaneous equilibrium distribution (Gibbs-Boltzmann distribution) as

where the instantaneous energy

where

or heat-bath rule as

where

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

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

where

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

where the partition functions appearing in the ratio on the right-hand side are for the initial (

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

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

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

The Jarzynski equality is a consequence from the fluctuation theorem [2, 3, 4], which relates the probability

This leads to the more generic result, for an observable

where

If we choose an observable depending only on the final state, which is denoted as

By looking over the above calculations, we can understand the roll of the exponentiated pseudo work. The resultant distribution after SA is given by

### 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

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 [8]. 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 [21].

### 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

where we extract the sign of the interaction

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

where the square bracket denotes the average over all the combinations of

### 2.5. Gauge transformation

Here let us define a local transformation by the simultaneous change of the interactions and spin variables as, by the binary variables

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

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

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

Therefore we here take the summation over all the possible configurations of

We take the summation over

where

Similarly, we can evaluate the rigorous upper bound on the specific heat. The condition

### 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

We apply Eq. (19) to a gauge-invariant quantity

The quantity on the left-hand side is the configurational and nonequilibrium averages of the observable

The gauge transformation

All the quantities in this equation are invariant under the gauge transformation. The summation over

On the other hand, let us evaluate the quantity

By Setting

If we set

Equation (43) leads to the lower bound on the pseudo work, using Jensen’s inequality for the average of

By substituting

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

#### 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

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

The following relation can also be obtained in a similar manipulation,

By setting

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

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) [13].

### 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) [5]. 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 [15].

In QAC, we introduce a non-commutative operator to drive the system by quantum nature in addition to the original Hamiltonian

where

where

We take the computational basis of the eigenstates of the

where

The quantum adiabatic computation starts from a trivial ground state of

The adiabatic theorem guarantees that the instantaneous state at time

where

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

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 [20]. Here we again employ JE to give another scheme of QA while considering the nonequilibrium behavior.

### 3.2. Jarzynski equality for isolated quantum system

In order to consider the nonequilibrium behavior away from the adiabatic dynamics of QAC, we shortly review JE for an isolated quantum system [1, 24].

To directly use JE in the protocol to find the ground state of the spin-glass Hamiltonian

where

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

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

If we measure the physical observable

where the subscript on the square brackets in the right-hand side denotes the thermal average in the last equilibrium state with the inverse temperature

The resultant equation suggests that we can estimate the thermal average under the Hamiltonian

## 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

### 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 [22].

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

We assume that the interactions

where we do not use

### 4.2. Gauge transformation for quantum spin systems

For several special spin glasses as the

where

### 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

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

A similar quantity of the average of the exponentiated work for spin glass with the inverse temperature

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

The symmetric distribution (

where

where

Here we defined the marginal distribution for the specific configuration

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

This equation reduces to, by setting

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

The quantity on the right-hand side becomes unity by the analysis with the gauge transformation as has been shown in the literatures [18, 19]. We thus reach a simple exact relation

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

## 5. Conclusion

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.

## Acknowledgement

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.