# Sign problem and stoquastic Hamiltonians

What is the sign problem in quantum simulations and how do stoquastic Hamiltonians solve it? I tried searching for a good reference that explains this but explanations regarding what the sign problem is are very hand-wavy.

A related question, for stoquastic Hamiltonians are only off-diagonal terms zero or non-positive or are diagonal terms also zero and non-positive? Slide 2 here suggests all matrix terms are non-positive, but that means the diagonals have to all be zero, as a Hamiltonian is positive semi-definite and positive semi-definite matrices have non-negative diagonal entries.

Stoquastic Hamiltonians do not suffer from the "sign problem" since for any observable A $$\langle A \rangle = \frac{1}{Z} \cdot \text{Tr } Ae^{-\beta H} = \frac{1}{Z} \cdot \sum_c A(c)p(c)$$ and all weights $$p(c) \geq 0$$.

A simple proof:

Define $$G = d I - H$$, where $$d = \text{max}_i H_{ii}$$. All matrix elements of $$G$$ are non-negative and so this holds for $$G^n, \forall n$$.

\begin{align*} \langle A \rangle & = \frac{1}{Z} \cdot \text{Tr } A e^{-\beta H} \\ &= \frac{1}{Z} \cdot \text{Tr } A e^{-\beta (dI - G)} \\ &= \frac{e^{-\beta d}}{Z} \cdot \text{Tr } A e^{\beta G} \\ &= \frac{e^{-\beta d}}{Z} \cdot \sum_n \frac{\beta^n}{n!} \text{Tr }A G^n \\ &= \frac{e^{-\beta d}}{Z} \cdot \sum_{n} \sum_{x, y} \frac{\beta^n}{n!} \cdot \langle x|A|y \rangle \langle y|G^n|x \rangle \end{align*}

and all weights $$e^{-\beta d} \cdot \frac{\beta^n}{n!} \cdot \langle y|G^n|x \rangle$$ are non-negative.

Stoquastic Hamiltonians have only non-positive off-diagonal terms, see for instance the abstract of this paper by Bravyi et al. The diagonal terms may be zero, but may also be stricly positive.

The sign problem is not restricted to only an appearance in quantum computing; it even stems from more general physics - check for instance this question and answer by user wsc on the physics stack exchange. The answer also links to this text by Troyer and Wiese.

My understanding is limited, but I know that it is closely correlated with Quantum Monte Carlo methods, which are methods of stochastic simulation of quantum mechanical systems that have been very effective, but only for Hamiltonians that do not suffer under the sign problem.

• "The sign problem goes beyond quantum computing into more general physics": It is really the opposite, the sign problem appears in all kind of areas in Monte Carlo simulations, and it happens to also appear in some contexts in quantum computing. Also, Troyer and Wiese is not an introduction to the sign problem. Jan 11 at 21:36
• @Norbert Schuch Ah; I meant to imply exactly that - that it is more general than quantum computing, and better understood in the scope (for lack of a better word) of general physics. I understand that my wording could have been more precise.
– JSdJ
Jan 11 at 21:43
• To me it sounded (and still sounds) like the problem originates in QC and then evolved into other fields, while it is quite the opposite. (Even the study of stoquastic Hamiltonians in complexity is partly linked to ideas from QMC, i.e. making a rigorous version of such simulations; the other part comes of course from adiabatic computation with stoquastic Hamiltonians.) Jan 11 at 23:03
• @NorbertSchuch My wording was - again/still - off. I hope it now reads better; thanks for your remarks.
– JSdJ
Jan 12 at 9:18