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 the ferromagnetic Ising model and in the case the three dimensional spin-glass model. I show in both the ferromagnetic Ising and the spin-glass model that the phases of the soft problem have the same properties with 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 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.
We investigate the temperature-disorder (
T-$\ensuremath{\sigma}$) phase diagram of a three-dimensional gauge glass model, which is a cubic-lattice nearest-neighbor
XY model with quenched random phase shifts
Axy at the bonds. We consider the uncorrelated phase-shift distribution $P({A}_{\mathit{xy}})~\mathrm{exp}[(\mathrm{cos}{A}_{\mathit{xy}})/\ensuremath{\sigma}]$, which has the pure
XY model, and the uniform distribution of random phase shifts as extreme cases at $\ensuremath{\sigma}=0$ and $\ensuremath{\sigma}\ensuremath{\rightarrow}\ensuremath{\infty}$, respectively, and which gives rise to equal magnetic and overlap correlation functions when $T=\ensuremath{\sigma}$. Our study is mostly based on numerical Monte Carlo simulations. While the high-temperature phase is always paramagnetic, at low temperatures there is a ferromagnetic phase for weak disorder (small $\ensuremath{\sigma}$) and a glassy phase at large disorder (large $\ensuremath{\sigma}$). These three phases are separated by transition lines with different magnetic and glassy critical behaviors. The disorder induced by the random phase shifts turns out to be irrelevant at the paramagnetic-ferromagnetic transition line, where the critical behavior belongs to the 3D
XY universality class of pure systems; disorder gives rise only to very slowly decaying scaling corrections. The glassy critical behavior along the paramagnetic-glassy transition line belongs to the gauge-glass universality class, with a quite large exponent $\ensuremath{\nu}=3.2(4)$. These transition lines meet at a multicritical point M, located at ${T}_{M}={\ensuremath{\sigma}}_{M}=0.7840(2)$. The low-temperature ferromagnetic and glassy phases are separated by a third transition line, from M down to the
T=0 axis, which is slightly reentrant.