Zero- and low-temperature behavior of the two-dimensional ±J Ising spin glass

Cluster percolation in the two-dimensional Ising spin glass

Suitable cluster definitions have allowed researchers to describe many ordering transitions in spin systems as geometric phenomena related to percolation. For spin glasses and some other systems with quenched disorder, however, such a connection has not been fully established, and the numerical evidence remains incomplete. Here we use Monte Carlo simulations to study the percolation properties of several classes of clusters occurring in the Edwards-Anderson Ising spin-glass model in two dimensions. The Fortuin-Kasteleyn-Coniglio-Klein clusters originally defined for the ferromagnetic problem do percolate at a temperature that remains nonzero in the thermodynamic limit. On the Nishimori line, this location is accurately predicted by an argument due to Yamaguchi. More relevant for the spin-glass transition are clusters defined on the basis of the overlap of several replicas. We show that various such cluster types have percolation thresholds that shift to lower temperatures by increasing the system size, in agreement with the zero-temperature spin-glass transition in two dimensions. The overlap is linked to the difference in density of the two largest clusters, thus supporting a picture where the spin-glass transition corresponds to an emergent density difference of the two largest clusters inside the percolating phase.

Droplet-scaling versus replica symmetry breaking debate in spin glasses revisited

Simulational studies of spin glasses since the early 2010s have focused on the so-called replicon exponent α as a means of determining whether the low-temperature phase of spin glasses is described by the replica symmetry breaking picture of Parisi or by the droplet-scaling picture. On the latter picture, it should be zero, but we shall argue that it will only be zero for systems of linear dimension L>L^{*}. The crossover length L^{*} may be of the order of hundreds of lattice spacings in three dimensions and approach infinity in six dimensions. We use the droplet-scaling picture to show that the apparent nonzero value of α when L<L^{*} should be 2θ, where θ is the domain wall energy scaling exponent. This formula is in reasonable agreement with the reported values of α.

Ordering behavior of the two-dimensional Ising spin glass with long-range correlated disorder

The standard short-range two-dimensional Ising spin glass is numerically well accessible, in particular, because there are polynomial-time ground-state algorithms. On the other hand, in contrast to higher dimensional spin glasses, it does not exhibit a rich behavior, i.e., no ordered phase at finite temperature. Here, we investigate whether long-range correlated bonds change this behavior. This would still keep the model numerically well accessible while exhibiting a more interesting behavior. The bonds are drawn from a Gaussian distribution with a two-point correlation for bonds at distance r that decays as (1+r^{2})^{-a/2}, a≥0. We study numerically with exact algorithms the ground-state and domain-wall excitations. Our results indicate that the inclusion of bond correlations still does not lead to a spin-glass order at any finite temperature. A further analysis reveals that bond correlations have a strong effect at local length scales, inducing ferro- and antiferromagnetic domains into the system. The length scale of ferro- and antiferromagnetic order diverges exponentially as the correlation exponent approaches a critical value, a→a_{crit}=0. Thus, our results suggest that the system becomes a ferro- or antiferromagnet only in the limit a→0.

From Spin Glasses to Negative-Weight Percolation

Spin glasses are prototypical random systems modelling magnetic alloys. One important way to investigate spin glass models is to study domain walls. For two dimensions, this can be algorithmically understood as the calculation of a shortest path, which allows for negative distances or weights. This led to the creation of the negative weight percolation (NWP) model, which is presented here along with all necessary basics from spin glasses, graph theory and corresponding algorithms. The algorithmic approach involves a mapping to the classical matching problem for graphs. In addition, a summary of results is given, which were obtained during the past decade. This includes the study of percolation transitions in dimension from d=2 up to and beyond the upper critical dimension du=6, also for random graphs. It is shown that NWP is in a different universality class than standard percolation. Furthermore, the question of whether NWP exhibits properties of Stochastic–Loewner Evolution is addressed and recent results for directed NWP are presented.

Binomial Spin Glass

