Finding spin glass ground states through deep reinforcement learning

Abstract

Spin glasses are disordered magnets with random interactions that are, generally, in conflict with each other. Finding the ground states of spin glasses is not only essential for the understanding of the nature of disordered magnetic and other physical systems, but also useful to solve a broad array of hard combinatorial optimization problems across multiple disciplines. Despite decades-long efforts, an algorithm with both high accuracy and high efficiency is still lacking. Here we introduce DIRAC - a deep reinforcement learning framework, which can be trained purely on small-scale spin glass instances and then applied to arbitrarily large ones. DIRAC displays better scalability than other methods and can be leveraged to enhance any thermal annealing method. Extensive calculations on 2D, 3D and 4D Edwards-Anderson spin glass instances demonstrate the superior performance of DIRAC over existing methods. As many hard combinatorial optimization problems have Ising spin glass formulations, our results suggest a promising tool in solving these hard problems. Moreover, the presented algorithm will help us better understand the nature of the low-temperature spin-glass phase, which is a fundamental challenge in statistical physics.

arXiv comment35 pages, 6 figures

References in corpus (12)

• Community detection in graphs
• Neural Message Passing for Quantum Chemistry
• Ising formulations of many NP problems
• Statistical Mechanics of Community Detection
• Learning Combinatorial Optimization Algorithms over Graphs
• Solving Statistical Mechanics Using Variational Autoregressive Networks
• Weak-ergodicity breaking in mean-field spin-glass models
• Generalized Elitzur's Theorem and Dimensional Reduction
• Scaling of stiffness energy for 3d +/-J Ising spin glasses
• Aspect-Ratio Scaling and The Stiffness Exponent $\theta$ for Ising Spin Glasses
• Domain-wall excitations in the two-dimensional Ising spin glass
• Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning

Cited by in corpus (2)

• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set