Hardness and ease of curing the sign problem for two-local qubit Hamiltonians