To establish a unified framework for studying both discrete and continuous coupling distributions, we introduce the binomial spin glass, a class of models where the couplings are sums of m identically distributed Bernoulli random variables. In the continuum limit m→∞, the class reduces to one with Gaussian couplings, while m=1 corresponds to the ±J spin glass. We demonstrate that for short-range Ising models on d-dimensional hypercubic lattices the ground-state entropy density for N spins is bounded from above by (sqrt[d/2m]+1/N)ln2, and further show that the actual entropies follow the scaling behavior implied by this bound. We thus uncover a fundamental noncommutativity of the thermodynamic and continuous coupling limits that leads to the presence or absence of degeneracies depending on the precise way the limits are taken. Exact calculations of defect energies reveal a crossover length scale L^{*}(m)∼L^{κ} below which the binomial spin glass is indistinguishable from the Gaussian system. Since κ=-1/(2θ), where θ is the spin-stiffness exponent, discrete couplings become irrelevant at large scales for systems with a finite-temperature spin-glass phase.

From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems

We present a methodology for generating Ising Hamiltonians of tunable complexity and with a priori known ground states based on a decomposition of the model graph into edge-disjoint subgraphs. The idea is illustrated with a spin-glass model defined on a cubic lattice, where subproblems, whose couplers are restricted to the two values {-1,+1}, are specified on unit cubes and are parametrized by their local degeneracy. The construction is shown to be equivalent to a type of three-dimensional constraint-satisfaction problem known as the tiling puzzle. By varying the proportions of subproblem types, the Hamiltonian can span a dramatic range of typical computational complexity, from fairly easy to many orders of magnitude more difficult than prototypical bimodal and Gaussian spin glasses in three space dimensions. We corroborate this behavior via experiments with different algorithms and discuss generalizations and extensions to different types of graphs.

Dynamic scaling in the two-dimensional Ising spin glass with normal-distributed couplings

We carry out simulated annealing and employ a generalized Kibble-Zurek scaling hypothesis to study the two-dimensional Ising spin glass with normal-distributed couplings. The system has an equilibrium glass transition at temperature T=0. From a scaling analysis when T→0 at different annealing velocities v, we find power-law scaling in the system size for the velocity required in order to relax toward the ground state, v∼L^{-(z+1/ν)}, the Kibble-Zurek ansatz where z is the dynamic critical exponent and ν the previously known correlation-length exponent, ν≈3.6. We find z≈13.6 for both the Edwards-Anderson spin-glass order parameter and the excess energy. This is different from a previous study of the system with bimodal couplings [Rubin et al., Phys. Rev. E 95, 052133 (2017)2470-004510.1103/PhysRevE.95.052133] where the dynamics is faster (z is smaller) and the above two quantities relax with different dynamic exponents (with that of the energy being larger). We argue that the different behaviors arise as a consequence of the different low-energy landscapes: for normal-distributed couplings the ground state is unique (up to a spin reflection), while the system with bimodal couplings is massively degenerate. Our results reinforce the conclusion of anomalous entropy-driven relaxation behavior in the bimodal Ising glass. In the case of a continuous coupling distribution, our results presented here also indicate that, although Kibble-Zurek scaling holds, the perturbative behavior normally applying in the slow limit breaks down, likely due to quasidegenerate states, and the scaling function takes a different form.

Temperature Scaling Law for Quantum Annealing Optimizers

Physical implementations of quantum annealing unavoidably operate at finite temperatures. We point to a fundamental limitation of fixed finite temperature quantum annealers that prevents them from functioning as competitive scalable optimizers and show that to serve as optimizers annealer temperatures must be appropriately scaled down with problem size. We derive a temperature scaling law dictating that temperature must drop at the very least in a logarithmic manner but also possibly as a power law with problem size. We corroborate our results by experiment and simulations and discuss the implications of these to practical annealers.

Dual time scales in simulated annealing of a two-dimensional Ising spin glass

