Optimized simulated annealing for Ising spin glasses
arXiv:1401.1084 · doi:10.1016/j.cpc.2015.02.015
Abstract
We present several efficient implementations of the simulated annealing algorithm for Ising spin glasses on sparse graphs. In particular, we provide a generic code for any choice of couplings, an optimized code for bipartite graphs, and highly optimized implementations using multi-spin coding for graphs with small maximum degree and discrete couplings with a finite range. The latter codes achieve up to 50 spin flips per nanosecond on modern Intel CPUs. We also compare the performance of the codes to that of the special purpose D-Wave devices built for solving such Ising spin glass problems.
11 pages, includes C++11 codes. Minor updates
References in corpus (5)
- Defining and detecting quantum speedup
- Multi-GPU Accelerated Multi-Spin Monte Carlo Simulations of the 2D Ising Model
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization
- Robust Classification with Adiabatic Quantum Optimization
Cited by in corpus (53)
- Microwave photonics with superconducting quantum circuits
- Quantum information processing with superconducting circuits: a review
- Defining and detecting quantum speedup
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- What is the Computational Value of Finite Range Tunneling?
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Nonnegative/binary matrix factorization with a D-Wave quantum annealer
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Coherent coupled qubits for quantum annealing
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- QuantumCumulants.jl: A Julia framework for generalized mean-field equations in open quantum systems
- Bayesian Network Structure Learning Using Quantum Annealing
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Benchmarking a quantum annealing processor with the time-to-target metric
- SiQAD: A Design and Simulation Tool for Atomic Silicon Quantum Dot Circuits
- Scalable spin-glass optical simulator
- Global warming: Temperature estimation in annealers
- Uncertain fate of fair sampling in quantum annealing
- Quantum processor-inspired machine learning in the biomedical sciences
- Challenges of variational quantum optimization with measurement shot noise
- 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
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- Quantitative Evaluation of Hardware Binary Stochastic Neurons
- Simulated bifurcation for higher-order cost functions
- Degeneracy, degree, and heavy tails in quantum annealing
- Real-time Trading System based on Selections of Potentially Profitable, Uncorrelated, and Balanced Stocks by NP-hard Combinatorial Optimization
- Efficient subgraph-based sampling of Ising-type models with frustration
- Simulated quantum annealing of double-well and multi-well potentials
- Limitations of optimization algorithms on noisy quantum devices
- Optimally Stopped Optimization
- Fast Quantum Methods for Optimization
- Computational hardness of spin-glass problems with tile-planted solutions
- Memory-Efficient FPGA Implementation of Stochastic Simulated Annealing
- Heterogeneous Quantum Computing for Satellite Constellation Optimization: Solving the Weighted K-Clique Problem
- ON-OFF Neuromorphic ISING Machines using Fowler-Nordheim Annealers
- Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits
- Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling
- Feeding the multitude: A polynomial-time algorithm to improve sampling
- Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
- Dynamical process of a bit-width reduced Ising model with simulated annealing
- Search for the Heisenberg spin glass on rewired square lattices with antiferromagnetic interaction
- Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
- Highly parallel algorithm for the Ising ground state searching problem
- Adding color: Visualization of energy landscapes in spin glasses
- Enhancing In-vehicle Multiple Object Tracking Systems with Embeddable Ising Machines
- Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization
- Classical Simulated Annealing Using Quantum Analogues
- Evolutionary Approaches to Optimization Problems in Chimera Topologies
- Quantum-inspired Ising machine using sparsified spin connectivity
- Quantum Computation