  Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have
positive off-diagonal matrix elements in a given basis, are known to pose
severe limitations on the efficiency of Quantum Monte Carlo algorithms designed
to simulate them, due to the infamous sign problem. We study the computational
complexity associated with `curing' non-stoquastic Hamiltonians, i.e.,
transforming them into sign-problem-free ones. We prove that if such
transformations are limited to single-qubit Clifford group elements or general
single-qubit orthogonal matrices, finding the curing transformation is
NP-complete. We discuss the implications of this result.
