When is the "minus sign problem" in quantum simulations an obstacle?

Question

The "minus sign problem" in quantum simulation refers to the fact that the probability amplitudes are not positive-definite, and it is my understanding that this leads to numerical instability when for example summing over paths, histories or configurations since large amplitudes of one phase can completely negate other large contributions but with the reverse phase. Without controlling this somehow, the sampling of alternative configurations has to be extremely dense, at least for situations where interference is expected to be important.

Assuming I haven't misunderstood it so far, my main question is when this is a show-stopper and when it can be ignored, and what the best workarounds are.

As an example, let's say that I want to simulate Compton scattering or something similar, numerically, to second order. I could evaluate the Feynman diagrams numerically to a certain resolution and sum them. I assume this won't work well. In Lattice QCD, complete field configurations are randomly generated and the action calculated and amplitude summed I guess (I have only superficial knowledge of Lattice QCD unfortunately).

Answer 1

The sign problem is an obstacle in two cases:

1) Simulating spin or boson hamiltonians with geometric frustration (Although here we can rely on the Marshall Sign Rule to tell us what hamiltonians will always have positive-definite ground-state wavefunctions)

2) Simulating fermi hamiltonians away from special symmetry points (in reference to Kostya's answer, we always integrate the Grassmann fields analytically -- the tool for this is usually called a "Hubbard-Stratonovich transformation," which leaves you with an auxillary bosonic field that you sample through Monte Carlo -- the sign problem shows up in that your probability measure is, again, not positive definite necessarily. Sometimes, by chance, you get lucky though -- the Hubbard model with an attractive interaction, or in general at half filling, has no sign problem - but this seems to be fortuitous at best.)

A good introduction to the sign problem can be found here: http://arxiv.org/abs/cond-mat/0408370

The main problem with "reweighting" is tackled in equation 7 of that paper: exponential growth of error in both particle number and inverse temperature (both of which we're trying to scale to infinity...)

Answer 2

As for the lattice part: here, you're interested in doing Monte Carlo Markov chains, which consists of summing over configurations $s$, each having a certain weight $p(s)$ and for which your observable $O$ takes the value $O(s)$. Normally, you propose a new configuration $s'$ at each step, calculate it's probability relative to your current configuration $p(s')/p(s)$, pull a random number $q \in [0,1]$ out of a hat and you switch configurations $s \mapsto s'$ iff $p(s')/p(s) > q.$ Thus if you start with a 'positive' configuration, you'll never pass by a 'negative' configuration, so that a significant part (typically ~half) of your phase space is never seen by your Monte Carlo run; your final estimate for $\langle O \rangle$ will thus be nonsense.

[Note: you could propose another scheme (the above one is called Metropolis), but fundamentally you run into problems because a Markov chain with negative weights doesn't make sense.]

There is a lot of literature on the sign problem in lattice QCD, as it is still open in general. A typical way out is reweighting; by noting that $$p(s) = \frac{p(s)}{|p(s)|} |p(s)|,$$ you can safely choose a new weight $\pi(s) = |p(s)| > 0$ and multiply every observable by the sign of the weight, $$O(s) \mapsto \frac{p(s)}{|p(s)|} O(s).$$ However, this might be expensive and even though formally the method is correct, it's not very elegant or insightful. However, since it's an open problem, not everyone will agree on its status or a way out...

Answer 3

I think that there is a slight misrepresentation of a problem in your question. The fact that quantum-mechanical amplitudes are generally complex numbers is not the root of the problem. It is usually solved by going into "imaginary time". By changing $t\to -it$ you effectively obtain the statistical mechanics problem instead of the quantum mechanical one:
$$ t \to -it,\quad p_0\to -ip_0$$ $$\int\!\!\!\cal{D}\phi\; exp\left[i\int\!\!\!dt\; \cal{L}[\phi]\right] \to \int\!\!\!\cal{D}\phi\; exp\left[-\int\!\!\!dt\; H[\phi]\right]$$ Note that Lagrangian is effectively replaced by Hamiltonian. And, instead of summing some complex numbers we've got the real and positive numbers to sum. Which is the work for the Metropolis algorithm.

The good news are that this actually works well. The bad news is that this only works for bosonic fields. For fermions your path integral is over Grassmanian-number-valued field. And there is no way of (well, effectively) represent the Grassmaian number in numerical calculations.

There are lots of tricks to deal with fermions and this is a rapidly developing field and I'm not an expert there at all. One of the ways to go is to calculate the integral over the fermions analytically, leaving only (sometimes, effective) bosonic degrees of freedom. Which gives you something like: $$\int\!\!\!\cal{D}\phi\; exp\left[-\int\!\!\!dt\; H[\phi]\right]\rho[\phi]$$ with $\rho[\phi]$ being not necessarily positive. That is where Metropolis ceases to work effectively and/or even properly.

Further you can read the article on Wikipedia.