Two-local qubit Hamiltonians: when are they stoquastic?

We examine the problem of determining if a 2-local Hamiltonian is stoquastic by local basis changes. We analyze this problem for two-qubit Hamiltonians, presenting some basic tools and giving a concrete example where using unitaries beyond Clifford rotations is required in order to decide stoquasticity. We report on simple results for n-qubit Hamiltonians with identical 2-local terms on bipartite graphs. Our most significant result is that we give an efficient algorithm to determine whether an arbitrary n-qubit XYZ Heisenberg Hamiltonian is stoquastic by local basis changes.