Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering

Abstract

Population annealing is a Monte Carlo algorithm that marries features from simulated annealing and parallel tempering Monte Carlo. As such, it is ideal to overcome large energy barriers in the free-energy landscape while minimizing a Hamiltonian. Thus, population annealing Monte Carlo can be used as a heuristic to solve combinatorial optimization problems. We illustrate the capabilities of population annealing Monte Carlo by computing ground states of the three-dimensional Ising spin glass with Gaussian disorder, whilst comparing to simulated annealing and parallel tempering Monte Carlo. Our results suggest that population annealing Monte Carlo is significantly more efficient than simulated annealing but comparable to parallel tempering Monte Carlo for finding spin-glass ground states.

arXiv comment9 pages, 7 figures

References in corpus (13)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Optimization with Extremal Dynamics
• Optimized parallel tempering simulations of proteins
• Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
• Domain-Wall Free-Energy of Spin Glass Models:Numerical Method and Boundary Conditions
• Scaling of stiffness energy for 3d +/-J Ising spin glasses
• Triviality of the Ground State Structure in Ising Spin Glasses
• Aspect-Ratio Scaling and The Stiffness Exponent $\theta$ for Ising Spin Glasses
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Improved extremal optimization for the Ising spin glass
• Evidence against a mean field description of short-range spin glasses revealed through thermal boundary conditions
• The ground state energy of the Edwards-Anderson spin glass model with a parallel tempering Monte Carlo algorithm
• Monte Carlo Methods for Rough Free Energy Landscapes: Population Annealing and Parallel Tempering

Cited by in corpus (50)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Coherent Ising machines -- Quantum optics and neural network perspectives
• Population annealing: Theory and application in spin glasses
• GPU accelerated population annealing algorithm
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Hybrid quantum annealing for larger-than-QPU lattice-structured problems
• Coherent Ising machines with error correction feedback
• Understanding population annealing Monte Carlo simulations
• Model-Free Data-Driven Inference in Computational Mechanics
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• Optimization of population annealing Monte Carlo for large-scale spin-glass simulations
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Analysis and Optimization of Population Annealing
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• Effects of setting the temperatures in the parallel tempering Monte Carlo algorithm
• Bond chaos in spin glasses revealed through thermal boundary conditions
• Computational hardness of spin-glass problems with tile-planted solutions
• Detecting many-body Bell non-locality by solving Ising models
• Fair sampling of ground-state configurations of binary optimization problems
• Population Annealing Simulations of a Binary Hard Sphere Mixture
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Patch-planting spin-glass solution for benchmarking
• Exploring first-order phase transitions with population annealing
• Spin Glass in the Bond-Diluted J1-J2 Ising Model on the Square Lattice
• Equilibrium Microcanonical Annealing for First-Order Phase Transitions
• Three-dimensional universality class of Ising model with power-law-correlated critical disorder
• Accelerating equilibrium spin-glass simulations using quantum annealers via generative deep learning
• Amorphous quantum magnets in a two-dimensional Rydberg atom array
• Approximate ground states of the random-field Potts model from graph cuts
• An effective introduction to the Markov Chain Monte Carlo method
• Deep reinforced learning heuristic tested on spin-glass ground states: The larger picture
• Optimal schedules for annealing algorithms
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• Dynamic Greedy Algorithms for the Edwards-Anderson Model
• Evidence of many thermodynamic states of the three-dimensional Ising spin glass
• Nonflat Histogram Techniques for Spin Glasses
• Performance of machine-learning-assisted Monte Carlo in sampling from simple statistical physics models
• SWAP algorithm for lattice spin models
• Quantum-enhanced Markov Chain Monte Carlo for systems larger than your Quantum Computer
• Highly parallel algorithm for the Ising ground state searching problem
• Massively parallel simulations for disordered systems
• Ground-state magnetization of the Ising spin glass: A recursive numerical method and Chen-Ma scaling
• Genetic-tunneling driven energy optimizer for spin systems
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• Generalized Probabilistic Approximate Optimization Algorithm
• Ground state interface exponents of the diluted Sherrington-Kirkpatrick spin glass
• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization
• Population annealing with topological defect driven nonlocal updates for spin systems with quenched disorder