Reduction of dilute Ising spin glasses

The recently proposed reduction method for diluted spin glasses is investigated in depth. In particular, the Edwards-Anderson model with $\pm J$ and Gaussian bond disorder on hypercubic lattices in $d=2$, 3, and 4 is studied for a range of bond dilutions. The results demonstrate the effectiveness of using bond dilution to elucidate low-temperature properties of Ising spin glasses and provide a starting point to enhance the methods used in reduction. Based on that, a greedy heuristic called “dominant bond reduction” is introduced and explored.

Figure 1

“Star-triangle” relation to reduce a three-connected spin $x_0$. The new bonds on the right are obtained in Eq. (4).

Figure 2

Illustration of rule VI for “strong” bonds. Left: the local topology of a graph is shown for two spins, $x_0$ and $x_1$, connected by a bond $J_{0,1}$ (thick line). If $J_{0,1}>0$ ($J_{0,1}<0$) satisfies Eq. (5), $x_0$ and $x_1$ must align (antialign) in the ground state and $x_0$ can be removed. Right: the remainder graph is shown after the removal. The other bonds emanating from $x_0$ (dashed lines) are now directly connected to $x_1$ (with a sign change if $J_{0,1}<0$). This procedure may lead to a double bond (rule III), as shown here, if $x_1$ was already connected to a neighbor of $x_0$ before.

Figure 3

(Color online) Plot of the efficiency of the reduction steps as a function of bond density $p$ in $d=2$ (left column), $d=3$ (middle column), and $d=4$ (right column) for $\pm J$ bonds (top row), Gaussian bonds without superbond reduction SB according to rule VI (middle row), and Gaussian bonds with SB (bottom row). All efficiencies quickly become independent of system size $L$ with closer-spaced curves corresponding to larger sizes. Rule VI, which is useful only for continuous bonds, does not effect other rules much but adds up to 10% in reduction even at $p=1$ with decreasing effect for larger $d$.

Figure 4

Plot of the probability to obtain any nonempty remainder graph after a complete exhaustion of the reduction rules as a function of bond density $p$ in $d=2$ (left column), $d=3$ (middle column), and $d=4$ (right column) for $\pm J$ bonds (top row), Gaussian bonds without superbond reduction SB according to rule VI (middle row), and Gaussian bonds with SB (bottom row). The sequence of graphs in each plot steepen for increasing system size $L$ from right to left. There is a strong dependence on $L$, and it appears that the probabilities converge to a $0–1$ step function at or near the bond-percolation threshold (indicated by a vertical line). With superbond reduction, rule VI, graphs are far more reducible even significantly above the threshold, at least at finite size.

Figure 5

Plot of the average (fractional) size of the remainder graph (empty or not) as a function of bond density $p$ in $d=2$ (left column), $d=3$ (middle column), and $d=4$ (right column) for $\pm J$ bonds (top row), Gaussian bonds without superbond reduction SB according to Rule VI (middle row), and Gaussian bonds with SB (bottom row). Superbond reduction with rule VI lowers the remainder size near the threshold by about an order of magnitude but with diminishing effects for larger $p$. The sequence of graphs in each plot steepens for increasing system size $L$.

Figure 6

Plot of the average connectivity $⟨\alpha ⟩$ of any nonempty remainder graph as a function of bond density $p$ in $d=2$ (left column), $d=3$ (middle column), and $d=4$ (right column) for $\pm J$ bonds (top row), Gaussian bonds without superbond reduction SB according to rule VI (middle row), and Gaussian bonds with SB (bottom row). The dramatic effect of implementing rule VI becomes apparent near the percolation threshold, especially for increasing $d$. The sequence of graphs in each plot steepens for increasing system size $L$.

Figure 7

Extrapolation plot of approximate ground-state energy densities $⟨e⟩=⟨E⟩/L^2$ for the two-dimensional EA in Eq. (1) as a function of $1/L^2$. Each data point is the average over ${10}^4$ random instances. The results for the DBR heuristic (circles) discussed in the text extrapolate to within 0.5% of the best-known prediction by Campbell-Hartmann-Katzgraber (CHK) (Ref. 39) marked by the horizontal line. Shown are also results obtained with the EO heuristic (squares) (Refs. 22, 23), which reproduces CHK within errors, and a simple alternative to DBR we call least bond reduction (LBR, triangles). LBR also applies rule VI but to the spin with the weakest total bond-weight, i.e., where the sum of all absolute weights of incident bonds is minimal. Both, DBR and LBR, are much faster than EO. LBR is marginally simpler than DBR and avoids the creation of highly connected spins.

Figure 8

Plot of $r_{\text{min}}$ during a run of DBR on a $N={20}^3$ lattice with Gaussian (top) and power-law bonds at $\gamma =1.5$ (bottom).