Wishart planted ensemble: A tunably rugged pairwise Ising model with a first-order phase transition

Area of Science:

• Statistical Mechanics
• Optimization Theory
• Computational Physics

Background:

• Ising models are fundamental in statistical mechanics.
• Understanding algorithmic hardness is crucial for optimization.
• Hopfield models have applications in neural networks and optimization.

Purpose of the Study:

• To introduce the Wishart planted ensemble, a novel class of zero-field Ising models.
• To explore its connections to integer programming and the Hopfield model.
• To analyze its thermodynamic properties and algorithmic hardness.

Main Methods:

• Derivation of Thouless-Anderson-Palmer (TAP) equations for analytical properties.
• Replica and annealed approximation analyses.
• Extensive Monte Carlo simulations for validation.

Main Results:

• The Wishart planted ensemble exhibits a first-order phase transition in temperature.
• Algorithmic hardness varies significantly with a generation parameter, showing an easy-hard-easy profile.
• Analytical expression for the hardness peak location derived, considering finite-precision representation.

Conclusions:

• The Wishart planted ensemble provides a tunable benchmark for optimization algorithms.
• Hardness in this model correlates with rugged energy landscapes and locally stable paramagnetic states.
• To achieve true hardness, integer program constraints must scale with system size at fixed precision.