On the ground states of the frustration model of a spin glass by a matching method of graph theory

Universal Fragility of Spin Glass Ground States under Single Bond Changes

We consider the effect of perturbing a single bond on ground states of nearest-neighbor Ising spin glasses, with a Gaussian distribution of the coupling constants, across various two- and three-dimensional lattices and regular random graphs. Our results reveal that the ground states are strikingly fragile with respect to such changes. Altering the strength of only a single bond beyond a critical threshold value leads to a new ground state that differs from the original one by a droplet of flipped spins whose boundary and volume diverge with the system size-an effect that is reminiscent of the more familiar phenomenon of disorder chaos. These elementary fractal-boundary zero-energy droplets and their composites feature robust characteristics and provide the lowest-energy macroscopic spin-glass excitations. Remarkably, within numerical accuracy, the size of such droplets conforms to a universal power-law distribution with exponents that depend on the spatial dimension of the system. Furthermore, the critical coupling strengths adhere to a stretched exponential distribution that is predominantly determined by the local coordination number.

Metastate analysis of the ground states of two-dimensional Ising spin glasses

Using an efficient polynomial-time ground-state algorithm we investigate the Ising spin glass state at zero temperature in two dimensions. For large sizes, we show that the spin state in a central region is independent of the interactions far away, indicating a "single-state" picture, presumably the droplet model. Surprisingly, a single power law describes corrections to this result down to the smallest sizes studied.

Criticality and conformality in the random dimer model

In critical systems, the effect of a localized perturbation affects points that are arbitrarily far from the perturbation location. In this paper, we study the effect of localized perturbations on the solution of the random dimer problem in two dimensions. By means of an accurate numerical analysis, we show that a local perturbation of the optimal covering induces an excitation whose size is extensive with finite probability. We compute the fractal dimension of the excitations and scaling exponents. In particular, excitations in random dimer problems on nonbipartite lattices have the same statistical properties of domain walls in spin glass. Excitations produced in bipartite lattices, instead, are compatible with a loop-erased self-avoiding random walk process. In both cases, we find evidence of conformal invariance of the excitations that is compatible with SLE_{κ} with parameter κ depending on the bipartiteness of the underlying lattice only.

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.

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.

Information-theoretic approach to ground-state phase transitions for two- and three-dimensional frustrated spin systems

The information-theoretic observables entropy (a measure of disorder), excess entropy (a measure of complexity), and multi-information are used to analyze ground-state spin configurations for disordered and frustrated model systems in two and three dimensions. For both model systems, ground-state spin configurations can be obtained in polynomial time via exact combinatorial optimization algorithms, which allowed us to study large systems with high numerical accuracy. Both model systems exhibit a continuous transition from an ordered to a disordered ground state as a model parameter is varied. By using the above information-theoretic observables it is possible to detect changes in the spatial structure of the ground states as the critical point is approached. It is further possible to quantify the scaling behavior of the information-theoretic observables in the vicinity of the critical point. For both model systems considered, the estimates of critical properties for the ground-state phase transitions are in good agreement with existing results reported in the literature.

Generalized Monte Carlo loop algorithm for two-dimensional frustrated Ising models

We introduce a generalized loop move (GLM) update for Monte Carlo simulations of frustrated Ising models on two-dimensional lattices with bond-sharing plaquettes. The GLM updates are designed to enhance Monte Carlo sampling efficiency when the system's low-energy states consist of an extensive number of degenerate or near-degenerate spin configurations, separated by large energy barriers to single spin flips. Through implementation on several frustrated Ising models, we demonstrate the effectiveness of the GLM updates in cases where both degenerate and near-degenerate sets of configurations are favored at low temperatures. The GLM update's potential to be straightforwardly extended to different lattices and spin interactions allows it to be readily adopted on many other frustrated Ising models of physical relevance.

Preparing ground States of quantum many-body systems on a quantum computer

