  Stoquastic Hamiltonians play a role in the computational complexity of the
local Hamiltonian problem as well as the study of classical simulability. In
particular, stoquastic Hamiltonians can be straightforwardly simulated using
Monte Carlo techniques. We address the question of whether two or more
Hamiltonians may be made simultaneously stoquastic via a unitary
transformation. This question has important implications for the complexity of
simulating quantum annealing where quantum advantage is related to the
stoquasticity of the Hamiltonians involved in the anneal. We find that for
almost all problems no such unitary exists and show that the problem of
determining the existence of such a unitary is equivalent to identifying if
there is a solution to a system of polynomial (in)equalities in the matrix
elements of the initial and transformed Hamiltonians. Solving such a system of
equations is NP-hard. We highlight a geometric understanding of this problem in
terms of a collection of generalized Bloch vectors.
