Message Passing Variational Autoregressive Network for Solving Intractable Ising Models

Abstract

Many deep neural networks have been used to solve Ising models, including autoregressive neural networks, convolutional neural networks, recurrent neural networks, and graph neural networks. Learning a probability distribution of energy configuration or finding the ground states of a disordered, fully connected Ising model is essential for statistical mechanics and NP-hard problems. Despite tremendous efforts, a neural network architecture with the ability to high-accurately solve these fully connected and extremely intractable problems on larger systems is still lacking. Here we propose a variational autoregressive architecture with a message passing mechanism, which can effectively utilize the interactions between spin variables. The new network trained under an annealing framework outperforms existing methods in solving several prototypical Ising spin Hamiltonians, especially for larger spin systems at low temperatures. The advantages also come from the great mitigation of mode collapse during the training process of deep neural networks. Considering these extremely difficult problems to be solved, our method extends the current computational limits of unsupervised neural networks to solve combinatorial optimization problems.

18 pages, 14 figures

References in corpus (17)

• Machine learning and the physical sciences
• Parallel Tempering: Theory, Applications, and New Perspectives
• Solving Statistical Mechanics Using Variational Autoregressive Networks
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Annealing by simulating the coherent Ising machine
• Non-Reversible Parallel Tempering: a Scalable Highly Parallel MCMC Scheme
• Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
• Boosting Monte Carlo simulations of spin glasses using autoregressive neural networks
• The Sherrington-Kirkpatrick model: an overview
• On independent sets in random graphs
• Graph Coloring with Physics-Inspired Graph Neural Networks
• Emulating the coherent Ising machine with a mean-field algorithm
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning
• Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks

Cited by in corpus (4)

• Generalized Probabilistic Approximate Optimization Algorithm
• A method for quantifying the generalization capabilities of generative models for solving Ising models
• Dreaming up scale invariance via inverse renormalization group
• Large-scale portfolio optimization with variational neural annealing