Computational hardness of spin-glass problems with tile-planted solutions
arXiv:1907.10809 · doi:10.1103/PhysRevE.101.023316
Abstract
We investigate the computational hardness of spin-glass instances on a square lattice, generated via a recently introduced tunable and scalable approach for planting solutions. The method relies on partitioning the problem graph into edge-disjoint subgraphs, and planting frustrated, elementary subproblems that share a common local ground state, which guarantees that the ground state of the entire problem is known a priori. Using population annealing Monte Carlo, we compare the typical hardness of problem classes over a large region of the multi-dimensional tuning parameter space. Our results show that the problems have a wide range of tunable hardness. Moreover, we observe multiple transitions in the hardness phase space, which we further corroborate using simulated annealing and simulated quantum annealing. By investigating thermodynamic properties of these planted systems, we demonstrate that the harder samples undergo magnetic ordering transitions which are also ultimately responsible for the observed hardness transitions on changing the sample composition.
arXiv comment12 pages, 14 figures, 1 table, loads of love
References in corpus (40)
- Ising formulations of many NP problems
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- Simulated Tempering: A New Monte Carlo Scheme
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Architectural considerations in the design of a superconducting quantum annealing processor
- Feedback-optimized parallel tempering Monte Carlo
- Universality in three-dimensional Ising spin glasses: A Monte Carlo study
- The Scaling Window of the 2-SAT Transition
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Error corrected quantum annealing with hundreds of qubits
- Quantum versus Classical Annealing of Ising Spin Glasses
- Probing for quantum speedup in spin glass problems with planted solutions
- Optimized simulated annealing for Ising spin glasses
- Low-temperature behavior of two-dimensional Gaussian Ising spin glasses
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Quantum annealing correction for random Ising problems
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Population annealing: Theory and application in spin glasses
- A deceptive step towards quantum speedup detection
- GPU accelerated population annealing algorithm
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- Practical engineering of hard spin-glass instances
- Optimization of population annealing Monte Carlo for large-scale spin-glass simulations
- Performance of a quantum annealer on range-limited constraint satisfaction problems
- Frustration - how it can be measured
- Equation Planting: A Tool for Benchmarking Ising Machines
- Critical behavior of the Coulomb-glass model in the zero-disorder limit: Ising universality in a system with long-range interactions
- Patch-planting spin-glass solution for benchmarking
- Frustration in vicinity of transition point of Ising spin glasses
Cited by in corpus (12)
- Boosting Monte Carlo simulations of spin glasses using autoregressive neural networks
- Understanding population annealing Monte Carlo simulations
- Computational Overhead of Locality Reduction in Binary Optimization Problems
- Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
- Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
- Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
- Posiform Planting: Generating QUBO Instances for Benchmarking
- Mapping State Transition Susceptibility in Quantum Annealing
- Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
- Spin glasses and percolation
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
- Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization