PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational Neural Annealing

Mohamed Hibat-Allah, Estelle M. Inack, Roeland Wiersema, Roger G. Melko, Juan Carrasquilla

arXiv:2101.10154v1cond-mat.dis-nncond-mat.stat-mechcs.LGquant-ph

TL;DR

Finite-time simulated annealing can miss exact Boltzmann distributions on complex landscapes. This paper anneals parameterized autoregressive models variationally and reports lower residual energies than conventional annealing methods at long run times.

  • Problem

    Finite-time simulated annealing samples approximate rather than exact Boltzmann distributions, so solution quality depends on problem complexity and cooling rate.

    Source: §I · p. 2

  • Method

    Variational neural annealing cools parameterized distributions or wavefunctions, using autoregressive recurrent neural networks and variational objectives.

    Source: §I · p. 2, §II · pp. 2–3

  • Results

    At large annealing counts, VCA beats SA and SQA in the Edwards–Anderson and fully connected cases; in Edwards–Anderson, residual energies are about three orders of magnitude smaller.

    Source: B. Edwards-Anderson model · p. 6, C. Fully-connected spin glasses · p. 6

  • Takeaways & Limitations

    Autoregressive variational annealing offers a route to accurate optimization that avoids slow sampling dynamics on rough landscapes, as demonstrated on prototypical spin-glass Hamiltonians.

    Source: §IV · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

Finite-time simulated annealing follows approximate rather than exact Boltzmann distributions, so solution quality depends on problem complexity and cooling rate. Variational neural annealing instead cools a parameterized model, using autoregressive neural networks to approximate the ideal trajectory.

I. INTRODUCTION

  • Many optimization problems map to minimizing an Ising Hamiltonian, but most such problems are NP-hard.The graph topology, couplings, and fields encode the problem.Source: §I · p. 1
  • Finite-time simulated annealing samples quasi-equilibrium distributions that only approximate the targeted Boltzmann distributions, yielding solutions whose quality depends on problem complexity and cooling rate.The paper frames this as a limitation of practical finite-time runs, in contrast to arbitrarily slow cooling.Source: §I · p. 2
  • Variational neural annealing replaces annealing the exact Boltzmann distribution with annealing a parameterized, sufficiently expressive and tractably sampled model.The paper implements this approach with autoregressive recurrent neural networks and presents it as an alternative to SA and SQA.Source: §I · p. 2

II. VARIATIONAL CLASSICAL AND QUANTUM ANNEALING

The paper develops classical and quantum annealing protocols that optimize parameterized distributions or wavefunctions as the target changes. Autoregressive recurrent neural networks provide exact samples, while a variational adiabatic theorem bounds the training steps under stated assumptions.

II. VARIATIONAL CLASSICAL AND QUANTUM ANNEALING

  • Both protocols use autoregressive recurrent neural networks to support exact sampling, avoiding Markov-chain sampling for VCA and providing exact Monte Carlo samples for VQA.VCA also uses those samples to estimate entropy without calculating the partition function.Source: §II · pp. 2–3
  • VCA warms up a parameterized distribution, then alternates cooling and training while reusing optimized parameters until T(1) = 0.The variational free energy upper-bounds the true instantaneous free energy and is updated by gradient descent; autoregressive RNNs enable exact samples and entropy estimation.Source: §II · p. 2
  • VQA optimizes a parameterized wavefunction against a time-dependent Hamiltonian energy, whose variational estimate upper-bounds the ground-state energy.The protocol warms up, then alternates annealing and training, reusing parameters across time steps; normalized RNN wavefunctions allow exact Monte Carlo samples.Source: §II · p. 3
  • The variational adiabatic theorem bounds the gradient-descent steps needed for adiabaticity and Psuccess > 1−ϵ, assuming a convex warm-up landscape, near-convergence during annealing, and noiseless energy gradients.The bound depends on the instantaneous energy gap; typical hard problems have exponentially shrinking minimum gaps, whereas polynomially shrinking gaps yield polynomially many steps.Source: §II · pp. 3–4

A. Annealing on random Ising chains

On random positive-coupling Ising chains, VCA and VQA residual energies decrease with annealing steps, with power-law decay at large step counts. Their fitted exponents suggest asymptotic speed-up over SA and coherent quantum annealing, although the exponents are hyperparameter-sensitive.

