Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension

Abstract

Spin systems with frustration and disorder are notoriously difficult to study both analytically and numerically. While the simulation of ferromagnetic statistical mechanical models benefits greatly from cluster algorithms, these accelerated dynamics methods remain elusive for generic spin-glass-like systems. Here we present a cluster algorithm for Ising spin glasses that works in any space dimension and speeds up thermalization by at least one order of magnitude at temperatures where thermalization is typically difficult. Our isoenergetic cluster moves are based on the Houdayer cluster algorithm for two-dimensional spin glasses and lead to a speedup over conventional state-of-the-art methods that increases with the system size. We illustrate the benefits of the isoenergetic cluster moves in two and three space dimensions, as well as the nonplanar chimera topology found in the D-Wave Inc.~quantum annealing machine.

5 pages, 4 figures

References in corpus (5)

• Universality in three-dimensional Ising spin glasses: A Monte Carlo study
• The Percolation Signature of the Spin Glass Transition
• Correlations between the dynamics of parallel tempering and the free-energy landscape in spin glasses
• Universality and universal finite-size scaling functions in four-dimensional Ising spin glasses
• Percolation thresholds on planar Euclidean relative neighborhood graphs

Cited by in corpus (75)

• Adiabatic Quantum Computing
• Perspectives of quantum annealing: Methods and implementations
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• What is the Computational Value of Finite Range Tunneling?
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Modernizing Quantum Annealing using Local Searches
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Quantum-enhanced Markov chain Monte Carlo
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
• Population annealing: Theory and application in spin glasses
• A deceptive step towards quantum speedup detection
• Demonstration of algorithmic quantum speedup
• Boosting Monte Carlo simulations of spin glasses using autoregressive neural networks
• Next-Generation Topology of D-Wave Quantum Processors
• Global warming: Temperature estimation in annealers
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Scalable Emulation of Sign-Problem$-$Free Hamiltonians with Room Temperature p-bits
• Maximum-Entropy Inference with a Programmable Annealer
• Readiness of Quantum Optimization Machines for Industrial Applications
• Matching microscopic and macroscopic responses in glasses
• 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
• Optimization of population annealing Monte Carlo for large-scale spin-glass simulations
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• Computational hardness of spin-glass problems with tile-planted solutions
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Fair sampling of ground-state configurations of binary optimization problems
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Patch-planting spin-glass solution for benchmarking
• Collective Monte Carlo updates through tensor network renormalization
• Cluster Percolation in the Two-Dimensional Ising Spin Glass
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Tensor network Monte Carlo simulations for the two-dimensional random-bond Ising model
• Feeding the multitude: A polynomial-time algorithm to improve sampling
• Site and bond percolation thresholds in $K_{n,n}$-based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
• Accelerating equilibrium spin-glass simulations using quantum annealers via generative deep learning
• Percolation of Fortuin-Kasteleyn clusters for the random-bond Ising model
• Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
• Sampling diverse near-optimal solutions via algorithmic quantum annealing
• Quantum Monte Carlo Annealing with Multi-Spin Dynamics
• Ordering Behavior of the Two-Dimensional Ising Spin Glass with Long-Range Correlated Disorder
• From quantum-enhanced to quantum-inspired Monte Carlo
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Performance of machine-learning-assisted Monte Carlo in sampling from simple statistical physics models
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• Demonstration of error-suppressed quantum annealing via boundary cancellation
• Quantum-enhanced Markov Chain Monte Carlo for systems larger than your Quantum Computer
• Multi-Community Detection in Signed Graphs Using Quantum Hardware
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Spin glasses and percolation
• Massively parallel simulations for disordered systems
• Entanglement-assisted variational algorithm for discrete optimization problems
• Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
• Cluster percolation in the three-dimensional $\pm J$ random-bond Ising model
• An Overview of Approaches to Modernize Quantum Annealing Using Local Searches
• Optimization and benchmarking of the thermal cycling algorithm
• Population annealing with topological defect driven nonlocal updates for spin systems with quenched disorder
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
• Classical Simulated Annealing Using Quantum Analogues
• Analog Errors in Quantum Annealing: Doom and Hope
• Recent quantum runtime (dis)advantages
• Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
• Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes
• q-Gaussian Crossover in Overlap Spectra towards 3D Edwards-Anderson Criticality
• Discrete Equilibrium Sampling with Arbitrary Nonequilibrium Processes