This thesis is an attempt to provide a new outlook on complex systems, as well as some physical answers for certain models, taking a computational approach. We have focused on disordered systems, addressing two traditional problems in three spatial dimensions: the Edwards-Anderson spin glass and the Diluted Antiferromagnet in a Field (the physical realisation of the random-field Ising model). These systems have been studied by means of large-scale Monte Carlo simulations, exploiting a variety of platforms, which include the Janus special-purpose supercomputer. Two main themes are explored throughout: a) the relationship between the (experimentally unreachable) equilibrium phase and the non-equilibrium evolution and b) the computation and efficient treatment of rugged free-energy landscapes. We perform a thorough study of the low-temperature phase of the D=3 Edwards-Anderson spin glass, where we establish a time-length dictionary and a finite-time scaling formalism to link, in a quantitative way, the experimental non-equilibrium regime and the finite-size equilibrium phase. At the experimentally relevant scales, the replica symmetry breaking theory emerges as the appropriate theoretical picture. We also introduce Tethered Monte Carlo, a general strategy for the study of systems with rugged free-energy landscapes. This formalism provides a general method to guide the exploration of the configuration space by constraining one or more reaction coordinates. From these tethered simulations, the Helmholtz potential associated to the reaction coordinates is reconstructed, yielding all the information about the system. We use this method to provide a comprehensive picture of the critical behaviour in the Diluted Antiferromagnet in a Field.
This thesis is an attempt to provide a new outlook on complex systems, as well as some physical answers for certain models, taking a computational approach. We have focused on disordered systems, addressing two traditional problems in three spatial dimensions: the Edwards-Anderson spin glass and the Diluted Antiferromagnet in a Field (the physical realisation of the random-field Ising model). These systems have been studied by means of large-scale Monte Carlo simulations, exploiting a variety of platforms, which include the Janus special-purpose supercomputer. Two main themes are explored throughout: a) the relationship between the (experimentally unreachable) equilibrium phase and the non-equilibrium evolution and b) the computation and efficient treatment of rugged free-energy landscapes. We perform a thorough study of the low-temperature phase of the D=3 Edwards-Anderson spin glass, where we establish a time-length dictionary and a finite-time scaling formalism to link, in a quantitative way, the experimental non-equilibrium regime and the finite-size equilibrium phase. At the experimentally relevant scales, the replica symmetry breaking theory emerges as the appropriate theoretical picture. We also introduce Tethered Monte Carlo, a general strategy for the study of systems with rugged free-energy landscapes. This formalism provides a general method to guide the exploration of the configuration space by constraining one or more reaction coordinates. From these tethered simulations, the Helmholtz potential associated to the reaction coordinates is reconstructed, yielding all the information about the system. We use this method to provide a comprehensive picture of the critical behaviour in the Diluted Antiferromagnet in a Field.
Disorder is present in many systems in nature and in many different versions. For instance, the dislocations of a crystal lattice, or the randomness of the interaction between magnetic moments. One of the most studied examples is that of spin glasses because they are simple to model but keep most of the very complex features that many disordered systems have. The frustration of the ground state configuration is responsible for the existence of a gap less spectrum of excitations and a rugged and complex free-energy landscape which bring about a very slow relaxation towards the equilibrium state. The main concern of the thesis has been to study what the properties of the typical excitation, i.e. those excitations that are large and contribute dominantly to the physics in the frozen phase. The existence of these large excitations brings about large fluctuations of the order parameter, and we have shown in these theses that this feature can be exploited to study the transition of any spin glass model. Moreover, we have shown that the information about these excitations can be extracted from the statistics of the lowest lying excitations. This is because due to the random nature of spin glasses, the physics obtained from averaging over the whole spectrum of excitations of an infinite sample is equivalent to averaging over many finite systems where only the ground state and the first excitation are considered. The novelty of this approach is that we do not need to make any assumption on what are typical excitations like because we can compute them exactly using numerical methods. Finally, we have investigated the dynamics and more specifically the link between the problem of chaos and the rejuvenation phenomena observed experimentally. Rejuvenation means that when lowering the temperature the aging process restarts again from scratch. This is potentially linked with the chaos assumption which states that equilibrium configurations at two different properties are not correlated. Chaos is a large scale phenomenon possible if entropy fluctuations are large. However, in this thesis we have shown that the response to temperature changes can be large in the absence of chaos close to a localization transition where the Boltzmann weight condenses in a few states. This has been observed in simulation of the Sinai model in which this localization is realized dynamically. In this model, since at low temperatures the system gets trapped in the very deep states, the dynamics is only local, so that only small excitations contribute to the rejuvenation signal that we have been able to observe. Thus, in agreement with the hierarchical picture, rejuvenation is possible even in the absence of chaos and reflects the start of the aging process of small length scales.
The main subjects of this dissertation are spin glass applications in other disciplines and spin glass algorithms. Spin glasses are magnetic systems with disorder and frustration, and the essential physics of spin glasses lies not in the details of their microscopic interactions but rather in the competition between quenched ferromagnetic and antiferromagnetic interactions. Concepts that arose in the study of spin glasses have led to applications in areas as diverse as computer science, biology, and finance, as well as a variety of others.\n\nIn the first part of this dissertation I study the equilibrium and non-equilibrium properties of Boolean decision problems with competing interactions on scale-free networks in an external bias (a magnetic field). First, I perform finite-temperature Monte Carlo simulations in a field to test the robustness of the spin-glass phase and I show that the system has a spin-glass phase in a field, i.e., it exhibits a de Almeida–Thouless line. Then I study avalanche distributions when the system is driven by a field at zero temperature to test whether the system displays self-organized criticality. The numerical results suggest that avalanches (damage) can spread across the entire system with nonzero probability when the decay exponent of the interaction degree is less than or equal to 2, i.e., that Boolean decision problems on scale-free networks with competing interactions can be fragile when the system is not in thermal equilibrium.\n\nIn the second part of this dissertation I discuss the best-case performance of quantum annealers on native spin-glass benchmarks, i.e., how chaos can affect success probabilities. We perform classical parallel-tempering Monte Carlo simulations of the archetypal benchmark problem, an Ising spin glass, on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, I study the best-case resilience, or the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We compute the upper-bound success probabilities for different instance classes based on these simple error models, and I present strategies for developing robust and hard benchmark instances.\n\nIn the third part of this dissertation I present a cluster algorithm for Ising spin glasses that works in any space dimension and speeds up thermalization by several orders of magnitude at temperatures where thermalization is typically difficult. Our isoenergetic cluster moves are based on the Houdayer cluster algorithm for two-dimensional spin glasses and lead to a speedup over conventional state-of-the-art methods that increases with the system size. We illustrate the benefits (improved thermalization and achievement of more equiprobable sampling of ground states) of the isoenergetic cluster moves in two and three space dimensions, as well as in the nonplanar Chimera topology found in the D-Wave quantum annealing machine.\n\nFinally, I study the thermodynamic properties of the two-dimensional Edwards-Anderson Ising spin-glass model on a square lattice using the tensor renormalization group method based on a higher-order singular-value decomposition. Our estimates of the partition function without a high precision data type lead to negative values at very low temperatures, thus illustrating that the method can not be applied to frustrated magnetic systems.
We present a collection of simulations of the Edwards–Anderson lattice spin glass at T=0 to elucidate the nature of low-energy excitations over a range of dimensions that reach from physically realizable systems to the mean-field limit. Using heuristic methods, we sample the ground states of instances to determine their energies while eliciting excitations through manipulating boundary conditions. We exploit the universality of the phase diagram of bond-diluted lattices to make such a study in higher dimensions computationally feasible. As a result, we obtain a variety of accurate exponents for domain wall stiffness and finite-size corrections, which allow us to examine their dimensional behavior and their connection with predictions from mean-field theory. We also provide an experimentally testable prediction for the thermal-to-percolative crossover exponent in dilute lattice Ising spin glasses.
Spin glasses have been the subject of intense study and considerable controversy for decades, and the low-temperature phase of short-range spin glasses is still poorly understood. Our main goal is to improve our understanding in this area and find an answer to the following question: Are there only a single pair or a countable infinity of pure states in the low temperature phase of the EA spin glass? To that aim we first start by introducing spin glasses and provide a brief history of their research, then proceed to describe our method of simulation, the parallel tempering Monte Carlo algorithm. Next, we present the results of a large-scale numerical study of the equilibrium three-dimensional Edwards-Anderson Ising spin glass with Gaussian disorder. In order to understand how the parallel tempering algorithm works, we measure various static, as well as dynamical quantities, such as the autocorrelation times and round-trip times for the parallel tempering Monte Carlo method. We examine the correlation between static and dynamic observables for _ 5000 disorder realizations and up to 1000 spins down to temperatures at 20% of the critical temperature, and our results show that autocorrelation times are directly correlated with the roughness of the free-energy landscape. In the following chapters, the three- and four-dimensional Edwards-Anderson and mean-field Sherrington-Kirkpatrick Ising spin glasses are studied again via large-scale Monte Carlo simulations at low temperatures, deep within the spinglass phase. Performing a careful statistical analysis of several thousand independent disorder realizations and using an observable that detects peaks in the overlap distribution, we show that the Sherrington-Kirkpatrick and Edwards-Anderson models have a distinctly different low-temperature behavior. We arrive to the following conclusion: The structure of the spin-glass overlap distribution for the Edwards-Anderson model suggests that its low-temperature phase has only a single pair of pure states. Finally we present results for several new observables, along with a few preliminary studies and suggestions for future research.
Spin glasses are disordered magnetic systems that have frustration. The most interesting feature of the physical properties of spin glasses is the complex structure of phase space that is caused by the competition between the quenched ferromagnetic and antiferromagnetic interactions of spin pairs. The popularity of spin glasses is two-fold. First of all, the extremely complicated energy landscapes built from the frustration among spin interactions gives spin glasses new properties that have never been seen in other ordered systems. One of these properties is a new transition between the paramagnetic phase and a disordered phase, the spin-glass phase. This new phenomenon triggers scientists' enthusiasm for deeply understanding the physical foundations and mathematical description for disordered systems such as spin glasses. Secondly, because analytical methods can no longer offer enough support for studying disordered systems, scientists use numerical tools like Markov-chain Monte Carlo to simulate the thermodynamics of the systems of interest as well as statistical methods to process big data generated from the simulations. Therefore, the research on such complex systems introduces a new paradigm to statistical physics and also opens a window into an overlapping area between computational physics and information science, which makes an interdisciplinary study necessary and helpful. \n\n\n\n I devote my research to this new interdisciplinary area by seeking new connections in both models and algorithms. This dissertation consists of two themes. The first theme is about the research of spin glasses, including a study on the universality of a diluted spin-glass model and the development of algorithms by introducing new tools from artificial intelligence and extending the current algorithms for more general use. I demonstrate that to detect the phase transition in a spin-glass model we can train convolutional neural networks with a different spin-glass model. Then, use the convolutional neural networks to precisely predict the phase transition of the model. I also show that by training the convolutional neural networks with poisoned data, the results can be very unpredictable. Next, I introduce research in modifying the isoenergetic cluster moves for highly connected topologies in spin glasses. The numerical results show that isoenergetic cluster moves can only be effective for graphs with low connectivities due to the relatively small percolation thresholds in topologies with high connectivities and the trade-off between the cluster size and acceptance rate forced by the detailed balance condition. To conclude the first theme, I study the universality of the two dimensional Ising model with bond dilution. This project is inspired by a debate in the grey area that is not covered by Harris criterion: the universality of a two-dimensional Ising model with disorder can not be theoretically explained. The simulation results for the two-dimensional Ising model with bond dilution show that the critical exponent of the correction to the correlation length does not change with disorder, which supports the strong universality scenario. The second theme of this dissertation is the study of the Boolean satisfiability problem through the use of Ising spin form. The Boolean satisfiability problem is the problem of determining if there exists an assignment of Boolean variables that satisfies a given Boolean formula. Considering that there are rarely global algorithms for the Boolean satisfiability problem and that the NP-complete Ising spin glass is written in Boolean variables as well, I use Monte Carlo simulations to find the optimal solutions for the Boolean satisfiability problem by implementing the Metropolis algorithm combined with the Parallel tempering algorithm. The advantage of this method is that the ergodicity of the thermodynamic procedure makes this algorithm global, which can help search for optimal solutions through the entire configuration space. The numerical results show that this physical algorithm has an obvious advantage over the current state-of-art algorithms on a derivative problem, the Boolean maximum satisfiability problem. Finally, I introduce my research on the Boolean satisfiability problem-based membership filter. Since the physical approach has the ability of globally seeking solutions it can help find uncorrelated solutions for the Boolean satisfiability problem-based membership filter, which is the key to improving efficiency for this new filter. Furthermore, I improve the efficiency of the filter by turning the Boolean satisfiability instance into a not-all-equal form to guarantee that the solutions found by our algorithm, Borealis, are uncorrelated. The numerical results show that the efficiency of Boolean satisfiability-based filter can be significantly improved while keeping the false positive rate low.
The statics-dynamics correspondence in spin glasses relate non-equilibrium results on large samples (the experimental realm) with equilibrium quantities computed on small systems (the typical arena for theoretical computations). Here we employ statics-dynamics equivalence to study the Ising spin-glass critical behavior in three dimensions. By means of Monte Carlo simulation, we follow the growth of the coherence length (the size of the glassy domains), on lattices too large to be thermalized. Thanks to the large coherence lengths we reach, we are able to obtain accurate results in excellent agreement with the best available equilibrium computations. To do so, we need to clarify the several physical meanings of the dynamic exponent close to the critical temperature.