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.
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.
The nature of the zero-temperature ordering transition in the three-dimensional Gaussian random-field Ising magnet is studied numerically, aided by scaling analyses. Various numerical calculations are used to consistently infer the location of the transition to a high precision. A variety of boundary conditions are imposed on large samples to study the order of the transition and the number of states in the large volume limit. In the ferromagnetic phase, where the domain walls have fractal dimension ds=2, the scaling of the roughness of the domain walls, $w\ensuremath{\sim}{L}^{\ensuremath{\zeta}},$ is consistent with the theoretical prediction $\ensuremath{\zeta}=2/3.$ As the randomness is increased through the transition, the probability distribution of the interfacial tension of domain walls scales in a manner that is clearly consistent with a single second-order transition. At the critical point, the fractal dimensions of domain walls and the fractal dimension of the outer surface of spin clusters are investigated: there are at least two distinct physically important fractal dimensions that describe domain walls. These dimensions are argued to be related by scaling to combinations of the energy scaling exponent $\ensuremath{\theta},$ which determines the violation of hyperscaling, the correlation length exponent $\ensuremath{\nu},$ and the magnetization exponent $\ensuremath{\beta}.$ The value $\ensuremath{\beta}=0.017\ifmmode\pm\else\textpm\fi{}0.005$ computed from finite-size scaling of the magnetization is very nearly zero: this estimate is supported by the study of the spin cluster size distribution at criticality. The variation of configurations in the interior of a sample with boundary conditions is consistent with the hypothesis that there is a single transition separating the disordered phase with one ground state from the ordered phase with two ground states. The array of results, including values for several exponents, are shown to be consistent with a scaling picture and a geometric description of the influence of boundary conditions on the spins. The details of the algorithm used and its implementation are also described.
In this thesis classical disordered spin systems, in particular, the random field Ising model (RFIM), are studied using numerical methods. The previous experimental and theoretical research on the RFIM is reviewed. Critical exponents of the RFIM are extracted at zero temperature. The heat capacity exponent α is found to be near zero. The ground states within a certain region with varying external field and disorder are portrayed, and it is speculated that if related quantities are scaled properly, ground state portraits at different system sizes are statistically similar. The performance of the Wang-Landau (WL) algorithm, which is used in our positive temperature study of the RFIM, is measured by the mean first-passage time. It is proved that the mean first, passage time of the mean field Ising model scales as N 2 log N, where N is the number of spins. The logarithmic correction term to the unbiased Markovian random walk is due to the boundaries. When applied to the Ising model with nearest neighbor interactions, the WL algorithm suffers from power law slowing down. Carefully designed cluster updating, however, can accelerate the WL algorithm and eliminate the slowing down. The WL algorithm is used in our finite temperature study of the RFIM. Physical quantities, such as the specific heat and the susceptibility, are obtained by the WL algorithm over a broad range of temperature. It is discovered that for some realizations with system size larger than 8 3, sharp peaks are present in these physical quantities. These sharp peaks result from flipping a large domain, and furthermore, the critical domains are strongly correlated to the domains found at the zero temperature transition. This observation suggests a strong version of the zero temperature fixed point picture. The MKRG approximation is employed to test the correlation between the critical states and the ground states in much larger systems. It is found that the fraction of correlated realizations drops as system size grows, while there are still significant number of correlated realizations even for systems as large as 10243. Whether substantial correlations will remain in the thermodynamic limit is unclear from our present data.
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 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.
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.
Clearly, in nature, but also in technological applications, complex systems built in an entirely ordered and regular fashion are the exception rather than the rule. In this thesis we explore how critical phenomena are influenced by quenched spatial randomness. Specifically, we consider physical systems undergoing a continuous phase transition in the presence of topological disorder, where the underlying structure, on which the system evolves, is given by a non-regular, discrete lattice. We therefore endeavour to achieve a thorough understanding of the interplay between collective dynamics and quenched randomness. According to the intriguing concept of universality, certain laws emerge from collectively behaving many-body systems at criticality, almost regardless of the precise microscopic realization of interactions in those systems. As a consequence, vastly different phenomena show striking similarities at their respective phase transitions. In this dissertation we pursue the question of whether the universal properties of critical phenomena are preserved when the system is subjected to topological perturbations. For this purpose, we perform numerical simulations of several prototypical systems of statistical physics which show a continuous phase transition. In particular, the equilibrium spin-1/2 Ising model and its generalizations represent -- among other applications -- fairly natural approaches to model magnetism in solids, whereas the non-equilibrium contact process serves as a toy model for percolation in porous media and epidemic spreading. Finally, the Manna sandpile model is strongly related to the concept of self-organized criticality, where a complex dynamic system reaches a critical state without fine-tuning of external variables. Our results reveal that the prevailing understanding of the influence of topological randomness on critical phenomena is insufficient. In particular, by considering very specific and newly developed lattice structures, we are able to show that -- contrary to the popular opinion -- spatial correlations in the number of interacting neighbours are not a key measure for predicting whether disorder ultimately alters the behaviour of a given critical system.