Approximate ground states of the random-field Potts model from graph cuts

While the ground-state problem for the random-field Ising model is polynomial, and can be solved using a number of well-known algorithms for maximum flow or graph cut, the analog random-field Potts model corresponds to a multiterminal flow problem that is known to be NP-hard. Hence an efficient exact algorithm is very unlikely to exist. As we show here, it is nevertheless possible to use an embedding of binary degrees of freedom into the Potts spins in combination with graph-cut methods to solve the corresponding ground-state problem approximately in polynomial time. We benchmark this heuristic algorithm using a set of quasiexact ground states found for small systems from long parallel tempering runs. For a not-too-large number $q$ of Potts states, the method based on graph cuts finds the same solutions in a fraction of the time. We employ the new technique to analyze the breakup length of the random-field Potts model in two dimensions.

Figure 1

Schematic diagram showing the variation of $E$ with time $t$ in the PT runs (in MC steps). The first occurrence of the minimum energy $E_0$ is at onset time $t=t_0$. The corresponding state is accepted as a ground state if no lower energy is found up to $t\ge 10t_0$.

Figure 2

Disorder-averaged onset times $t_0$ for finding the ground states of the $d=2$ RFPM using parallel tempering. The data is plotted on a linear-log scale as a function of (a) the number of Potts states $q$ for $L=16$, and (b) the system size $L$ for $q=3$. The data are averaged over 1536 realizations of quenched random fields according to Eq. (3) with $\mathrm{\Delta }=1$. The shaded area shows the range that contains the onset times for 66% of the samples.

Figure 3

Energy histograms of final states obtained from GC for the $q=3$ RFPM (top row) and the $q=4$ RFPM (bottom row) on a ${64}^2$ lattice. The histograms are obtained from 10 000 initial configurations $\left\{s_i\right\}$ for a fixed disorder configuration $\left\{{\epsilon }_i^{\alpha }\right\}$.

Figure 4

Variation of the standard deviation of energy $\left[{\sigma }_E\right]$ from runs of the GC method as a function of disorder amplitude $\mathrm{\Delta }$ for the $d=2$ RFPM with (a) $q=3$ and (b) $q=4$. All data are averaged over 100 disorder realizations $\left\{{\epsilon }_i^{\alpha }\right\}$ and 1000 initial states $\left\{s_i\right\}$ for each disorder realization. Clearly, $\left[{\sigma }_E\right]$ grows with lattice size $L$, and also with number of states $q$. The scaled data in the insets demonstrate that $\left[{\sigma }_E\right]\sim \sqrt{N}=L$, i.e., there are no critical fluctuations in this range of $\mathrm{\Delta }$ values.

Figure 5

Plot of $\left[{\sigma }_E\right]$ vs. $q$ for the $d=2$ RFPM with $\mathrm{\Delta }=1.0$ and indicated lattice sizes. The statistics is the same as in Fig. 4. The spread in energy of the GC states increases with $q$. The inset shows that $\left[{\sigma }_E\right]\sim \sqrt{N}=L$.

Figure 6

Disorder-averaged success probability of finding the ground state from GC and PT runs for 2D RFPM as a function of $q$ (left panel, $L=16$) and $L$ (right panel, $q=3$). The GC data correspond to one initial state per disorder sample, while the run time in PT was adapted to yield exactly the same average success probability as the corresponding GC run (see main text). All data are averaged over 1536 configurations of the random fields.

Figure 7

Accuracy $\left[\varepsilon \right]$ defined in Eq. (14) of GC and PT runs for the $d=2$ RFPM as a function of $q$ (left panel, $L=16$) and $L$ (right panel, $q=3$), respectively. Both methods are tuned to have the same success probabilities, as shown in Fig. 6. The data are averaged over 1536 disorder realizations with $\mathrm{\Delta }=1.0$.

Figure 8

Average overlap $\left[O\right]$ [see Eq. (15)] of the states returned by GC and PT, respectively, with the true ground states for the $d=2$ RFPM as a function of $q$ for $L=16$ (left) and $L$ for $q=3$ (right), respectively. The averaging is done over 1536 disorder realizations with $\mathrm{\Delta }=1.0$.

Figure 9

Disorder-averaged run time $\left[r\right]$ (in CPU seconds) for determining the final state by the application of the $\alpha$-expansion GC method to the RFPM in two dimensions (top row) and three dimensions (bottom row) as a function of the number of spins $N=L^d$ and the number of states $q$, respectively. The data are averaged over 1000 disorder realizations with $\mathrm{\Delta }=1.0$. The solid lines are power-law fits with the specified exponents and demonstrate that the run time is linear in $N$ and approximately linear in $q$.

Figure 10

Disorder-averaged run time $\left[r\right]$ of the GC method for the 2D RFPM as compared to CPU and GPU implementations of the PT method tuned to achieve the same success probability as a function of $q$ (left panel, $N={16}^2$) and as a function of $N=L^2$ (right panel, $q=3$).

Figure 11

Left panel: Disorder-averaged probability $P_{\mathrm{FM}}(L,\mathrm{\Delta })$ of samples of the 2D $q=3$ RFPM to have purely ferromagnetic ground states. The data are averaged over 10 000 disorder realizations for $L\le 128$ and 5000 realizations for $L=256$ and 512. Right panel: The breakup length scale $L_b$, defined as the system size $L$ where $P_{\mathrm{FM}}(L,\mathrm{\Delta })=0.5$, versus the inverse random-field strength $1/\mathrm{\Delta }$ for $q=2,3$, and 4. The solid lines show fits of the functional form $L_b\sim e^{A/\mathrm{\Delta }}$ to the data, where $A=3.6\pm 0.03$.