The common feature for a nontrivial hard problem is the existence of nontrivial topological structures, non-planarity graphs, nonlocalities, or long-range spin entanglements in a model system with randomness. For instance, the Boolean satisfiability (K-SAT) problems for K ≥ 3 MSATK≥3 are nontrivial, due to the existence of non-planarity graphs, nonlocalities, and the randomness. In this work, the relation between a spin-glass three-dimensional (3D) Ising model MSGI3D with the lattice size N = mnl and the K-SAT problems is investigated in detail. With the Clifford algebra representation, it is easy to reveal the existence of the long-range entanglements between Ising spins in the spin-glass 3D Ising lattice. The internal factors in the transfer matrices of the spin-glass 3D Ising model lead to the nontrivial topological structures and the nonlocalities. At first, we prove that the absolute minimum core (AMC) model MAMC3D exists in the spin-glass 3D Ising model, which is defined as a spin-glass 2D Ising model interacting with its nearest neighboring plane. Any algorithms, which use any approximations and/or break the long-range spin entanglements of the AMC model, cannot result in the exact solution of the spin-glass 3D Ising model. Second, we prove that the dual transformation between the spin-glass 3D Ising model and the spin-glass 3D Z2 lattice gauge model shows that it can be mapped to a K-SAT problem for K ≥ 4 also in the consideration of random interactions and frustrations. Third, we prove that the AMC model is equivalent to the K-SAT problem for K = 3. Because the lower bound of the computational complexity of the spin-glass 3D Ising model CLMSGI3D is the computational complexity by brute force search of the AMC model CUMAMC3D, the lower bound of the computational complexity of the K-SAT problem for K ≥ 4 CLMSATK≥4 is the computational complexity by brute force search of the K-SAT problem for K = 3 CUMSATK=3. Namely, CLMSATK≥4=CLMSGI3D≥CUMAMC3D=CUMSATK=3. All of them are in subexponential and superpolynomial. Therefore, the computational complexity of the K-SAT problem for K ≥ 4 cannot be reduced to that of the K-SAT problem for K < 3.
The common feature for a nontrivial hard problem is the existence of nontrivial topological structures, non-planarity graphs, nonlocalities, or long-range spin entanglements in a model system with randomness. For instance, the Boolean satisfiability (K-SAT) problems for K ≥ 3 MSATK≥3 are nontrivial, due to the existence of non-planarity graphs, nonlocalities, and the randomness. In this work, the relation between a spin-glass three-dimensional (3D) Ising model MSGI3D with the lattice size N = mnl and the K-SAT problems is investigated in detail. With the Clifford algebra representation, it is easy to reveal the existence of the long-range entanglements between Ising spins in the spin-glass 3D Ising lattice. The internal factors in the transfer matrices of the spin-glass 3D Ising model lead to the nontrivial topological structures and the nonlocalities. At first, we prove that the absolute minimum core (AMC) model MAMC3D exists in the spin-glass 3D Ising model, which is defined as a spin-glass 2D Ising model interacting with its nearest neighboring plane. Any algorithms, which use any approximations and/or break the long-range spin entanglements of the AMC model, cannot result in the exact solution of the spin-glass 3D Ising model. Second, we prove that the dual transformation between the spin-glass 3D Ising model and the spin-glass 3D Z2 lattice gauge model shows that it can be mapped to a K-SAT problem for K ≥ 4 also in the consideration of random interactions and frustrations. Third, we prove that the AMC model is equivalent to the K-SAT problem for K = 3. Because the lower bound of the computational complexity of the spin-glass 3D Ising model CLMSGI3D is the computational complexity by brute force search of the AMC model CUMAMC3D, the lower bound of the computational complexity of the K-SAT problem for K ≥ 4 CLMSATK≥4 is the computational complexity by brute force search of the K-SAT problem for K = 3 CUMSATK=3. Namely, CLMSATK≥4=CLMSGI3D≥CUMAMC3D=CUMSATK=3. All of them are in subexponential and superpolynomial. Therefore, the computational complexity of the K-SAT problem for K ≥ 4 cannot be reduced to that of the K-SAT problem for K < 3.
An overview of the mathematical structure of the three-dimensional (3D) Ising model is given, from the viewpoints of topologic, algebraic and geometric aspects. By analyzing the relations among transfer matrices of the 3D Ising model, Reidemeister moves in the knot theory, Yang-Baxter and tetrahedron equations, the following facts are illustrated for the 3D Ising model: 1) The complexified quaternion basis constructed for the 3D Ising model represents naturally the rotation in a (3 + 1) - dimensional space-time, as a relativistic quantum statistical mechanics model, which is consistent with the 4-fold integrand of the partition function by taking the time average. 2) A unitary transformation with a matrix being a spin representation in 2^(nlo)-space corresponds to a rotation in 2nlo-space, which serves to smooth all the crossings in the transfer matrices and contributes as the non-trivial topologic part of the partition function of the 3D Ising model. 3) A tetrahedron relation would ensure the commutativity of the transfer matrices and the integrability of the 3D Ising model, and its existence is guaranteed also by the Jordan algebra and the Jordan-von Neumann-Wigner procedures. 4) The unitary transformation for smoothing the crossings in the transfer matrices changes the wave functions by complex phases Φx, Φy, and Φz. The relation with quantum field and gauge theories, physical significance of weight factors are discussed in details. The conjectured exact solution is compared with numerical results, and singularities at/near infinite temperature are inspected. The analyticity in β = 1/(kB T) of both the hard-core and Ising models has been proved for β > 0, not for β = 0. Thus the high-temperature series cannot serve as a standard for judging a putative exact solution of the 3D Ising model.
An overview of the mathematical structure of the three-dimensional(3D) Ising model is given from the points of view of topology,algebra,and geometry.By analyzing the relationships among transfer matrices of the 3D Ising model,Reidemeister moves in the knot theory,Yang-Baxter and tetrahedron equations,the following facts are illustrated for the 3D Ising model.1) The complex quaternion basis constructed for the 3D Ising model naturally represents the rotation in a(3+1)-dimensional space-time as a relativistic quantum statistical mechanics model,which is consistent with the 4-fold integrand of the partition function obtained by taking the time average.2) A unitary transformation with a matrix that is a spin representation in 2 n·l·o-space corresponds to a rotation in 2n·l·o-space,which serves to smooth all the crossings in the transfer matrices and contributes the non-trivial topological part of the partition function of the 3D Ising model.3) A tetrahedron relationship would ensure the commutativity of the transfer matrices and the integrability of the 3D Ising model,and its existence is guaranteed by the Jordan algebra and the Jordan-von Neumann-Wigner procedures.4) The unitary transformation for smoothing the crossings in the transfer matrices changes the wave functions by complex phases φx,φy,and φz.The relationship with quantum field and gauge theories and the physical significance of the weight factors are discussed in detail.The conjectured exact solution is compared with numerical results,and the singularities at/near infinite temperature are inspected.The analyticity in β=1/(kBT) of both the hard-core and the Ising models has been proved only for β>0,not for β=0.Thus the high-temperature series cannot serve as a standard for judging a putative exact solution of the 3D Ising model.
Finding an exact ground state of a three-dimensional (3D) Ising spin glass is proven to be an NP-hard problem (i.e., at least as hard as any problem in the nondeterministic polynomial-time (NP) class). Given validity of the exponential time hypothesis, its computational complexity was proven to be no less than 2 N 2 / 3 , where N is the total number of spins. Here, we report results of extensive experimentation with D-Wave 3D annealer with N ≤ 5627 . We found exact ground states (in a probabilistic sense) for typical realizations of 3D spin glasses with the efficiency, which scales as 2 N / β with β ≈ 10 3 . Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, β can be increased even further. This suggests that, for N < β 3 , annealing devices provide most efficient way to find an exact ground state.
In this work, we first reveal the nature of three dimensions: the existence of non-local behavior. Taking the three-dimensional (3D) Ising model as an example, we analyze the transfer matrices as well as the partition function to discuss in details the origin of non-local behavior in three dimensions. We then point out that fail to deal with non-local behavior is one of the main disadvantages of several theoretical approaches (such as conventional low-temperature expansions, conventional high-temperature expansions, perturbative renormalization group and Monte Carlo methods, etc), all of which take local environments into account only. This work provides a deep understanding on the natural difference between 3D bulk materials and 2D materials, and shows that how to treat the non-local behavior and the interaction between spins along the third dimension is a key point for solving exactly the problems of the 3D systems with the nearest neighboring interactions. Finally, we will briefly review recent advance in the 3D Ising model and related topics.
Abstract The gauge invariance is an important phenomenon widely occurring in various matters with many-body interactions. The gauge theories are very important for understanding the evolution of fundamental physical processes in particle physics, high-energy physics, and condensed matter physics. In this work, the origin of nonlocal effects is inspected, and the contributions of nontrivial topological structures to physical properties are investigated in detail for both the three-dimensional (3D) Ising model and the 3D Z 2 lattice gauge model. Then, the exact solution for the 3D Z 2 lattice gauge theory is derived by the duality between the two models. The partition function, the spontaneous magnetization, the true range of correlation, and the critical point are rigorously derived for the 3D Z 2 lattice gauge theory. The critical exponents of the 3D Z 2 lattice gauge theory are in the same universality class as the 3D Ising model, which are α = 0, β = 3/8, γ = 5/4, δ = 13/3, η = 1/8, and ν = 2/3. Several fundamental issues, such as dimensionality, duality, symmetry, manifold and degenerate states, are investigated for these many-body interacting spin systems. The connections with superfluid, superconductors, particle physics, etc. are evaluated. Furthermore, physical significances and mathematical aspects of the 3D Z 2 lattice gauge theory are discussed with respect to topology, geometry, and algebra. The present results for the 3D Z 2 lattice gauge theory are helpful for figuring out the basic features of 3D lattice gauge theories with other symmetries, such as U(1), SU(2), and SU(3). This work shines a light on the interdisciplinarity between many-body interacting systems, algebra, topology, and geometry.
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.