We apply a generalized Kibble-Zurek out-of-equilibrium scaling ansatz to simulated annealing when approaching the spin-glass transition at temperature T=0 of the two-dimensional Ising model with random J=±1 couplings. Analyzing the spin-glass order parameter and the excess energy as functions of the system size and the annealing velocity in Monte Carlo simulations with Metropolis dynamics, we find scaling where the energy relaxes slower than the spin-glass order parameter, i.e., there are two different dynamic exponents. The values of the exponents relating the relaxation time scales to the system length, τ∼L^{z}, are z=8.28±0.03 for the relaxation of the order parameter and z=10.31±0.04 for the energy relaxation. We argue that the behavior with dual time scales arises as a consequence of the entropy-driven ordering mechanism within droplet theory. We point out that the dynamic exponents found here for T→0 simulated annealing are different from the temperature-dependent equilibrium dynamic exponent z_{eq}(T), for which previous studies have found a divergent behavior: z_{eq}(T→0)→∞. Thus, our study shows that, within Metropolis dynamics, it is easier to relax the system to one of its degenerate ground states than to migrate at low temperatures between regions of the configuration space surrounding different ground states. In a more general context of optimization, our study provides an example of robust dense-region solutions for which the excess energy (the conventional cost function) may not be the best measure of success.

Ising spin glasses in two dimensions: Universality and nonuniversality

Following numerous earlier studies, extensive simulations and analyses were made on the continuous interaction distribution Gaussian model and the discrete bimodal interaction distribution Ising spin glass (ISG) models in two dimensions [Lundow and Campbell, Phys. Rev. E 93, 022119 (2016)1539-375510.1103/PhysRevE.93.022119]. Here we further analyze the bimodal and Gaussian data together with data on two other continuous interaction distribution two-dimensional ISG models, the uniform and the Laplacian models, and three other discrete interaction distribution models, a diluted bimodal model, an "antidiluted" model, and a more exotic symmetric Poisson model. Comparisons between the three continuous distribution models show that not only do they share the same exponent η≡0 but that to within the present numerical precision they share the same critical exponent ν also, and so lie in a single universality class. On the other hand the critical exponents of the four discrete distribution models are not the same as those of the continuous distributions, and the present data strongly indicate that they differ from one discrete distribution model to another. This is evidence that discrete distribution ISG models in two dimensions have nonzero values of the critical exponent η and do not lie in a single universality class.

Bimodal and Gaussian Ising spin glasses in dimension two

An analysis is given of numerical simulation data to size L=128 on the archetype square lattice Ising spin glasses (ISGs) with bimodal (±J) and Gaussian interaction distributions. It is well established that the ordering temperature of both models is zero. The Gaussian model has a nondegenerate ground state and thus a critical exponent η≡0, and a continuous distribution of energy levels. For the bimodal model, above a size-dependent crossover temperature T(*)(L) there is a regime of effectively continuous energy levels; below T(*)(L) there is a distinct regime dominated by the highly degenerate ground state plus an energy gap to the excited states. T(*)(L) tends to zero at very large L, leaving only the effectively continuous regime in the thermodynamic limit. The simulation data on both models are analyzed with the conventional scaling variable t=T and with a scaling variable τ(b)=T(2)/(1+T(2)) suitable for zero-temperature transition ISGs, together with appropriate scaling expressions. The data for the temperature dependence of the reduced susceptibility χ(τ(b),L) and second moment correlation length ξ(τ(b),L) in the thermodynamic limit regime are extrapolated to the τ(b)=0 critical limit. The Gaussian critical exponent estimates from the simulations, η=0 and ν=3.55(5), are in full agreement with the well-established values in the literature. The bimodal critical exponents, estimated from the thermodynamic limit regime analyses using the same extrapolation protocols as for the Gaussian model, are η=0.20(2) and ν=4.8(3), distinctly different from the Gaussian critical exponents.

