It’s tempting to think that the sign problem is due to rapid oscillations of the integrand. In fact, the Wikipedia article on the topic basically says as much:

In applied mathematics, the numerical sign problem is the problem of numerically evaluating the integral of a highly oscillatory function of a large number of variables.

It’s easy to pick up on this intuition. An easy way to obtain a sign problem in one dimension is to consider the integral $$ I(\xi) = \int dx\; e^{-x^2}\cos\left(\xi x\right)\text. $$ This integral has no sign problem at \(\xi = 0\), of course, and the sign problem gets exponentially worse as we increase \(|\xi|\). Simultaneously, the oscillations of the integrand get more and more rapid.

As far as I can tell, though, the general intuition that rapid oscillations are the fundamental cause of the “hard” sign problem is just not true.

Let’s start looking at another unrealistic example in one dimension. I won’t bother finding a “nice” analytic form to demonstrate, because the difficulty of the sign problem does not usually have anything to do with the analytic structure of the integrand. Here’s a simple integrand with a sign problem: $$ f(x) = e^{-|x|}\begin{cases} 1&x \le 0\\ \epsilon-1&x > 0 \end{cases} $$ The integral \(\int f\) is proportional to \(\epsilon\), while the quenched integral is always of order unity. As a result, we have \(\langle\sigma\rangle \sim \epsilon\), and the sign problem can be made arbitrarily bad without ever making the oscillations more rapid. A similar example is the integral of \(\epsilon + \cos \theta\) that features here. The mean-field restriction of the Thirring model has similar behavior, see here.

What creates the sign problem in all these cases is not the rapidness of the oscillations, but rather the fact that there are two regions that cancel each other. One region has positive sign, one has negative sign, and in order to work out the cancellations to decide whether the net integral is positive or negative, each region’s integral must be measured to very high precision. This problem is independent of the shapes of the regions. Even when we know exactly how to sample from the positive region alone, and exactly how to sample from the negative region alone, we still cannot solve the sign problem easily!

Now, these are only one-dimensional integrals, and have little to do with the interesting “physical” sign problems. What about a realistic example? Let’s consider a scalar path integral obtained by Trotterizing \(e^{-i H t}\) for the harmonic oscillator (although little would change if we switched to an interacting scalar field theory). The path integral is $$ \int \mathcal D \phi\; e^{i S}\text{, with } S = \int dx\; \frac 1 2 \left(\partial\phi\right)^2 - \frac{m^2}{2} \phi^2 $$ This is a pretty typical example of a sign problem that’s hard to solve in practice. Does it feature rapid oscillations of the integrand? The “speed” with which the integrand is oscillating is easily measured by the derivative of the imaginary part of the action: \(\frac{\partial}{\partial \phi} S_I\). This is not particularly large! In fact, this derivative gets no larger as we increase the number of sites on the lattice, while the sign problem is exponentially bad in the number of sites. Meanwhile, this derivative does become large as we take \(m\) to be small, which does not make the sign problem particularly worse.

One last way to phrase this, hearkening back to what I said earlier about the sign problem being independent of the shapes of the positive and negative regions. Suppose you are asked not to calculate an integral, but a sum of two integrals: $$ \sigma = \int dx\;f(x) + \int dy\;g(y)\text. $$ Each integrand by itself is perfectly well behaved and sign-problem-free. However, \(f(x) < 0\) for all \(x\), and \(g(y) > 0\) for all \(y\). Can you compute the sum efficiently? Monte Carlo methods will yield each integral individually with some error bars — which will overlap, so we will have a hard time deciding whether \(\sigma > 0\). You can try pairing points off, but in general \(f(x) + g(x)\) may be positive or negative, so we just create an ordinary sign problem again unless we know of a special pairing with nice properties.

And, of course, this sort of sign problem has no oscillations at all.