I propose a new method to study computationally difficult problems. I consider a new system, larger than the one I want to simulate. The original system is recovered by imposing constraints on the large system. I simulate the large system with the hard constraints replaced by soft constraints. I illustrate the method in the case of a ferromagnetic Ising model and in the case of a three-dimensional spin-glass model. I show that in both models the phases of the soft problem have the same properties as the phases of the original model and that the softened model belongs to the same universality class as the original one. I show that correlation times are much shorter in the larger soft constrained system and that it is computationally advantageous to study it instead of the original system. This method is quite general and can be applied to many other 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.
Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.
As an analysis of equilibrium phase transitions, the nonequilibrium relaxation method is extended to the spin glass (SG) transition. The $\ifmmode\pm\else\textpm\fi{}J$ Ising SG model is analyzed for three-dimensional (cubic) lattices up to the linear size of
L=127 and for four-dimensional (hypercubic) lattice up to
L=41. These sizes of systems are quite large as compared with those calculated, so far, by equilibrium simulations. As a dynamical order parameter, we calculate the clone correlation function (CCF) ${Q(t,t}_{\mathrm{w}})\ensuremath{\equiv}[〈{S}_{i}^{(1)}{(t+t}_{\mathrm{w}}){S}_{i}^{(2)}{(t+t}_{\mathrm{w}}){〉}^{\mathrm{F}}],$ which is a spin correlation of two replicas produced after the waiting time
tw from a simple starting state. It is found that the CCF shows an exponential decay in the paramagnetic phase, and a power-law decay after aginglike development $(t\ensuremath{\gg}{t}_{\mathrm{w}})$ in the SG phase. This provides a reliable upper bound of the transition temperature
Tg. It is also found that a scaling relation, ${Q(t,t}_{\mathrm{w}}{)=t}_{\mathrm{w}}^{\ensuremath{-}{\ensuremath{\lambda}}_{q}}\overline{q}{(t/t}_{\mathrm{w}}),$ holds just around the transition point providing the lower bound of
Tg. Together with these two bounds, we propose a new dynamical way for the estimation of
Tg from much larger systems. In the SG phase, the power-law behavior of the CCF for $t\ensuremath{\gg}{t}_{\mathrm{w}}$ suggests that the SG phase in short-range Ising models has a rugged phase space.