A. Annealing on random Ising chains

  • VCA’s residual-energy decay exponent is 1.5–1.9, while VQA’s is about 0.9–1.1; both follow power-law decay at large annealing-step counts.These exponents suggest asymptotic speed-up over SA and coherent quantum annealing, whose residual energies follow a logarithmic law.Source: A. Annealing on random Ising chains · p. 4, Figure 3 · p. 4
  • VCA’s average residual energy is an order of magnitude more accurate than VQA’s for a large number of annealing steps.The benchmark uses random positive couplings and system sizes N = 32, 64, 128.Source: A. Annealing on random Ising chains · p. 4, Figure 3 · p. 4
  • The reported decay exponents are not universal and may depend on learning rate, model choice, training steps, and optimizer.The authors describe them as a priori sensitive to algorithm hyperparameters.Source: A. Annealing on random Ising chains · p. 4

B. Edwards-Anderson model

On the two-dimensional Edwards–Anderson spin glass, VCA improves on quantum and classical annealing in the long-time regime, though SA and SQA can be better at short annealing times. The section also compares VCA with a zero-temperature variant and evaluates it on a larger lattice.

B. Edwards-Anderson model

  • The benchmark uses the square-lattice Edwards–Anderson spin glass with random nearest-neighbor couplings, and the variational protocols use a 2D tensorized RNN ansatz without weight sharing.The EA setup includes open boundary conditions; exact ground states are obtained using the spin-glass server.Source: B. Edwards-Anderson model · p. 5
  • In the 10 × 10 comparison, VCA solutions are three orders of magnitude more accurate on average than VQA in the adiabatic, long-time regime.Adding a fictitious Shannon entropy term improves VQA, but its scaling remains behind VCA; the figure also includes CQO.Source: B. Edwards-Anderson model · p. 5, Figure 4 · p. 5
  • With zero thermal fluctuations, CQO nears 1% accuracy after about 10^3 training steps and does not improve through 10^5 gradient steps.The authors interpret the plateau as evidence that CQO can get stuck in local minima.Source: B. Edwards-Anderson model · p. 5
  • At large Nannealing, VCA reaches residual energies about three orders of magnitude below SA and SQA on the 40 × 40 lattice.The methods use the same annealing speed; VCA's residual energy also improves faster, even at relatively small Nannealing.Source: Figure 4 · p. 5, B. Edwards-Anderson model · p. 6

C. Fully-connected spin glasses

For fully connected spin glasses, VCA improves on SA and SQA at longer annealing times for the SK model and the WPE at α = 0.5, while results at α = 0.25 are more competitive. WPE provides a benchmark with a known ground state and tunable hardness.

C. Fully-connected spin glasses

  • For SK with N = 100, VCA overtakes SA and SQA after Nannealing ∼10^3 and improves residual energy faster as annealing continues.At small Nannealing, SA and SQA produce lower residual energies; VCA's large-annealing advantage is also reflected in its higher density of low-energy configurations.Source: C. Fully-connected spin glasses · p. 6, Figure 5 · p. 7
  • For SK, VCA produces a higher density of low-energy configurations than SA and SQA in the large-annealing residual-energy histograms.The SK histograms use 1,000 residual energies for each of 25 disorder realizations; the figure also presents WPE residual-energy histograms.Source: C. Fully-connected spin glasses · p. 6, Figure 5 · p. 7
  • The WPE has a known planted ground state and tunable hardness; for α < 1, numerous near-zero-temperature paramagnetic metastable states can trap annealing methods.The benchmarks use N = 32 and α ∈ {0.25, 0.5}.Source: C. Fully-connected spin glasses · p. 6
  • At α = 0.5, VCA is about three orders of magnitude more accurate than SA and SQA at large Nannealing; at α = 0.25, its average performance is similar to theirs.For α = 0.25, VCA has a non-negligible density at very low residual energies while SA and SQA remain orders of magnitude higher.Source: C. Fully-connected spin glasses · p. 7, Figure 5 · p. 7

IV. CONCLUSIONS AND OUTLOOK

Variational neural annealing uses parameterized autoregressive models to search for ground states, and typically achieves solutions orders of magnitude more accurate than simulated annealing on spin glasses at large annealing-step counts. The authors identify model and protocol choices, including architecture–Hamiltonian fit, as directions for improvement.

