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 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 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.
Disordered systems arise in many physical contexts. Not all matter is uni- form, and impurities or heterogeneities can be modeled by fixed random disor- der. Numerous complex networks also possess fixed disorder, leading to appli- cations in transportation systems [1], telecommunications [2], social networks [3, 4], and epidemic modeling [5], to name a few. Due to their random nature and power law critical behavior, disordered systems are difficult to study analytically. Numerical simulation can help overcome this hurdle by allowing for the rapid computation of system states. In order to get precise statistics and extrapolate to the thermodynamic limit, large systems must be studied over many realizations. Thus, innovative al- gorithm development is essential in order reduce memory or running time requirements of simulations. This thesis presents a review of disordered systems, as well as a thorough study of two particular systems through numerical simulation, algorithm de- velopment and optimization, and careful statistical analysis of scaling proper- ties. Chapter 1 provides a thorough overview of disordered systems, the his- tory of their study in the physics community, and the development of tech- niques used to study them. Topics of quenched disorder, phase transitions, the renormalization group, criticality, and scale invariance are discussed. Several prominent models of disordered systems are also explained. Lastly, analysis techniques used in studying disordered systems are covered. In Chapter 2, minimal spanning trees on critical percolation clusters are studied, motivated in part by an analytic perturbation expansion by Jackson and Read [6] that I check against numerical calculations. This system has a direct mapping to the ground state of the strongly disordered spin glass [7]. We compute the path length fractal dimension of these trees in dimensions d = {2, 3, 4, 5} and find our results to be compatible with the analytic results suggested by Jackson and Read. In Chapter 3, the random bond Ising ferromagnet is studied, which is es- pecially useful since it serves as a prototype for more complicated disordered systems such as the random field Ising model and spin glasses. We investigate the effect that changing boundary spins has on the locations of domain walls in the interior of the random ferromagnet system. We provide an analytic proof that ground state domain walls in the two dimensional system are de- composable, and we map these domain walls to a shortest paths problem. By implementing a multiple-source shortest paths algorithm developed by Philip Klein [8], we are able to efficiently probe domain wall locations for all possible configurations of boundary spins. We consider lattices with uncorrelated dis- order, as well as disorder that is spatially correlated according to a power law. We present numerical results for the scaling exponent governing the probabil- ity that a domain wall can be induced that passes through a particular location in the system’s interior, and we compare these results to previous results on the directed polymer problem.
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
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.
Magnetic frustrations are the fundamental cause of many interesting phenomena in materials that have been intensely studied since the middle of the 20th century. Magnetic systems with competing interactions, ranging from insulating antiferromagnets to arrays of superconducting qubits, exhibit nontrivial quantum e ects that arise from the need to satisfy a jagged free energy landscape. The search for and characterization of quantum spin liquids, nontrivial topological phases, and quantum phase transitions is conducted through investigations of such frustrated models. Within the large umbrella of frustrated magnetism I have studied some speci c models with the purpose of answering the following questions: (1) What are the interesting phases and less-interesting phases, and how do they fall in the phase diagram relative to one another? (2) What properties do the phases have, and how can we characterize what happens when one phase transitions to another? Armed with the answers to these questions, researchers can further explore these interesting phenomena and apply them towards new materials and devices. In this thesis, I rst develop a computational methodology for studying both classical and quantum spin models using various forms of Monte Carlo simulation. I use classical Monte Carlo to study highly-frustrated models of Ising spins both at nite temperatures and in the T = 0 limit, to map the phase diagram and determine the universality class of phase transitions. Using these methods, I show that in a dissipative chain of qubits, bath-induced qubit-qubit interactions lead to collective decoherence above a critical dissipation strength. This causes the qubits to lose all stored information and become fully correlated with one another, an e ect that one would need to mitigate in order to perform quantum computation. In another study, I show that in antiferromagnetic insulators with anisotropic interactions, frustration can cause an intermediate paramagnetic phase with oblong \droplets" of correlated spins. This phenomenon is quite general and the presence of these droplets can help explain experimental signatures that occur at unexpected temperatures in such materials. In addition to the classical simulations, I develop a variational Monte Carlo (VMC) technique to search for ground states in Heisenberg-type models, speci cally for spins S = 1. The case of S = 1 is more complicated than the case for S = 1=2 due to an additional local degree of freedom, which has interesting implications for the possible states that can be realized. Using semiclassical energy minimization as well as VMC, I show that spin S = 1 diamond-lattice antiferromagnets experience higher-order spinspin interactions that destroy previously theorized liquid-like spiral spin orderings. However, the presence of these higher-order interactions can also potentially allow other phases such as quantum spin liquids and topological paramagnets. Such results can provide an avenue for explaining anomalous phenomena like low-temperature paramagnetism in future experimental materials.
Spin glass behavior was first seen in metallic alloys with magnetic impurities dispersed randomly in the main non-magnetic component. Due to the simultaneous presence of quenched disorder and competing ferromagnetic and antiferromagnetic interactions, the nonequilibrium behaviors of spin glasses are intricate and difficult to understand. Experimental research on spin glass materials indicate extremely slow dynamics, suggesting that the direct numerical simulation using local spin flips will take impractical time scales to replicate the nonequilibrium behaviors. This thesis introduces efficient algorithms and heuristics for the numerical simulation of simple models for spin glasses and discusses significant simulation results. The results provide insights into understanding the nonequilibrium behaviors, especially aging and memory, through studying microscopic constituent configurations. The methodology and conclusion presented in this thesis can be potentially extended to address general questions about disordered materials at nonequilibrium. Chapter 1 provides a thorough overview of spin glasses. A detailed introduction on complex nonequilibrium behaviors, including slow dynamics and memory effects, seen in typical experiments of spin glass materials, is presented. A general discussion about the characterization and categorization of memory effects found in many out-of-equilibrium systems is highlighted. Two prevalent theoretical models on spin glasses, the droplet and replica symmetry breaking theory, are described. Lastly, algorithm development and simulation techniques used to study spin glasses are covered. In Chapter 2, a patchwork heuristic is applied to accelerate the relaxation of spin glass models in dimensions d=1 and d=2 with the goal of investigating the dynamics of loss and recovery of spin configurations. A well-designed simulation protocol, consists of a aging and recovery stage, is used to mimic the temperature cycling experiment, where the temperature variations are replaced by the variations of the spin coupling realization. Eventual recovery of memory upon coarsening is seen in two-dimensional Ising spin glasses and one-dimensional clock models, while one-dimensional Ising spin systems do not exhibit configuration memory. A central result is that the coarsening recovery length scale sc grows faster than the aging length scale ℓ as a power law relation sc∼ℓ2.58. In Chapter 3, the microscopic dependence of spin glass equilibration on sample history, i.e., the initial configuration and the specific noise history of stochastic dynamics, is examined. The patchwork dynamics is used to simulate the glassy dynamics over a wide range of length scales. The dependence of the nearest-neighbor spin correlations at long time on initial spin configurations and on noise histories are compared. Most of the local spin correlations are independent of the details of evolution, due to the formation of rigid domains. The correlations on a fractal set of domain walls are found to have distinct dependence on the noise history and the initial state. The initial ``nature'' of the state is retained in the domain walls under coarsening more than the ``nurture'' of the noise, while the location of the domain walls at each scale is determined by the frozen disorder (``environment''). We also provide evidence that coarsening with local dynamics at finite temperature gives persistence of overlaps roughly consistent with coarsening at zero temperature, at least over short distances, supporting the use of zero-temperature heuristics to address finite-temperature dynamics and memory.