Limited resources motivate decomposing large-scale problems into smaller, "local" subsystems and stitching together the so-found solutions. We explore the physics underlying this approach and discuss the concept of "local hardness," i.e., the complexity of predicting local properties of the solution from local information, for the ground-state problem of both P- and NP-hard spin glasses and related frustrated spin systems. Depending on the model considered, we observe varying scaling behaviors in how errors associated with local predictions decay as a function of the size of the solved subsystem. These errors are intimately connected to global critical threshold instabilities, characterized by gapless, avalanchelike excitations that follow scale-invariant size distributions. Away from criticality, local solvers quickly achieve high accuracy, aligning closely with the results of the computationally much more expensive global minimization. We leverage these findings to introduce a heuristic contraction-based algorithm for globally studying spin-glass ground states. The local solvers further display sharp imprints of the phase transition from the spin-glass to the ferromagnetic phase as the distribution of spin-glass couplings is shifted, as well as characteristic differences for the infinite-range model, implying the existence of specific classes of local hardness. Our findings shed light on how nature may operate solely through local actions at her disposal.
Limited resources motivate decomposing large-scale problems into smaller, "local" subsystems and stitching together the so-found solutions. We explore the physics underlying this approach and discuss the concept of "local hardness," i.e., the complexity of predicting local properties of the solution from local information, for the ground-state problem of both P- and NP-hard spin glasses and related frustrated spin systems. Depending on the model considered, we observe varying scaling behaviors in how errors associated with local predictions decay as a function of the size of the solved subsystem. These errors are intimately connected to global critical threshold instabilities, characterized by gapless, avalanchelike excitations that follow scale-invariant size distributions. Away from criticality, local solvers quickly achieve high accuracy, aligning closely with the results of the computationally much more expensive global minimization. We leverage these findings to introduce a heuristic contraction-based algorithm for globally studying spin-glass ground states. The local solvers further display sharp imprints of the phase transition from the spin-glass to the ferromagnetic phase as the distribution of spin-glass couplings is shifted, as well as characteristic differences for the infinite-range model, implying the existence of specific classes of local hardness. Our findings shed light on how nature may operate solely through local actions at her disposal.
Spin glasses are disordered magnets with random interactions that are, generally, in conflict with each other. Finding the ground states of spin glasses is not only essential for the understanding of the nature of disordered magnetic and other physical systems, but also useful to solve a broad array of hard combinatorial optimization problems across multiple disciplines. Despite decades-long efforts, an algorithm with both high accuracy and high efficiency is still lacking. Here we introduce DIRAC - a deep reinforcement learning framework, which can be trained purely on small-scale spin glass instances and then applied to arbitrarily large ones. DIRAC displays better scalability than other methods and can be leveraged to enhance any thermal annealing method. Extensive calculations on 2D, 3D and 4D Edwards-Anderson spin glass instances demonstrate the superior performance of DIRAC over existing methods. As many hard combinatorial optimization problems have Ising spin glass formulations, our results suggest a promising tool in solving these hard problems. Moreover, the presented algorithm will help us better understand the nature of the low-temperature spin-glass phase, which is a fundamental challenge in statistical physics.
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.
Spin glasses are disordered magnets with random interactions that are, generally, in conflict with each other. Finding the ground states of spin glasses is not only essential for understanding the nature of disordered magnets and many other physical systems, but also useful to solve a broad array of hard combinatorial optimization problems across multiple disciplines. Despite decades-long efforts, an algorithm with both high accuracy and high efficiency is still lacking. Here we introduce DIRAC - a deep reinforcement learning framework, which can be trained purely on small-scale spin glass instances and then applied to arbitrarily large ones. DIRAC displays better scalability than other methods and can be leveraged to enhance any thermal annealing method. Extensive calculations on 2D, 3D and 4D Edwards-Anderson spin glass instances demonstrate the superior performance of DIRAC over existing methods. The presented framework will help us better understand the nature of the low-temperature spin-glass phase, which is a fundamental challenge in statistical physics. Moreover, the gauge transformation technique adopted in DIRAC builds a deep connection between physics and artificial intelligence. In particular, this opens up a promising avenue for reinforcement learning models to explore in the enormous configuration space, which would be extremely helpful to solve many other hard combinatorial optimization problems.
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.
Frustrated spin systems exhibit a wide range of phenomena such as novel phases, residual entropy and glassy dynamics. In contrast to the usual assumption of universality, microscopic details such as the underlying lattice structure often play a crucial role in these systems. In this dissertation the frustrated J1-J2 Ising model on the honeycomb lattice is considered. Earlier work shows that the coupling ratio R = J2 /|J1 | = −1/4 separates regions of two different ground states. Above this threshold the ground state is (anti-)ferromagnetically ordered for (anti-)ferromagnetic J1 , whereas below it infinitely many states of minimal energy exist. A recent Monte Carlo (MC) study by Žukovič finds a continuous transition with Ising critical exponents for R ≥ −0.2, leaving open the question of criticality for −1/4 < R < −0.2, for which the study was obfuscated by the presence of strong metastability. The regime with the highly degenerate ground states (R < −1/4), on the other hand, is characterized by feature-rich specific heat curves, and slow low-temperature dynamics reminiscent of spin glasses, although there is no disorder in this system. Prior to this work, no order parameter has been identified, and there is no clear understanding of its potentially critical behavior. Here, the question of criticality for −1/4 < R < −0.2 is addressed, and Ising universality is found for lower values of R, namely, at least for R ≥ −0.23. This result is achieved by carrying out finite-size scaling analyses of response functions like the magnetic susceptibility, and of the complex partition function zeros. In both cases, the underlying numerical data was generated using population annealing (PA) MC, a framework devised for spin glasses but generally applicable to systems with metastability. Furthermore, the region of degenerate ground states is studied using different boundary conditions, which are found to strongly affect the thermodynamic observations. A broken symmetry at zero temperature is identified, which can be quantified using a complex nematic order parameter. The MC data are consistent with a continuous symmetry-breaking transition. However, due to the limited system sizes that could be studied, and the presence of strong finite-size effects, one cannot rule out a higher-order transition or a cross-over without any singularities. In the process of studying this system, also the understanding of the PA framework was further developed. Specifically, the role of the resampling step in the algorithm was investigated. While it is crucial for efficient equilibration, no benefit is found in noisier resampling schemes such as the multinomial resampling method. Instead, two resampling schemes, which have the lowest sampling variance, are identified as preferential.:1 Introduction I Background and Methodology 2 Background 2.1 Fundamentals of Statistical Mechanics 2.1.1 Equilibrium ensembles 2.1.2 Phase transitions and critical behavior 2.1.3 Common spin models 2.2 Frustrated Spin Models 2.2.1 Frustrated J1-J2 Ising model on the square lattice 2.2.2 Gonihedric model in two dimensions 2.3 Monte Carlo Simulations 2.3.1 Fundamentals 2.3.2 Autocorrelation and error bars in MCMC time series 2.3.3 Possible implementations 2.3.4 Generalized ensemble methods 3 Methodology 3.1 General Algorithmic Design 3.2 Population Annealing 3.2.1 Algorithm 3.2.2 Assessing population annealing performance 3.2.3 Adaptive temperature steps 3.2.4 Weighted averages 3.2.5 Population annealing and first-order transitions 3.3 Estimating Critical Exponents from Finite Systems 3.3.1 Standard finite size scaling 3.3.2 Complex partition function zeros II Results 4 Algorithmic Improvements and Extensions to the Population Annealing Framework 4.1 Resampling Step in Population Annealing 4.1.1 Conceptual overview 4.1.2 Possible resampling methods 4.1.3 Benchmarking different resampling methods 4.1.4 Simulation results 4.1.5 PA simulations with finite populations in the limit of perfect equilibration 4.1.6 PA simulations in the limit of infinite populations and perfect equilibration 4.1.7 Conclusion 4.2 Using Population Annealing on Many Computing Nodes 4.2.1 Literature overview and different rebalancing schemes 4.2.2 Simulations of simulations 4.2.3 Conclusion and outlook 4.3 Adaptive Number of Spin Updates in Population Annealing 4.4 Microcanonical Population Annealing 5 The Frustrated J1-J2 Ising Model on the Honeycomb Lattice 5.1 Overview 5.2 Regime of Ising Universality Class 5.2.1 Finite-size scaling analysis 5.2.2 Energy barriers 5.2.3 Exploring the complex partition function zeros 5.3 Finite Ground State Entropy per Spin for J2/|J1| = −1/4 5.4 Highly Degenerate Striped Phase for J2/|J1| < −1/4 5.4.1 Boundary conditions 5.4.2 Energy minimization and ground states 5.4.3 Topological defects 5.4.4 Observables 5.4.5 Simulation details 5.4.6 Simulation results for R = −0.5 5.4.7 Simulation results for R = −1 5.4.8 Discussion 5.4.9 Conclusion and outlook 6 Parallel tempering and its infinite-swap limit 6.1 Formalism 6.2 Details on Implementation 6.3 Numerical Results from INS-PT Simulations 6.3.1 One-dimensional Ising model 6.3.2 Two-dimensional Ising model 6.3.3 q-state Potts model 6.3.4 Lennard-Jones clusters 6.4 Discussion 7 Conclusions and outlook Bibliography Appendices A Algorithmic Improvements and Extensions to the Population Annealing framework: Further details A.1 Generating correlated energy time series B J1-J2 honeycomb Ising model: Further plots and details B.1 GPU domain decomposition B.2 Finite-size scaling using Metropolis population annealing B.3 The decoupled antiferromagnet limit B.4 Zero temperature value of the nematic order parameter B.5 Percolation properties for J2 = −0.5 B.6 Binder parameter of the one-dimensional Ising model C Application for Ethical Approval
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.