Variational Neural Annealing

Abstract

Many important challenges in science and technology can be cast as optimization problems. When viewed in a statistical physics framework, these can be tackled by simulated annealing, where a gradual cooling procedure helps search for groundstate solutions of a target Hamiltonian. While powerful, simulated annealing is known to have prohibitively slow sampling dynamics when the optimization landscape is rough or glassy. Here we show that by generalizing the target distribution with a parameterized model, an analogous annealing framework based on the variational principle can be used to search for groundstate solutions. Modern autoregressive models such as recurrent neural networks provide ideal parameterizations since they can be exactly sampled without slow dynamics even when the model encodes a rough landscape. We implement this procedure in the classical and quantum settings on several prototypical spin glass Hamiltonians, and find that it significantly outperforms traditional simulated annealing in the asymptotic limit, illustrating the potential power of this yet unexplored route to optimization.

19 pages, 9 figures, 1 table

References in corpus (22)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A class of quantum many-body states that can be efficiently simulated
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Recurrent Neural Network Wave Functions
• Deep autoregressive models for the efficient variational simulation of many-body quantum systems
• Solving Statistical Mechanics Using Variational Autoregressive Networks
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Zero-Variance Zero-Bias Principle for Observables in quantum Monte Carlo: Application to Forces
• Dilated Recurrent Neural Networks
• Dynamics of a quantum phase transition in the random Ising model
• Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
• Optimal Control of Majorana Zero Modes
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Cooling dynamics of pure and random Ising chains
• Quantum annealing speedup over simulated annealing on random Ising chains
• Automatic Differentiable Monte Carlo: Theory and Application
• Iterative Retraining of Quantum Spin Models Using Recurrent Neural Networks
• On the dynamics of Simulated Quantum Annealing in random Ising chains
• Classical Quantum Optimization with Neural Network Quantum States
• The deep learning and statistical physics applications to the problems of combinatorial optimization

Cited by in corpus (11)

• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• From Tensor Network Quantum States to Tensorial Recurrent Neural Networks
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• A Bayesian generative neural network framework for epidemic inference problems
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems
• Estimating the Euclidean quantum propagator with deep generative modeling of Feynman paths
• Accelerating equilibrium spin-glass simulations using quantum annealers via generative deep learning
• Exploring explicit coarse-grained structure in artificial neural networks
• Adiabatic quantum computing with parameterized quantum circuits