The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
arXiv:1906.00275 · doi:10.1103/PhysRevE.101.052102
Abstract
We propose the Wishart planted ensemble, a class of zero-field Ising models with tunable algorithmic hardness and specifiable (or planted) ground state. The problem class arises from a simple procedure for generating a family of random integer programming problems with specific statistical symmetry properties, but turns out to have intimate connections to a sign-inverted variant of the Hopfield model. The Hamiltonian contains only 2-spin interactions, with the coupler matrix following a type of Wishart distribution. The class exhibits a classical first-order phase transition in temperature. For some parameter settings the model has a locally-stable paramagnetic state, a feature which correlates strongly with difficulty in finding the ground state and suggests an extremely rugged energy landscape. We analytically probe the ensemble thermodynamic properties by deriving the Thouless-Anderson-Palmer equations and free energy and corroborate the results with a replica and annealed approximation analysis; extensive Monte Carlo simulations confirm our predictions of the first-order transition temperature. The class exhibits a wide variation in algorithmic hardness as a generation parameter is varied, with a pronounced easy-hard-easy profile and peak in solution time towering many orders of magnitude over that of the easy regimes. By deriving the ensemble-averaged energy distribution and taking into account finite-precision representation, we propose an analytical expression for the location of the hardness peak and show that at fixed precision, the number of constraints in the integer program must increase with system size to yield truly hard problems. The Wishart planted ensemble is interesting for its peculiar physical properties and provides a useful and analytically-transparent set of problems for benchmarking optimization algorithms.
arXiv comment40 pages, 19 figures, 1 lonely table
References in corpus (23)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum annealing with more than one hundred qubits
- Defining and detecting quantum speedup
- A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
- Universality in three-dimensional Ising spin glasses: A Monte Carlo study
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Probing for quantum speedup in spin glass problems with planted solutions
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Mean-Field Equations for Spin Models with Orthogonal Interaction Matrices
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
- A physicist's approach to number partitioning
- Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- Energy landscapes, supergraphs, and "folding funnels" in spin systems
- A deceptive step towards quantum speedup detection
- Locked constraint satisfaction problems
- Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
- Typology of phase transitions in Bayesian inference problems
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- Mean-field theory for a spin-glass model of neural networks: TAP free energy and paramagnetic to spin-glass transition
- Equation Planting: A Tool for Benchmarking Ising Machines
- Patch-planting spin-glass solution for benchmarking
Cited by in corpus (12)
- Variational Neural Annealing
- Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
- Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems
- Ising Hamiltonian Minimization: Gain-Based Computing with Manifold Reduction of Soft-Spins vs Quantum Annealing
- Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
- Mean-field Coherent Ising Machines with artificial Zeeman terms
- Message Passing Variational Autoregressive Network for Solving Intractable Ising Models
- Two-dimensional Parallel Tempering for Constrained Optimization
- Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
- A method for quantifying the generalization capabilities of generative models for solving Ising models
- Continuous Approximation of the Ising Hamiltonian: Exact Ground States and Applications to Fidelity Assessment in Ising Machines
- Polaritonic XY-Ising Machine