From local to global ground states in Ising spin glasses

Abstract

We consider whether it is possible to find ground states of frustrated spin systems by solving them locally. Using spin glass physics and Imry-Ma arguments in addition to numerical benchmarks we quantify the power of such local solution methods and show that for the average low-dimensional spin glass problem outside the spin- glass phase the exact ground state can be found in polynomial time. In the second part we present a heuristic, general-purpose hierarchical approach which for spin glasses on chimera graphs and lattices in two and three dimensions outperforms, to our knowledge, any other solver currently around, with significantly better scaling performance than simulated annealing.

10 pages, 15 figures, 5 tables, minor additions and corrections

References in corpus (5)

• Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
• Study of the de Almeida-Thouless line using power-law diluted one-dimensional Ising spin glasses
• Thermodynamic glass transition in a spin glass without time-reversal symmetry
• Spin glasses in a field: Three and four dimensions as seen from one space dimension
• The three dimensional Ising spin glass in an external magnetic field: the role of the silent majority

Cited by in corpus (5)

• Towards Hybrid Classical-Quantum Computation Structures in Wirelessly-Networked Systems
• A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
• Multi-Community Detection in Signed Graphs Using Quantum Hardware
• Classical Simulated Annealing Using Quantum Analogues
• Evolutionary Approaches to Optimization Problems in Chimera Topologies