From local to global ground states in Ising spin glasses
arXiv:1408.1901 · doi:10.1103/PhysRevB.91.024201
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.
arXiv comment10 pages, 15 figures, 5 tables, minor additions and corrections
References in corpus (16)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Defining and detecting quantum speedup
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- A scalable control system for a superconducting adiabatic quantum optimization processor
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Lower Critical Dimension of Ising Spin Glasses
- Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
- A scalable readout system for a superconducting adiabatic quantum optimization system
- Study of the de Almeida-Thouless line using power-law diluted one-dimensional Ising spin glasses
- Ising spin glass transition in magnetic field out of mean-field
- 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
- Fractal Droplets in Two Dimensional Spin Glasses
- Generating droplets in two-dimensional Ising spin glasses by using matching algorithms
Cited by in corpus (19)
- Adiabatic Quantum Computing
- Quantum optimization using variational algorithms on near-term quantum devices
- Digitized adiabatic quantum computing with a superconducting circuit
- What is the Computational Value of Finite Range Tunneling?
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Network Community Detection On Small Quantum Computers
- Building an iterative heuristic solver for a quantum annealer
- Boosting quantum annealer performance via sample persistence
- Towards Hybrid Classical-Quantum Computation Structures in Wirelessly-Networked Systems
- Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
- Blockchain platform with proof-of-work based on analog Hamiltonian optimisers
- Ground-state magnetization of the Ising spin glass: A recursive numerical method and Chen-Ma scaling
- Multi-Community Detection in Signed Graphs Using Quantum Hardware
- Classical Simulated Annealing Using Quantum Analogues
- Evolutionary Approaches to Optimization Problems in Chimera Topologies
- Partial Reinitialisation for Optimisers