Monte Carlo simulations

Question

I was wondering what were the models of statistical physics that are still considered difficult/slow to simulate (exactly, or approximately) with the current technology of Monte Carlo approaches. I can think of growing long self-avoiding walks, simulate very dense hard spheres configurations, etc... though I may be wrong since I am not aware of the new approaches to tackle these problems. It could be nice to have a brief description of the way people attack these difficult simulations.

Answer 1

Lattice gauge theory is extremely demanding (four dimensions, small space and time scales, extremely complicated dynamics, etc.), and application-specific supercomputing infrastructure has been used for it. Monte Carlo simulations are used to demonstrate QCD phenomenology.

Answer 2

Here is a bit of a braindump, ranging from things physicists actually write down to theory that might never be seen by anyone in a lab. Please comment if you want some more specific responses, and I can try to hunt something down.

The large particle physics projects use intensive MC simulations, and these are not computationally quick or easy, taking days or weeks to run (my only direct experience is with SNO, and indir.ectly CERN because of that, but this must be true for most projects). These often seem very specific (i.e. they model much of the world, including where dirt might come from and so on, not something like 'hard discs' or other abstract systems)

As Steve Huntsman mentions, lattice guage theory is demanding (though there have been many huge successes!), both in terms of the theory and in terms of the crazy calculations people have succeeded in doing.

Outside of my direct experience, but within recent reading, random surfaces and the 'surface integrals' (which are in some sense analogous to 'path integrals', though I don't know enough physics to know why) are so hard that we are very far from making any sort of reasonable success. There are many good survey articles by physicists on the subject (google searching will get some), but as a mathematician it is worthwhile to remember that these models are still fairly mathematically intractable.

Statistical physics (of the graph-dynamics/spin-system type) is, as far as I know, a mixed bag right now. Until recently, 'all' of it was I think quite hard. Some recent advances (especially coupling from the past) have allowed sampling from the Ising model on a lattice and a number of other formerly intractable problems, while leaving other nearby problems sort of untouched.

I don't have any great references for the above, and am not involved in that research, so take it with a grain of salt. One source you should really look at is David Wilson's spectacular archive on MCMC in general. He seems to have a strong interest in physical models: http://dimacs.rutgers.edu/~dbwilson/exact.html/

Another general reference (it is not primarily about physics, but has physics references at the end, and was an intro to the area for me) is http://www.ams.org/bull/2009-46-02/S0273-0979-08-01238-X/S0273-0979-08-01238-X.pdf. In it, he suggests reading "Statistical Mechanics: Algorithms and Computations" by Krauth (2006). I have only looked at it briefly, but it certainly touches upon many modern problems, including those that you mention, and is probably fairly up-to-date.

EDIT: I'll add something that is probably obvious, just in case you are new, since it wasn't obvious to me when I first looked at this subject. The 'hard' examples you mention (like solid-balls-in-boxes) are the ones that are just on the borderline between being tractable math and total messes. The Ising model has now crossed over into 'tractable' land, as have some types of graph-colouring problems. On the other hand, the first thing I mention (use of MC for large particle physics experiments) is often completely intractable, and nobody can turn these sorts of things into math problems - physicists just do something that seems reasonable and run the simulation for a while. There's nothing wrong with that, but you should be aware that the types of 'mathy' hard sampling problems you mention are ones where there is some hope of rigorously showing that your sample is close to correct, and there are many more problems where rigorous and/or sharp analysis is essentially impossible.

Answer 3

Lattice gauge theory is indeed still very demanding, although the last decade has seen tremendous progress, both in terms of algorithms and of software implementations that make good use of modern computer hardware (GPUs & Co.). To some extent, lattice gauge theory simulations now serve as benchmarks for some HPC systems.

A hard problem is still posed by lattice gauge theories with fermions in the presence of a chemical potential (i.e. finite-density QCD), where there exists a "sign problem", i.e. where the determinant of the Dirac operator appearing in the path integral to be evaluated is no longer positive, whence the ordinary Markov-chain MC methods no longer apply. There are some attempts to bypass this using complex Langevin methods (but the theoretical foundation isn't 100% settled) or imaginary chemical potentials (but the continuation to real chemical potential only gets you so far).