Patch-planting spin-glass solution for benchmarking
arXiv:1706.02825 · doi:10.1103/PhysRevE.96.023312
Abstract
We introduce an algorithm to generate (not solve) spin-glass instances with planted solutions of arbitrary size and structure. First, a set of small problem patches with open boundaries is solved either exactly or with a heuristic, and then the individual patches are stitched together to create a large problem with a known planted solution. Because in these problems frustration is typically smaller than in random problems, we first assess the typical computational complexity of the individual patches using population annealing Monte Carlo, and introduce an approach that allows one to fine-tune the typical computational complexity of the patch-planted system. The scaling of the typical computational complexity of these planted instances with various numbers of patches and patch sizes is investigated and compared to random instances.
9 pages, 12 figures, 2 tables
References in corpus (33)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Search by Local Adiabatic Evolution
- Defining and detecting quantum speedup
- Architectural considerations in the design of a superconducting quantum annealing processor
- Experimental signature of programmable quantum annealing
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Universality in three-dimensional Ising spin glasses: A Monte Carlo study
- Quantum Optimization of Fully-Connected Spin Glasses
- Quantum versus Classical Annealing of Ising Spin Glasses
- Probing for quantum speedup in spin glass problems with planted solutions
- A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Quantum annealing correction for random Ising problems
- Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
- Quantum Annealing Correction with Minor Embedding
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- 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
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- Population annealing: Theory and application in spin glasses
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Evidence against a mean field description of short-range spin glasses revealed through thermal boundary conditions
- Practical engineering of hard spin-glass instances
- Efficient subgraph-based sampling of Ising-type models with frustration
- Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
- borealis - A generalized global update algorithm for Boolean optimization problems
- Persistence and Memory in Patchwork Dynamics for Glassy Models
Cited by in corpus (11)
- Boosting Monte Carlo simulations of spin glasses using autoregressive neural networks
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
- Computational hardness of spin-glass problems with tile-planted solutions
- Estimating the Density of States of Frustrated Spin Systems
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- Approximate ground states of the random-field Potts model from graph cuts
- Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
- Posiform Planting: Generating QUBO Instances for Benchmarking
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking