A density of state approach to the sign problem
Most of the successes of lattice QCD are strictly connected with advances in numerical methods. In particular, importance sampling Monte Carlo methods have underpinned lattice QCD calculations since the early days of the field. However, it is well known that importance sampling methods fail in cases when one has to sample over configurations whose occurrence is suppressed by the Monte Carlo measure. Typical examples are first order phase transitions, in which two equally probable equilibrium states are connected by configurations with probability of occurrence exponentially suppressed with the system size, or the sign problem, whereby strong cancellations occurring for observables evaluated over highly probable configurations give a high relative weight to less recurring states. A possible way around these problems is a direct sampling of the density of states through a non-Markovian Random Walk in configuration space, as proposed by Wang and Landau a few years ago. In this contribution, I review the Logarithmic Linear Relaxation (LLR) method, a recently introduced algorithm in the Wang-Landau class that allows us to determine density of states over several orders of magnitude with the same relative accuracy. After an introduction to the ideas inspiring the algorithm and the presentation of some practical implementations, I discuss some applications to spin and gauge systems, with emphasis on the sign problem and the challenges it presents.