Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices

Abstract

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)] demonstrates an alternative that can bypass this issue for spin glasses with planar or quasi-planar 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)]. 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)] 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 at ~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.

13 pages, 12 figures

References in corpus (30)

• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Hyper-optimized tensor network contraction
• Tensor Network Algorithms: a Route Map
• Simple universal models capture all classical spin physics
• Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Annealing by simulating the coherent Ising machine
• Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Tropical Tensor Network for Ground States of Spin Glasses
• Strengths and Weaknesses of Parallel Tempering
• Hybrid quantum annealing for larger-than-QPU lattice-structured problems
• Scaling overhead of embedding optimization problems in quantum annealing
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• Efficient evaluation of partition functions of frustrated and inhomogeneous spin systems
• The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Computational hardness of spin-glass problems with tile-planted solutions
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Exploring Quantum Annealing Architectures: A Spin Glass Perspective
• Collective Monte Carlo updates through tensor network renormalization
• Tensor networks for $p$-spin models

Cited by in corpus (2)

• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
• Variational matrix product states for combinatorial optimization