Preparing the ground state of a system of interacting classical particles is an NP-hard problem. Thus, there is in general no better algorithm to solve this problem than exhaustively going through all N configurations of the system to determine the one with lowest energy, requiring a running time proportional to N. A quantum computer, if it could be built, could solve this problem in time sqrt[N]. Here, we present a powerful extension of this result to the case of interacting quantum particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.

Exact ground states of large two-dimensional planar Ising spin glasses

Studying spin-glass physics through analyzing their ground-state properties has a long history. Although there exist polynomial-time algorithms for the two-dimensional planar case, where the problem of finding ground states is transformed to a minimum-weight perfect matching problem, the reachable system sizes have been limited both by the needed CPU time and by memory requirements. In this work, we present an algorithm for the calculation of exact ground states for two-dimensional Ising spin glasses with free boundary conditions in at least one direction. The algorithmic foundations of the method date back to the work of Kasteleyn from the 1960s for computing the complete partition function of the Ising model. Using Kasteleyn cities, we calculate exact ground states for huge two-dimensional planar Ising spin-glass lattices (up to 3000;{2} spins) within reasonable time. According to our knowledge, these are the largest sizes currently available. Kasteleyn cities were recently also used by Thomas and Middleton in the context of extended ground states on the torus. Moreover, they show that the method can also be used for computing ground states of planar graphs. Furthermore, we point out that the correctness of heuristically computed ground states can easily be verified. Finally, we evaluate the solution quality of heuristic variants of the L. Bieche approach.

Inference from matrix products: a heuristic spin-glass algorithm

We present an algorithm for finding ground states of two-dimensional spin-glass systems based on ideas from matrix product states in quantum information theory. The algorithm works directly at zero temperature and defines an approximation to the energy whose accuracy depends on a parameter k. We test the algorithm against exact methods on random field and random bond Ising models, and we find that accurate results require a k which scales roughly polynomially with the system size. The algorithm also performs well when tested on small systems with arbitrary interactions, where no fast, exact algorithms exist. The time required is significantly less than Monte Carlo schemes.

Genetic embedded matching approach to ground states in continuous-spin systems

Due to an extremely rugged structure of the free energy landscape, the determination of spin-glass ground states is among the hardest known optimization problems, found to be NP hard in the most general case. Owing to the specific structure of local (free) energy minima, general-purpose optimization strategies perform relatively poorly on these problems, and a number of specially tailored optimization techniques have been developed in particular for the Ising spin glass and similar discrete systems. Here, an efficient optimization heuristic for the much less discussed case of continuous spins is introduced, based on the combination of an embedding of Ising spins into the continuous rotators and an appropriate variant of a genetic algorithm. Statistical techniques for insuring high reliability in finding (numerically) exact ground states are discussed, and the method is benchmarked against the simulated annealing approach.

Efficient algorithm for random-bond ising models in 2D

We present an efficient algorithm for calculating the properties of Ising models in two dimensions, directly in the spin basis, without the need for mapping to fermion or dimer models. The algorithm computes the partition function and correlation functions at a single temperature on any planar network of N Ising spins in O(N;{3/2}) time or less. The method can handle continuous or discrete bond disorder and is especially efficient in the case of bond or site dilution, where it executes in O(NlnN) time near the percolation threshold. We demonstrate its feasibility on the ferromagnetic Ising model and the +/-J random-bond Ising model and discuss the regime of applicability in cases of full frustration such as the Ising antiferromagnet on a triangular lattice.

Ground states and defect energies of the two-dimensional XY spin glass from a quasiexact algorithm

We employ a novel algorithm using a quasiexact embedded-cluster matching technique as minimization method within a genetic algorithm to reliably obtain numerically exact ground states of the Edwards-Anderson XY spin-glass model with bimodal coupling distribution for square lattices of up to 28 x 28 spins. Contrary to previous conjectures, the ground state of each disorder replica is nondegenerate up to a global O(2) rotation. The scaling of spin and chiral defect energies induced by applying several different sets of boundary conditions exhibits strong crossover effects. This suggests that previous calculations have yielded results far from the asymptotic regime. The novel algorithm and the aspect-ratio scaling technique consistently give theta(s)=-0.308(30) and theta(c)=-0.114(16) for the spin and chiral stiffness exponents, respectively.

