2 This equation naturally leads us to the following new representation of the partition function Z ( β ) = Z$_{SPS}$ ( β ) = Tr$_{{}$ S $_{i}$} , { g$_{ij}$ } ∏ i<j ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g$_{ij}$ ) . (11) We also find that the probability that some configuration { S$_{i}$ } is realized in the SPS algorithm is given as and Δ 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}$ . We can choose the potential ˜ V$_{ij}$ arbitrarily . On the other hand, using P$_{ij}$ ( S$_{i}$ , S$_{j}$ ), the potential ¯ V$_{ij}$ is given as This is the reason why the Boltzmann sampling is achieved by the SPS algorithm. We next show that the equilibrium distribution of the SPS algorithm is given by eq. (8). Let us denote the transition probability in the step (A) of the SPS algo- rithm as W$_{A}$ ( { g$_{ij}$ } → { g ′ ij }|{ S$_{i}$ } ) and that in the step (B) as W$_{B}$ ( { S$_{i}$ S ′ i }|{ g$_{ij}$ } ). It should be noted that the procedure in the step (A) updates the graph vari- ables { g$_{ij}$ } with fixing the configuration variables { S$_{i}$ } , and that in the step (B) updates { S$_{i}$ } with fixing g$_{ij}$ . In the following, we will show that the two transition probabilities satisfy the detailed balance conditions It is shown that this MC procedure strictly satisfies the detailed balance condition with respect to the original Hamiltonian of eq. (1). In the SCO method, ˜ V$_{ij}$ is set to zero to reduce the computational time of H ′ defined by eq. (5). Further- more, the use of an efficient method enables us to reduce the computational time of the potential switching proce- dure (A) greatly (see ref. [11] for details). In order to reformulate the SPS algorithm, we first introduce a graph variable g$_{ij}$ defined by These two equations clearly show that the equilibrium distribution of the SPS algorithm is P$_{SPS}$ ( { S$_{i}$ } , { g$_{ij}$ } ). We start from the proof of eq. (14). It can be easily seen from the procedure in the step (A) that W$_{A}$ ( { g$_{ij}$ } → { g ′ ij }|{ S$_{i}$ } ) = ∏ (0) ′ P$_{ij}$ ( S$_{i}$ , S$_{j}$ ) ∏ (1) ′ [1 − P$_{ij}$ ( S$_{i}$ , S$_{j}$ )] , (16) ′ P$_{SPS}$ ( { S$_{i}$ } , { g$_{ij}$ } ) W$_{A}$ ( { g$_{ij}$ } → { g ′ ij }|{ S$_{i}$ } ) = P$_{SPS}$ ( { S$_{i}$ } , { g ′ ij } ) W$_{A}$ ( { g ′ ij g$_{ij}$ S$_{i}$ } ) , (14) P$_{SPS}$ ( { S$_{i}$ } , { g$_{ij}$ } ) W$_{B}$ ( { S$_{i}$ } → { S ′ i }|{ g$_{ij}$ } ) = P$_{SPS}$ ( { S ′ i } , { g$_{ij}$ } ) W$_{B}$ ( { S ′ i S$_{i}$ g$_{ij}$ } ) . (15) where the product ∏ (0) runs over all the pairs with g ′ ij = 0 and ∏ (1) ′ runs over those with g ′ ij = 1. It should be noted that W$_{A}$ does not depend on { g$_{ij}$ } . To rewrite the right hand side of the above equation, we utilize the following two equations: Firstly, it is found from eqs. (2), (3), and (7) that 1 − P$_{ij}$ ( S$_{i}$ , S$_{j}$ ) = { e − βV$_{ij}$ ( S $_{i}$, S $_{j}$) − ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g ′ ij = 0) } e βV$_{ij}$ ( S $_{i}$, S $_{j}$) = ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g ′ ij = 1)e βV$_{ij}$ ( S $_{i}$, S $^{$_{j}$)}$, (18) Secondly, we can rewrite 1 − P$_{ij}$ ( S$_{i}$ , S$_{j}$ ) as P$_{ij}$ ( S$_{i}$ , S$_{j}$ ) = ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g ′ ij = 0)e βV$_{ij}$ ( S $_{i}$, S $^{$_{j}$)}$. (17) Tr$_{g}$$_{ij}$$_{=0}$$_{,}$$_{1}$ ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g$_{ij}$ ) = exp[ − βV$_{ij}$ ( S$_{i}$ , S$_{j}$ )] . (10) Z$_{SPS}$ ≡ Tr$_{{}$ S $_{i}$} , { g$_{ij}$ } ∏ i<j ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g$_{ij}$ ) . (9) P$_{SPS}$ ( { S$_{i}$ } , { g$_{ij}$ } ) ≡ Z − 1 SPS ∏ i<j ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g$_{ij}$ ) , (8) As it is readily derived from eqs. (2), (3), (4), and (7), the weight ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g$_{ij}$ ) has the following property: where This weight is analogous to the weight introduced by Ed- wards and Sokal [19]. We hereafter show that the SPS algorithm is a MC method which realizes equilibrium dis- tribution defined by g$_{ij}$ = { 0 if V$_{ij}$ is switched to ˜ V$_{ij}$, 1 if V$_{ij}$ is switched to ¯ V$_{ij}$. (6) ω$_{ij}$ ( S$_{i}$ , S$_{j}$ ; g$_{ij}$ ) = { e − β { ˜ V$_{ij}$ ( S $_{i}$, S $_{j}$)+Δ V ∗ $_{ij}$} ( g$_{ij}$ = 0) , e − β ¯ V$_{ij}$ ( S $_{i}$, S $_{j}$) ( g$_{ij}$ = 1) . (7) We next introduce a weight ω ( S$_{i}$ , S$_{j}$ ; g$_{ij}$ ) defined by With this potential switching process, the algorithm pro- ceeds as follows: (A) Potentials V$_{ij}$ are switched to either ˜ V$_{ij}$ or ¯ V$_{ij}$ with the probability of P$_{ij}$ or 1 − P$_{ij}$ , respectively. (B) A standard MC simulation is performed with the switched Hamiltonian H ′ expressed as H ′ = ∑ ′ ˜ V$_{ij}$ ( S$_{i}$ , S$_{j}$ ) + ∑ ′′ ¯ V$_{ij}$ ( S$_{i}$ , S$_{j}$ ) , (5) (C) Return to (A). where ′ runs over all the potentials switched to ˜ V and ∑ ′′ runs over those switched to ¯ V . The potential is fixed during the simulation. where P$_{B}$ is the Boltzmann distribution defined as P$_{B}$ ( { S$_{i}$ } ) = Z ( β ) − $^{1}$exp [ − β ∑ i<j V$_{ij}$ ( S$_{i}$ , S$_{j}$ ) ] . (13) ¯ V$_{ij}$ ( S$_{i}$ , S$_{j}$ ) = V$_{ij}$ ( S$_{i}$ , S$_{j}$ ) − β − $^{1}$log[1 − P$_{ij}$ ( S$_{i}$ , S$_{j}$ )] . (4) P ( { S$_{i}$ } ) = Tr$_{{}$$_{g}$$_{ij}$$_{}}$ P$_{SPS}$ ( { S$_{i}$ } , { g$_{ij}$ } ) = P$_{B}$ ( { S$_{i}$ } ) , (12)