Sign problems, Terry Tau, and open science

Recently a colleague of mine had a pretty amazing experience in open science. In brief, an outstanding conjecture in determinant quantum Monte Carlo about the sign problem was posed and answered by Terrance Tao and others on mathoverflow. The total turnaround time was approximately 3 days from beginning to finish, making it a wonderful example of the power of open science.

First some background. Pretty much any Monte Carlo simulation of fermions suffers from the notorious sign problem. In essence, because the exchange of two Fermi particle contributes a negative weight, any stochastic sampling of a Fermi distribution will result in approximately equal positive and negative parts. In fact, if one measures the sign weight throughout a Monte Carlo simulation, it can be seen to decay to zero exponentially with the number of states/particles and projection time/inverse temperature. There’s been some work by Troyer and Wiese that showed the sign problem in some specific instances falls into the NP-complete complexity class (http://arxiv.org/abs/cond-mat/0408370), though this deserves a blog post of its own. The upshot is it’s a HUGE hindrance to studying fermions and any progress on this front is generally considered very important.

Determinant quantum Monte Carlo (DQMC) is a specific breed of QMC that stochastically samples determinants representing all permutations of single particle fermion states. It was first introduced by some heavy hitters in the QMC committee to study the 2D Fermi Hubbard model (http://journals.aps.org/prb/abstract/10.1103/PhysRevB.80.075116), where they found that for the spin unpolarized system (equal spin-up and spin-down) there was no sign problem! Essentially the spin-up and spin-down signs could cancel each other. Later, Wu and Zhang extended the space of models that were sign problem free in DQMC (http://journals.aps.org/prb/abstract/10.1103/PhysRevB.71.155115). In both these works, however, the lack of a sign problem was found empirically without any hard proof.

Now, my friend and colleague Lei Wang wanted to know exactly why this true, and possibly if more models could fall under this category of sign problem free. Empirically, people see the following:

If Ai=(0 B_i^{T} // B_i 0), where B_i are real matrices and i=1,2,…,N, then det(I+exp(A_1)exp(A_2)…exp(A_N))≥0

For spin unpolarized systems it’s pretty clear why each A_i is of this form, but for others systems it’s not as clear. Anyways, this was the question he posed to mathoverflow. Amazingly people jumped on it, and it wasn’t long before Fields Medalist Terrance Tao got involved! It was then only a matter of 3 days before the conjecture was proven to be true in a mathematically rigorous way. For a full writeup of the proof, you can check out Tao’s blog.

When I found out about this, I was super excited to see the open science model working so incredibly well. Tao really is a leader on this front (though perhaps it’s much easier for him to command a crowd-sourced legion as well). At any rate, I would love to see more of this in the future, and I think we can take this instance as an excellent example of success.