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.
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.
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.
Spin glasses are experiencing a revival due to applications in quantum information\ntheory. In particular, they are the archetypal native benchmark problem for quantum annealing\nmachines. Furthermore, they find applications in fields as diverse as satisfiability,\nneural networks, and general combinatorial optimization problems. As such, developing\nand improving algorithms and methods to study these computationally complex systems\nis of paramount importance to many disciplines. This body of work attempts to attack\nthe problem of solving combinatorial optimization problems by simulating spin glasses\nfrom three sides: classical algorithm development, suggestions for quantum annealing\ndevice design, and improving measurements in realistic physical systems with inherent\nnoise. I begin with the introduction of a cluster algorithm based on Houdayer’s cluster algorithm\nfor two-dimensional Ising spin-glasses that is applicable to any space dimension\nand speeds up thermalization by several orders of magnitude at low temperatures where\nprevious algorithms have difficulty. I show improvement for the D-Wave chimera topology\nand the three-dimensional cubic lattice that increases with the size of the problem.\nOne consequence of adding cluster moves is that for problems with degenerate solutions,\nground-state sampling is improved. I demonstrate an ergodic algorithm to sample ground\nstates through the use of simple Monte Carlo with parallel tempering and cluster moves.\nIn addition, I present a non-ergodic algorithm to generate new solutions from a bank of\nknown solutions. I compare these results against results from quantum annealing utilizing\nthe D-Wave Inc. quantum annealing device. Finally, I present an algorithm for improving\nthe recovery of ground-state solutions from problems with noise by using thermal fluctuations\nto infer the correct solution at the Nishimori temperature. While this method has been\ndemonstrated analytically and numerically for trivial ferromagnetic and Gaussian distributions, a useful metric for more complex Gaussian distributions with added Gaussian noise\nis unavailable. We show improved recovery of numerical solutions on the chimera graph\nwith a ferromagnetic distribution and added Gaussian noise. Next, I direct my focus to the\ndesign of future generations of quantum annealers. The first design is the two-dimensional\nsquare-lattice bimodal spin glass with next-nearest ferrromagnetic interactions proposed\nby Lemke and Campbell claimed to exhibit a finite-temperature spin-glass state for a particular\nrelative strength of the next-nearest to nearest neighbor interactions. Our results\nfrom finite-temperature simulations show the system is in a paramagnetic state in the thermodynamic\nlimit, thus not useful for quantum annealing device designs that would benefit\nfrom a spin-glass phase transition. The second design is the diluted next-nearest neighbor\nIsing spin-glass with Gaussian interactions in an attempt to improve the estimation\nof critical parameter with smaller system sizes by implementing averaging of observables\nover different graph dilutions. To date, this model has shown no improvement. Finally,\nI make suggestions for the choice of distributions of interactions that are robust to noise\nand present a method for using previously unaccessible continuous distributions. I begin\nwith showing the best-case performance of quantum annealing devices. I show results for\nthe resilience, the probability that the ground-state solution has changed due to inherent\nanalog noise in the device, and present strategies for developing robust instance classes.\nThe analog noise is also detrimental to interactions chosen from continuous distributions.\nUsing Gaussian quadratures, I present a method for discretizing continuous distributions\nto reduce noise effects. Simulations on the D-Wave show that the average residual of\nthe ground-state energy with the true ground-state energy is calculated and shown to be\nsmaller in the case of the discrete distribution.
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.
This thesis addresses the surprising features of zero-temperature statics and dynamics of several spin glass models, including correlations between soft spins that arise spontaneously during avalanches, and the discovery of localized states that involve the presence of two-level systems. It also presents the only detailed historiographical research on the spin glass theory. Despite the extreme simplicity of their definition, spin glasses display a wide variety of non-trivial behaviors that are not yet fully understood. In this thesis the author sheds light on some of these, focusing on both the search for phase transitions under perturbations of Hamiltonians and the zero-temperature properties and responses to external stimuli. After introducing spin glasses and useful concepts on phase transitions and numerics, the results of two massive Monte Carlo campaigns on three-dimensional systems are presented: The first of these examines the de Almeida Thouless transition, and proposes a new finite-size scaling ansatz, which accelerates the convergence to the thermodynamic limit. The second reconstructs the phase diagram of the Heisenberg spin glass with random exchange anisotropy
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
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.