Hardness and Ease of Curing the Sign Problem for Two-Local Qubit\n Hamiltonians

We examine the problem of determining whether a multi-qubit two-local\nHamiltonian can be made stoquastic by single-qubit unitary transformations. We\nprove that when such a Hamiltonian contains one-local terms, then this task can\nbe NP-hard. This is shown by constructing a class of Hamiltonians for which\nperforming this task is equivalent to deciding $3$-SAT. In contrast, we show\nthat when such a Hamiltonian contains no one-local terms then this task is\neasy, namely we present an algorithm which decides, in a number of arithmetic\noperations over $\\mathbb{R}$ which is polynomial in the number of qubits,\nwhether the sign problem of the Hamiltonian can be cured by single-qubit\nrotations.\n