content_image/435918.jpg content_image/435902.jpg content_image/435914.jpg content_image/435913.jpg content_image/435905.jpg content_image/435906.jpg content_image/435911.jpg content_image/435912.jpg content_image/435903.jpg content_image/435904.jpg
where V ∗ ij is a constant equal to (or greater than) the maximum value of V$_{ij}$ ( S$_{i}$ , S$_{j}$ ) over all S$_{i}$ and S$_{j}$ . The point of the formulae is the presence of δ$_{g}$$_{kl}$$_{,}$$_{1}$ in ˜ E and ∂ ˜ E $_{∂β}$. In general, the strength of pairwise long-range in- teractions V$_{ij}$ decreases with increasing the distance r$_{ij}$ . Therefore, g$_{ij}$ for most of distant and weak interactions becomes zero (see eqs. (2) and (6)). This means that the computational time of ˜ E and its derivative is much shorter than that of ∑ k<l V$_{kl}$ which is needed in naive internal energy and heat capacity measurements. Al- though the calculation of the constant E$_{const}$ requires O ( N $^{2}$) computational time, it is enough to calculate it just once at the beginning of the simulation. 

In summary, the use of the formulae (eqs. (24), (25), (31), (32), and (33)) enables us to reduce the computa- tional time for internal energy and heat capacity mea- surements greatly. This method can be used in the SCO method [11] because ˜ V$_{ij}$ is set to be zero in the method. 

## IV. A FORMULA FOR THE REPLICA EXCHANGE MC METHOD 

We first explain the replica exchange MC method [18] briefly. This method is quite efficient for systems with rugged energy landscape such as spin glasses. In this method, we consider a system with M independent repli- cas and M different temperatures. The M replicas have a common Hamiltonian H ( S ). The purpose of the method is to sample states of the M replica system with the fol- lowing equilibrium distribution 

<img src='content_image/435918.jpg'>

where { } m -th replica and P$_{B}$ is the Boltzmann distribution de- fined by eq. (13). In the replica exchange MC method, the equilibration is accelerated by exchanging the replica at temperature T$_{m}$ for that at T$_{n}$ . By employing the Metropolis method, the probability of accepting the ex- change is given as 

where 

A problem of the replica exchange MC method in long- range interacting systems is that it costs O ( N $^{2}$) compu- tational time to calculate the exchange probability since 

<img src='content_image/435902.jpg'>

<img src='content_image/435914.jpg'>

<img src='content_image/435913.jpg'>

X$_{B}$ in eq. (36) contains H which consists of O ( N $^{2}$) pair- wise interactions. In order to overcome the difficulty, we consider a replica exchange MC method whose equilib- rium distribution is 

where g$_{m}$ denotes the set of graph variables { g$_{ij}$ } of the m -th replica and P$_{SPS}$ is defined by eq. (8). It should be noted that this replica exchange MC method sam- ples configuration ( S$_{1}$ , · · · , S$_{M}$ ) according to the original probability Q B since Q SPS is related to Q B as 

where we have used eq. (12). The probability of accepting the replica exchange is given as 

<img src='content_image/435905.jpg'>

where 

<img src='content_image/435906.jpg'>

In this equation, the product ∏ ( α ) runs over all the pairs with g$_{ij}$ = α and ∏ ( α ) ′ runs over those with g ′ ij = α . When ˜ V$_{ij}$ = 0, we can rewrite the first product in the right hand side of eq. (40) as 

<img src='content_image/435911.jpg'>

The second product can be rewritten in a similar way. By substituting these results into eq. (40), we find 

<img src='content_image/435912.jpg'>

<img src='content_image/435903.jpg'>

<img src='content_image/435904.jpg'>

