We present a unified exact tensor network approach to compute the ground state energy, identify the optimal configuration, and count the number of solutions for spin glasses. The method is based on tensor networks with the tropical algebra defined on the semiring of (R∪{-∞},⊕,⊙). Contracting the tropical tensor network gives the ground state energy; differentiating through the tensor network contraction gives the ground state configuration; mixing the tropical algebra and the ordinary algebra counts the ground state degeneracy. The approach brings together the concepts from graphical models, tensor networks, differentiable programming, and quantum circuit simulation, and easily utilizes the computational power of graphical processing units (GPUs). For applications, we compute the exact ground state energy of Ising spin glasses on square lattice up to 1024 spins, on cubic lattice up to 216 spins, and on three regular random graphs up to 220 spins, on a single GPU; we obtain exact ground state energy of ±J Ising spin glass on the chimera graph of D-Wave quantum annealer of 512 qubits in less than 100 s and investigate the exact value of the residual entropy of ±J spin glasses on the chimera graph; finally, we investigate ground-state energy and entropy of three-state Potts glasses on square lattices up to size 18×18. Our approach provides baselines and benchmarks for exact algorithms for spin glasses and combinatorial optimization problems, and for evaluating heuristic algorithms and mean-field theories.
We present a unified exact tensor network approach to compute the ground state energy, identify the optimal configuration, and count the number of solutions for spin glasses. The method is based on tensor networks with the tropical algebra defined on the semiring of (R∪{-∞},⊕,⊙). Contracting the tropical tensor network gives the ground state energy; differentiating through the tensor network contraction gives the ground state configuration; mixing the tropical algebra and the ordinary algebra counts the ground state degeneracy. The approach brings together the concepts from graphical models, tensor networks, differentiable programming, and quantum circuit simulation, and easily utilizes the computational power of graphical processing units (GPUs). For applications, we compute the exact ground state energy of Ising spin glasses on square lattice up to 1024 spins, on cubic lattice up to 216 spins, and on three regular random graphs up to 220 spins, on a single GPU; we obtain exact ground state energy of ±J Ising spin glass on the chimera graph of D-Wave quantum annealer of 512 qubits in less than 100 s and investigate the exact value of the residual entropy of ±J spin glasses on the chimera graph; finally, we investigate ground-state energy and entropy of three-state Potts glasses on square lattices up to size 18×18. Our approach provides baselines and benchmarks for exact algorithms for spin glasses and combinatorial optimization problems, and for evaluating heuristic algorithms and mean-field theories.
Characterizing the ground-state properties of disordered systems, such as spin glasses and combinatorial optimization problems, is fundamental to science and engineering. However, computing exact ground states and counting their degeneracies are generally NP-hard and #P-hard problems, respectively, posing a formidable challenge for exact algorithms. Recently, Tensor Networks methods, which utilize high-dimensional linear algebra and achieve massive hardware parallelization, have emerged as a rapidly developing paradigm for efficiently solving these tasks. Despite their success, these methods are fundamentally constrained by the exponential growth of space complexity, which severely limits their scalability. To address this bottleneck, we introduce the Branch-and-Bound Tensor Network (BBTN) method, which seamlessly integrates the adaptive search framework of branch-and-bound with the efficient contraction of tropical tensor networks, significantly extending the reach of exact algorithms. We show that BBTN significantly surpasses existing state-of-the-art solvers, setting new benchmarks for exact computation. It pushes the boundaries of tractability to previously unreachable scales, enabling exact ground-state counting for ±J spin glasses up to 64×64 and solving Maximum Independent Set problems on King's subgraphs up to 100×100. For hard instances, BBTN dramatically reduces the computational cost of standard Tropical Tensor Networks, compressing years of runtime into minutes. Furthermore, it outperforms leading integer-programming solvers by over 30×, establishing a versatile and scalable framework for solving hard problems in statistical physics and combinatorial optimization.
We devise a deterministic algorithm to efficiently sample high-quality solutions of certain spin-glass systems that encode hard optimization problems. We employ tensor networks to represent the Gibbs distribution of all possible configurations. Using approximate tensor-network contractions, we are able to efficiently map the low-energy spectrum of some quasi-two-dimensional Hamiltonians. We exploit the local nature of the problems to compute spin-glass droplets geometries, which provides a new form of compression of the low-energy spectrum. It naturally extends to sampling, which otherwise, for exact contraction, is #P-complete. In particular, for one of the hardest known problem-classes devised on chimera graphs known as deceptive cluster loops and for up to 2048 spins, we find on the order of 10^{10} degenerate ground states in a single run of our algorithm, computing better solutions than have been reported on some hard instances. Our gradient-free approach could provide new insight into the structure of disordered spin-glass complexes, with ramifications both for machine learning and noisy intermediate-scale quantum devices.
We present a general method for approximately contracting tensor networks with an arbitrary connectivity. This enables us to release the computational power of tensor networks to wide use in inference and learning problems defined on general graphs. We show applications of our algorithm in graphical models, specifically on estimating free energy of spin glasses defined on various of graphs, where our method largely outperforms existing algorithms, including the mean-field methods and the recently proposed neural-network-based methods. We further apply our method to the simulation of random quantum circuits and demonstrate that, with a trade-off of negligible truncation errors, our method is able to simulate large quantum circuits that are out of reach of the state-of-the-art simulation methods.
In spin systems, geometrical frustration describes the impossibility of minimizing simultaneously all the interactions in a Hamiltonian, often giving rise to macroscopic ground-state degeneracies and emergent low-temperature physics. In this thesis, combining tensor network (TN) methods to Monte Carlo (MC) methods and ground-state energy lower bound approaches, we study two-dimensional frustrated classical Ising models. In particular, we focus on the determination of the residual entropy in the presence of farther-neighbor interactions in kagome lattice Ising antiferromagnets (KIAFM). In general, using MC to determine the residual entropy is a significant challenge requiring ad-hoc updates, a precise evaluation of the energy at all temperatures to allow for thermodynamic integration, and a good control of the finite-size scaling behavior. As an alternative, we turn to TNs; however, we argue that, in the presence of frustration and macroscopic ground-state degeneracy, standard algorithms fail to converge at low temperatures on the usual TN formulation of partition functions. Inspired by methods for constructing ground-state energy lower bounds, we propose a systematic way to find the ground-state local rule using linear programming. Characterizing the rules as tiles that can be tessellated to form ground states of the model gives rise to a natural contractible TN formulation of the partition function. This method provides a direct access to the ground-state properties of frustrated models and, in particular, allows an extremely precise determination of their residual entropy. We then study two models inspired by artificial spin systems on the kagome lattice with out-of-plane (OOP) anisotropy. The first model is motivated by experiments on an array of chirally coupled nanomagnets. We argue that the farther-neighbor to nearest-neighbor couplings ratios in this system are much smaller than in the dipolar case, J2/J1 being of the order of 2%. A comparison of the experimental correlations with the results of extensive TN and MC simulations shows that (1) the experimental second- and third-neighbor correlations are inverted as compared to those of a pure nearest-neighbor model at equilibrium (even with a magnetic field), and (2) second-neighbor couplings as small as 1% of the nearest-neighbor couplings will affect the spin-spin correlations even at fairly high temperatures. Motivated by dipolar coupled artificial spin systems, we turn to the progressive lifting of the ground-state degeneracy of the KIAFM. We provide a detailed study of the ground-state phases of this model with up to third neighbor interactions, for arbitrary J2, J3 such that J1 >> J2, J3, obtaining exact results for the ground-state energies. When all couplings are antiferromagnetic, we exhibit three macroscopically degenerate ground-state phases and establish their residual entropy using our TN approach. Furthermore, in the phase corresponding to the dipolar KIAFM truncated to third neighbors, we use the ground-state tiles to establish the existence of a mapping to the ground-state manifold of the triangular Ising antiferromagnet.
We present a general graph-based projected entangled-pair state (gPEPS) algorithm to approximate ground states of nearest-neighbor local Hamiltonians on any lattice or graph of infinite size. By introducing the structural matrix, which codifies the details of tensor networks on any graphs in any dimension d, we are able to produce a code that can be essentially launched to simulate any lattice. We further introduce an optimized algorithm to compute simple tensor updates as well as expectation values and correlators with a mean-field-like effective environments. Though not being variational, this strategy allows to cope with PEPS of very large bond dimension (e.g., D=100) and produces remarkably accurate results in the thermodynamic limit in many situations, and specially when the correlation length is small and the connectivity of the lattice is large. We prove the validity of our approach by benchmarking the algorithm against known results for several models, i.e., the antiferromagnetic Heisenberg model on a chain, star and cubic lattices, the hardcore Bose-Hubbard model on square lattice, the ferromagnetic Heisenberg model in a field on the pyrochlore lattice, as well as the three-state quantum Potts model in field on the kagome lattice and the spin-1 bilinear-biquadratic Heisenberg model on the triangular lattice. We further demonstrate the performance of gPEPS by studying the quantum phase transition of the 2d quantum Ising model in transverse magnetic field on the square lattice, and the phase diagram of the Kitaev-Heisenberg model on the hyperhoneycomb lattice. Our results are in excellent agreement with previous studies.
Obtaining the low-energy configurations of spin glasses that have rugged energy landscapes is of direct relevance to combinatorial optimization and fundamental science. Search-based heuristics have difficulty with this task due to the existence of many local minima that are far from optimal. The work of M. M. Rams et al. [Phys. Rev. E 104, 025308 (2021)2470-004510.1103/PhysRevE.104.025308] demonstrates an alternative that can bypass this issue for spin glasses with planar or quasiplanar geometry: sampling the Boltzmann distribution via approximate contractions of tensor networks. The computational complexity of this approach is due only to the complexity of contracting the network and is therefore independent of landscape ruggedness. Here we initiate an investigation of how to take this approach beyond (quasi-)planar geometry by utilizing hyperoptimized approximate contraction of tensor networks [J. Gray and G. K.-L. Chan, Phys. Rev. X 14, 011009 (2024)2160-330810.1103/PhysRevX.14.011009]. We perform tests on the periodic square- and cubic-lattice, planted-solution Ising spin glasses generated with tile planting [F. Hamze et al., Phys. Rev. E 97, 043303 (2018)2470-004510.1103/PhysRevE.97.043303] for up to 2304 (square lattice) and 216 (cubic lattice) spins. For a fixed bond dimension, the time complexity is quadratic. With a bond dimension of only four, over the tested system sizes, the average relative energy error in the most rugged instance class remains ∼1% (square lattice) or ∼10% (cubic lattice) of optimal. In less rugged instances the solution is always optimal for the square lattice and either optimal or within ∼1% for the cubic lattice. These results suggest that further development of optimization methods based on tensor-network representations of spin glass partition functions may be fruitful, especially given that such methods are not limited to the Ising (i.e., binary) or two-body (i.e., quadratic) settings.