EXACT DETERMINATION OF ALL GROUND-STATES OF RANDOM-FIELD SYSTEMS IN POLYNOMIAL-TIME

An algorithm is developed which allows calculating all ground states of ferromagnetic and unfrustrated antiferromagnetic Ising systems with arbitrary site-dependent fields by transforming the system into an equivalent network and calculating the maximal flow. By a trial and error scheme a minimum cut is constructed which corresponds to a spin configuration. In this way each ground state is calculated with a finite probability. The algorithm is applied to site-diluted antiferromagnets in external magnetic fields. It is found that in this case its time complexity is approximately quadratic in the lattice size. As an application we calculate the distribution of overlaps between ground states of the site-diluted antiferromagnet in a strong magnetic field and we analyse the fractal structure of these ground states.