Unraveling Quantum Annealers using Classical Hardness

Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealing optimizers that contain hundreds of quantum bits. These optimizers, commonly referred to as 'D-Wave' chips, promise to solve practical optimization problems potentially faster than conventional 'classical' computers. Attempts to quantify the quantum nature of these chips have been met with both excitement and skepticism but have also brought up numerous fundamental questions pertaining to the distinguishability of experimental quantum annealers from their classical thermal counterparts. Inspired by recent results in spin-glass theory that recognize 'temperature chaos' as the underlying mechanism responsible for the computational intractability of hard optimization problems, we devise a general method to quantify the performance of quantum annealers on optimization problems suffering from varying degrees of temperature chaos: A superior performance of quantum annealers over classical algorithms on these may allude to the role that quantum effects play in providing speedup. We utilize our method to experimentally study the D-Wave Two chip on different temperature-chaotic problems and find, surprisingly, that its performance scales unfavorably as compared to several analogous classical algorithms. We detect, quantify and discuss several purely classical effects that possibly mask the quantum behavior of the chip.

Ground-state phase-space structures of two-dimensional ±J spin glasses: A network approach

We illustrate a complex-network approach to study the phase spaces of spin glasses. By mapping the whole ground-state phase spaces of two-dimensional Edwards-Anderson bimodal (±J) spin glasses exactly into networks for analysis, we discovered various phase-space properties. The Gaussian connectivity distribution of the phase-space networks demonstrates that both the number of free spins and the visiting frequency of all microstates follow the Gaussian distribution. The spectra of phase-space networks are Gaussian, which is proven to be exact when the system is infinitely large. The phase-space networks exhibit community structures. By coarse graining to the community level, we constructed a network representing the entropy landscape of the ground state and discovered its scale-free property. The phase-space networks exhibit fractal structures, as a result of the rugged entropy landscape. Moreover, we show that the connectivity distribution, community structures, and fractal structures change drastically at the ferromagnetic-to-glass phase transition. These quantitative measurements of the ground states provide new insight into the study of spin glasses. The phase-space networks of spin glasses share a number of common features with those of lattice gases and geometrically frustrated spin systems and form a new class of complex networks with unique topology.

Measuring free energy in spin-lattice models using parallel tempering Monte Carlo

An efficient and simple approach of measuring the absolute free energy as a function of temperature for spin lattice models using a two-stage parallel tempering Monte Carlo and the free energy perturbation method is discussed and the results are compared with those of population annealing Monte Carlo using the three-dimensional Edwards-Anderson Ising spin glass model as benchmark tests. This approach requires little modification of regular parallel tempering Monte Carlo codes with also little overhead. Numerical results show that parallel tempering, even though using a much less number of temperatures than population annealing, can nevertheless equally efficiently measure the absolute free energy by simulating each temperature for longer times.

Numerically exact correlations and sampling in the two-dimensional Ising spin glass

A powerful existing technique for evaluating statistical mechanical quantities in two-dimensional Ising models is based on constructing a matrix representing the nearest-neighbor spin couplings and then evaluating the Pfaffian of the matrix. Utilizing this technique and other more recent developments in evaluating elements of inverse matrices and exact sampling, a method and computer code for studying two-dimensional Ising models is developed. The formulation of this method is convenient and fast for computing the partition function and spin correlations. It is also useful for exact sampling, where configurations are directly generated with probability given by the Boltzmann distribution. These methods apply to Ising model samples with arbitrary nearest-neighbor couplings and can also be applied to general dimer models. Example results of computations are described, including comparisons with analytic results for the ferromagnetic Ising model, and timing information is provided.

Finite-size scaling in two-dimensional Ising spin-glass models

We study the finite-size behavior of two-dimensional spin-glass models. We consider the ±J model for two different values of the probability of the antiferromagnetic bonds and the model with Gaussian distributed couplings. The analysis of renormalization-group invariant quantities, the overlap susceptibility, and the two-point correlation function confirms that they belong to the same universality class. We analyze in detail the standard finite-size scaling limit in terms of TL(1/ν) in the ±J model. We find that it holds asymptotically. This result is consistent with the low-temperature crossover scenario in which the crossover temperature, which separates the universal high-temperature region from the discrete low-temperature regime, scales as T(c)(L)~L(-θ(S)) with θ(S)≈0.5.