# Is there a list of models that do and do not have the QMC sign problem?

The sign problem is a huge limitation of QMC, but it's not easy to tell by looking at a Hamiltonian if it has the sign problem. Often there will be some clever transformation that allows you to avoid the sign problem.

Is there somewhere that a database of models with known sign-problem-free implementations are listed?

Example of a nontrivial avoidance of the sign problem:

The antiferromagnetic Heisenberg Model is:

$$H = J \sum \limits_{\langle i,j \rangle} \vec S_i \cdot \vec S_j = J \sum \limits_{\langle i,j \rangle} [ S^z_i S^z_j + \frac{1}{2} ( S^+_i S^-_j + S^-_i S^+_j ) ]$$

If you naively implement the stochastic series exchange QMC, you will get a sign problem, but that can be avoided on bipartite lattices by adding a constant offset and doing a sublattice rotation arXiv:1101.3281, p. 144 (AIP Conference Proceedings 2010, 1297, 135). This is all pretty simple mathematically, but it is not trivial to figure out in the first place, and it would be easy to imagine encountering the apparent sign problem and simply giving up.

And even more nontrivial example is a method for avoiding the sign problem in this antiferromagnetic Heisenberg model with random ferromagnetic bonds: Phys. Rev. B 1994, 50 (21), 15803–15807.

Addition: if there is no such list, what are some examples of sign-problem that have solutions like this?

• I suppose this is related to a very hot recent topic on "stoquasticity". Stoquastic problems in the complexity class StoqP can be solved in polynomial time (no sign problem). I believe Sergiy Bravyi, Stephen Jordan, Milad Marvian, Keisuke Fujii, Hidetoshi Nishimori and others have worked a lot on stoquastic vs. non-stoquastic problems very recently. Is this paper helpful at all? nature.com/articles/s41467-019-09501-6 – Nike Dattani May 15 '20 at 4:07
• What if there is no list? Then we will get no answers. What do you think about asking people instead to give examples of interesting Hamiltonians that can be "cured" ? For example I know that a transverse-field Ising Hamiltonian with linear $X$ terms can be cured by multiplying the whole Hamiltonian by $Z$ and $Z^\dagger$ on the left and right sides respectively. All $X$ terms then become $-X$ and the Hamiltonian goes from being non-stoquastic to stoquastic. It's interesting to know what other Hamiltonians can be "cured" this way, but a comprehensive list might not exist? – Nike Dattani May 15 '20 at 16:36

## 2 Answers

The general problem of determining whether a Hamiltonian can be transformed into "stoquastic" (i.e. sign-problem-free) form by local transformations is NP-hard:

https://arxiv.org/abs/1906.08800

https://arxiv.org/abs/1802.03408

On the other hand, there are lots of individual Hamiltonians for which people have figured out clever tricks to bring them into stoquastic form, as the question asker has noted. Unfortunately, I am not aware of any place that these have been systematically aggregated.

You can tell if a Hamiltonian is sign-free by looking at it in the form that it is handed to you. If the Hamiltonian is real and the off-diagonals are non-positive then it is Stoquastic (which is sign-free). Moreover, every Hamiltonian is sign-free if you don't care about the computational complexity of transforming it: In the basis that it is diagonal, the diagonal is real and all the off diagonals are zero and the Hamiltonian is Stoquastic and sign-free.

The issue often is, and that is what Stephen Jordan points out as well, that the Hamiltonian in the original form may not seem to be Stoquastic yet it might be if you do a small amount of work (say local transformations or an efficient poly-time algorithm). It is hard to decide whether a non-stoquastic looking Hamiltonian is Stoquastic IF one allows for some SMALL amount of computation to transform it.