General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results

We survey and summarize the literature on the computational aspects of neural network models by presenting a detailed taxonomy of the various models according to their complexity theoretic characteristics. The criteria of classification include the architecture of the network (feedforward versus recurrent), time model (discrete versus continuous), state type (binary versus analog), weight constraints (symmetric versus asymmetric), network size (finite nets versus infinite families), and computation type (deterministic versus probabilistic), among others. The underlying results concerning the computational power and complexity issues of perceptron, radial basis function, winner-take-all, and spiking neural networks are briefly surveyed, with pointers to the relevant literature. In our survey, we focus mainly on the digital computation whose inputs and outputs are binary in nature, although their values are quite often encoded as analog neuron states. We omit the important learning issues.

Corrections to scaling are large for droplets in two-dimensional spin glasses

The energy of a droplet of linear extent l in the droplet theory of spin glasses goes as l(theta) for large l. It is shown by numerical studies of large droplets in two-dimensional systems that this formula needs to be modified by the addition of a scaling correction l(-omega) in order to accurately describe droplet energies at the length scales currently probed in numerical simulations. Using this simple modification, it is now possible to explain many results which have been found in simulations of three-dimensional Ising spin glasses with the droplet model.

On the computational complexity of binary and analog symmetric hopfield nets

We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this problem in the case of binary nets. Finally, we show that symmetric analog nets with an external clock are computationally Turing universal.

Ground-state degeneracies of Ising spin glasses on diamond hierarchical lattices

The total number of ground states for short-range Ising spin glasses, defined on diamond hierarchical lattices of fractal dimensions d=2, 3, 4, 5, and 2.58, is estimated by means of analytic calculations (three last hierarchy levels of the d=2 lattice) and numerical simulations (lower hierarchies for d=2 and all remaining cases). It is shown that in the case of continuous probability distributions for the couplings, the number of ground states is finite in the thermodynamic limit. However, for a bimodal probability distribution (+/-J with probabilities p and 1-p, respectively), the average number of ground states is maximum for a wide range of values of p around p=1 / 2 and depends on the total number of sites at hierarchy level n, Nn. In this case, for all lattices investigated, it is shown that the ground-state degeneracy behaves like exp[h(d)Nn], in the limit Nn large, where h(d) is a positive number which depends on the lattice fractal dimension. The probability of finding frustrated cells at a given hierarchy level n, Fn(p), is calculated analytically (three last hierarchy levels for d=2 and the last hierarchy of the d=3 lattice, with 0<or=p<or=1), as well as numerically (all other cases, with p=1 / 2). Except for d=2, in which case Fn(1 / 2) increases by decreasing the hierarchy level, all other dimensions investigated present an exponential decrease in Fn(1 / 2) for decreasing values of n. For d=2 our results refer to the paramagnetic phase, whereas for all other dimensions considered [which are greater than the lower critical dimension dl (dl approximately 2.5)], our results refer to the spin-glass phase at zero temperature; in the latter cases h(d) increases with the fractal dimension. For n>>1, only the last hierarchies contribute significantly to the ground-state degeneracy; such a dominant behavior becomes stronger for high fractal dimensions. The exponential increase of the number of ground states with the total number of sites is in agreement with the mean-field picture of spin glasses.

Complexity of protein folding

It is believed that the native folded three-dimensional conformation of a protein is its lowest free energy state, or one of its lowest. It is shown here that both a two- and three-dimensional mathematical model describing the folding process as a free energy minimization problem is NP-hard. This means that the problem belongs to a large set of computational problems, assumed to be very hard ("conditionally intractable"). Some of the possible ramifications of this result are speculated upon.