IV. CONCLUSIONS AND OUTLOOK

  • On the considered spin-glass problems, variational neural annealing typically reaches solutions orders of magnitude more accurate on average than simulated annealing at large annealing-step counts.The paper reports accurate solutions for all optimization problems considered.Source: §IV · p. 7
  • The authors present variational neural annealing as a strategy to address simulated annealing’s slow sampling dynamics on rough or glassy landscapes.It anneals variational parameters of an autoregressive model that can be exactly sampled without slow dynamics, even on rough landscapes.Source: §IV · p. 7
  • Hyperparameters, model, hardware, and variational-objective choices remain open avenues that may improve the methods.The protocols use a simple annealing schedule, which the authors say reinforcement learning could improve [39].Source: §IV · p. 7
  • The authors report that different neural-network architectures were more efficient on particular Hamiltonians, motivating study of architecture–problem relationships and domain-informed designs.They envision using symmetries and domain knowledge to guide model and algorithm design.Source: §IV · p. 8
  • The authors anticipate machine-learning optimization methods may be adopted in diverse scientific and technological areas, including physics, biology, health care, and manufacturing.Source: §IV · p. 8

A. Recurrent Neural Network Ans¨atze

The RNN ansätze represent joint spin distributions through autoregressive conditional probabilities, with hidden states carrying information from earlier spins. The paper extends this construction with tensorized, two-dimensional, and dilated architectures for different settings.

A. Recurrent Neural Network Ans¨atze

  • RNNs factorize the joint spin distribution into conditional probabilities, each parameterized by an RNN cell that uses information encoded in its hidden state.The hidden state summarizes previous spins and is used to model the next-spin conditional probability.Source: A. Recurrent Neural Network Ans¨atze · p. 8
  • Softmax-normalized conditional probabilities make the resulting autoregressive joint distribution normalized.Source: A. Recurrent Neural Network Ans¨atze · p. 8
  • For disordered systems, the authors use site-dependent parameters instead of the usual weight sharing.They note that the benefit of this choice is demonstrated in Appendix D.Source: A. Recurrent Neural Network Ans¨atze · p. 8
  • The tensorized vanilla RNN replaces concatenation with a tensor operation to increase ansatz expressiveness.The paper also considers a tensorized recursion for two-dimensional systems.Source: A. Recurrent Neural Network Ans¨atze · p. 8
  • In the 2D tensorized RNN, each cell combines inputs and hidden states from two neighboring coordinates, with the coordinates determined by a zigzag path.The same zigzag path is used for autoregressive sampling.Source: A. Recurrent Neural Network Ans¨atze · p. 8, Figure 6 · p. 9
  • For fully connected models such as Sherrington–Kirkpatrick and Wishart planted systems, dilated RNNs model long-range correlations using connections that span increasing distances across layers.The authors use depth L = ⌈log2(N)⌉, bounding the path between two spins by O(log2(N)).Source: A. Recurrent Neural Network Ans¨atze · pp. 8–9
  • Figure 6 illustrates 1D cells updating hidden states from the preceding spin and state, and 2D cells receiving two states and inputs along the zigzag path.Source: Figure 6 · p. 9
  • The authors report accurate results across their RNN architectures using the exponential linear unit activation function.Source: A. Recurrent Neural Network Ans¨atze · p. 9

B. Minimizing the variational free energy

Variational classical annealing optimizes a model’s variational free energy using exact samples from an RNN. Its gradient estimator uses a baseline to reduce noise, and the method has a zero-variance property when the model matches the Boltzmann distribution, provided mode collapse is avoided.

B. Minimizing the variational free energy

C. Variational Monte Carlo

The variational Monte Carlo ansatz represents positive ground-state amplitudes of stoquastic Hamiltonians through a probability distribution and estimates energy from exact RNN samples. Its gradient estimator reduces noise, with variance approaching zero near an eigenstate.

C. Variational Monte Carlo

  • For stoquastic Hamiltonians with strictly real, positive ground-state amplitudes in the product spin basis, the wave function can be represented using a probability distribution.Source: C. Variational Monte Carlo · p. 10
  • The RNN wave function is normalized by construction, and exact samples from its probability distribution support estimates of the energy expectation value.Source: C. Variational Monte Carlo · p. 10
  • Subtracting the estimated energy from the gradient estimator reduces noise without introducing bias.When the ansatz is close to an eigenstate, local energies approach the energy expectation and gradient variance approaches zero.Source: C. Variational Monte Carlo · p. 10
  • The energy variance per spin becomes zero when the wave function matches an eigenstate, which is likely to be the ground state under variational-energy minimization.Source: C. Variational Monte Carlo · p. 10
  • For Hamiltonians with O(N) non-diagonal elements, one gradient step costs O(Ns×N^2×d_h^2) for the listed 1D and 2D RNNs.Source: C. Variational Monte Carlo · p. 10

D. Simulated Quantum Annealing and Simulated Annealing

This section describes the simulated quantum annealing and simulated annealing baselines used for comparison. SQA maps a quantum system to coupled classical replicas and samples them with Monte Carlo moves, while SA cools the classical system.

