Improved belief propagation algorithm finds many Bethe states in the random-field Ising model on random graphs

Area of Science:

• Statistical physics
• Computational complexity

Background:

• The Belief Propagation (BP) algorithm is crucial for analyzing complex systems.
• Understanding its behavior on random field Ising models is key to phase transition physics.

Purpose of the Study:

• To empirically study the BP algorithm on random field Ising models at zero temperature.
• To introduce and utilize extremal solutions for BP equations.
• To develop an improved BP scheme for finding ground states and analyzing fixed points.

Main Methods:

• Empirical study of the BP algorithm on random regular graphs.
• Introduction of extremal solutions to constrain spin configurations.
• Development of a novel BP scheme using bounds on BP messages.
• Analysis of fixed point behavior with system size.

Main Results:

• Extremal solutions fix a fraction of spins, which percolates at the phase transition.
• The new BP scheme efficiently finds minimum energy configurations.
• The number of stable fixed points of the BP algorithm increases with system size in the critical region.

Conclusions:

• The developed BP scheme is effective for finding ground states of Ising models.
• The growth of fixed points in the critical region raises new questions about the physics of these models.