From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
arXiv:1711.04083 · doi:10.1103/PhysRevE.97.043303
Abstract
We present a methodology for generating Ising Hamiltonians of tunable complexity and with a priori known ground states based on a decomposition of the model graph into edge-disjoint subgraphs. The idea is illustrated with a spin-glass model defined on a cubic lattice, where subproblems, whose couplers are restricted to the two values {-1,+1}, are specified on unit cubes and are parametrized by their local degeneracy. The construction is shown to be equivalent to a type of three-dimensional constraint satisfaction problem known as the tiling puzzle. By varying the proportions of subproblem types, the Hamiltonian can span a dramatic range of typical computational complexity, from fairly easy to many orders of magnitude more difficult than prototypical bimodal and Gaussian spin glasses in three space dimensions. We corroborate this behavior via experiments with different algorithms and discuss generalizations and extensions to different types of graphs.
arXiv comment18 pages, 14 figures
References in corpus (34)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- Defining and detecting quantum speedup
- A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
- Architectural considerations in the design of a superconducting quantum annealing processor
- Feedback-optimized parallel tempering Monte Carlo
- A case study in programming a quantum annealer for hard operational planning problems
- The Entropy of the K-Satisfiability Problem
- Monte Carlo Simulations of Spin Glasses at Low Temperatures
- Probing for quantum speedup in spin glass problems with planted solutions
- Optimized simulated annealing for Ising spin glasses
- A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
- Scaling of stiffness energy for 3d +/-J Ising spin glasses
- Triviality of the Ground State Structure in Ising Spin Glasses
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Temperature and Disorder Chaos in Three-Dimensional Ising Spin Glasses
- Population annealing: Theory and application in spin glasses
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- MAX 2-SAT with up to 108 qubits
- Zero and low temperature behavior of the two-dimensional Ising spin glass
- Chaos and universality in two-dimensional Ising spin glasses
- Ground-state clusters of two-, three- and four-dimensional +-J Ising spin glasses
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Evidence for existence of many pure ground states in 3d Spin Glasses
- Chaos in spin glasses revealed through thermal boundary conditions
- Practical engineering of hard spin-glass instances
- Correlations between the dynamics of parallel tempering and the free-energy landscape in spin glasses
- Assessment of Quantum Annealing for the Construction of Satisfiability Filters
- The +/-J Spin Glass: Effects of Ground State Degeneracy
- Patch-planting spin-glass solution for benchmarking
Cited by in corpus (12)
- On the Computational Complexity of Curing the Sign Problem
- Hybrid quantum annealing for larger-than-QPU lattice-structured problems
- The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
- Computational Overhead of Locality Reduction in Binary Optimization Problems
- Computational hardness of spin-glass problems with tile-planted solutions
- Fluctuation guided search in quantum annealing
- Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
- Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
- Non-equilibrium criticality and efficient exploration of glassy landscapes with memory dynamics
- Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
- 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