Simulated Quantum Annealing

  • SQA uses the Suzuki-Trotter mapping to represent a quantum system as P coupled classical replicas, or Trotter slices.The effective partition function is simulated at temperature PT using Metropolis-Hastings Monte Carlo.Source: D. Simulated Quantum Annealing and… · pp. 10–11
  • SQA combines local spin flips across sites and slices with global moves that flip a site's spin in every slice.The global move does not affect the coupling term between replicas.Source: D. Simulated Quantum Annealing and… · p. 11
  • SQA is initialized by SA cooling from T0 = 3 to 1/P in 60 steps, with 100 Metropolis moves per site at each temperature.It then decreases Γ linearly to 10^-8, performing five local and global moves per annealing step.Source: D. Simulated Quantum Annealing and… · p. 11

Simulated Annealing

Appendix A: Numerical proof of principle of adiabaticity

The appendices present numerical evidence on variational annealing’s ability to track adiabatic evolution and compare it with logarithmic-decay annealing baselines on random chains. They also specify conditions for this behavior and examine recurrent-network architectures and weight-sharing choices across three spin-model settings.

Appendix A: Numerical proof of principle of adiabaticity

  • VCA’s residual-energy decay exponent is 1.3–1.6 and VQA’s is approximately 1, suggesting asymptotic speedups over SA and coherent quantum annealing, whose residual energies follow a logarithmic law.Figure 8 reports residual energy per site versus annealing steps for random Ising chains with N = 32, 64, and 128.Source: Figure 8 · p. 12, Appendix A · p. 12
  • On a 20-spin uniform ferromagnetic chain, VQA tracks the exact ground energy and keeps residual energy much smaller than the gap; transferring parameters between steps is important for both VQA and VCA.The VCA free energy also agrees excellently with the exact free energy; random reinitialization is less effective than transferred parameters.Source: Appendix A · pp. 11–12, Figure 7 · p. 12

Appendix B: The variational adiabatic theorem

  • Under assumptions A1–A8, the theorem gives a sufficient bound on gradient-descent steps to maintain closeness to the instantaneous ground state, implying ground-state success probability of at least 1 − ϵ.The derivation assumes exact gradients; the authors note stochastic-gradient bounds could account for noise and second-order methods may improve scaling with the minimum gap.Source: Appendix B · pp. 13, 15
  • The theorem’s derivation assumes a non-degenerate target ground state and includes ϵ-dependent assumptions; the authors identify noisy gradients and first-order optimization as limitations for future bounds.They suggest stochastic-gradient convergence bounds and stochastic reconfiguration or natural gradient as possible extensions.Source: Appendix B · pp. 13, 15

Appendix C: Default Hyperparameters

  • The reported simulation hyperparameters yielded good performance, though the authors say more advanced hyperparameter study may improve results; VQA/VCA used one GPU workstation per run, while SA/SQA used a multicore CPU.The appendix summarizes the simulation architectures and hyperparameters in Table I.Source: Appendix C · p. 15

Appendix D: Benchmarking Recurrent neural network cells

  • For a 100-spin uniform ferromagnetic chain at criticality, tensorized RNNs achieve both lower energy variance and faster convergence than vanilla RNNs.The comparison uses energy variance per site as an indicator of optimized wave-function quality.Source: Appendix D · p. 15
  • For disordered Ising chains with random ±1 couplings at criticality, site-dependent RNN parameters yield better energy variance per spin than site-independent parameters.Source: Appendix D · p. 15
  • For the N = 20 Sherrington-Kirkpatrick model at T = 1, dilated RNNs achieve nearly an order of magnitude lower free-energy variance per spin than tensorized RNNs with comparable parameter counts.The authors suggest skip connections help dilated RNNs capture long-term dependencies more efficiently.Source: Appendix D · p. 15
  • The listed no-weight-sharing RNN configuration uses 20 dilated-RNN memory units, 40 tensorized-RNN memory units, 100 samples, and learning rate 10−4.The table caption clarifies that the sample count is the batch size used to train the RNN.Source: Appendix D · p. 16, Table I · p. 16
  • Figure 9 compares tensorized, vanilla, and dilated RNN ansatzes across a critical ferromagnetic Ising chain, a disordered random Ising chain, and the Sherrington-Kirkpatrick model.The comparisons vary weight sharing and use N = 100 spins for the ferromagnetic chain and N = 20 for the other settings; the caption gives no winning architecture.Source: Figure 9 · p. 17

Related papers

Loading 2101.10154v1…