Tropical Tensor Network for Ground States of Spin Glasses

Abstract

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. 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 3 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 seconds 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 3-state Potts glasses on square lattices up to size 18 x 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.

arXiv commentcode: https://github.com/TensorBFS/TropicalTensors.jl

References in corpus (30)

• Ising formulations of many NP problems
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum annealing with more than one hundred qubits
• The Bethe lattice spin glass revisited
• Simulating quantum computation by contracting tensor networks
• A New Approach to Spin Glass Simulations
• The computational complexity of PEPS
• Unsupervised Generative Modeling Using Matrix Product States
• Equivalence of restricted Boltzmann machines and tensor network states
• Differentiable Programming Tensor Networks
• Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design
• Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
• Forward-Mode Automatic Differentiation in Julia
• Classical Simulation of Quantum Supremacy Circuits
• Simulation of low-depth quantum circuits as complex undirected graphical models
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Residual entropies for three-dimensional frustrated spin systems with tensor networks
• qTorch: The Quantum Tensor Contraction Handler
• Tensor Network Contractions for #SAT
• Fast counting with tensor networks
• Solving frustrated Ising models using tensor networks
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Efficient subgraph-based sampling of Ising-type models with frustration
• Algebraic Geometry of Matrix Product States
• Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation
• Tensor Network Rewriting Strategies for Satisfiability and Counting
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
• Functional Tensors for Probabilistic Programming
• Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
• Do tensor renormalization group methods work for frustrated spin systems?

Cited by in corpus (27)

• The ITensor Software Library for Tensor Network Calculations
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum-Informed Recursive Optimization Algorithms
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Partial lifting of degeneracy in the $J_1-J_2-J_3$ Ising antiferromagnet on the kagome lattice
• Artificial out-of-plane Ising antiferromagnet on the kagome lattice with very small further neighbour couplings
• Mitigating the fermion sign problem by automatic differentiation
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Critical line of the triangular Ising antiferromagnet in a field from a $C_3$-symmetric corner transfer matrix algorithm
• Tensor network Monte Carlo simulations for the two-dimensional random-bond Ising model
• Efficient calculation of three-dimensional tensor networks
• Sampling diverse near-optimal solutions via algorithmic quantum annealing
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
• Probabilistic Inference in the Era of Tensor Networks and Differential Programming
• Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints
• Long-range spin-orbital order in the spin-orbital SU(2)$\times$SU(2)$\times$U(1) model
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Efficient Optimization of Variational Autoregressive Networks with Natural Gradient
• Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
• Differentiate Everything with a Reversible Embeded Domain-Specific Language
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Effects of Topological Boundary Conditions on Bell Nonlocality
• Solving Sharp Bounded-error Quantum Polynomial Time Problem by Evolution methods
• Variational matrix product states for combinatorial optimization