Combinatorics

Discrete mathematics

Physics

Graph

Qubit

Mathematics

Hamiltonian path

Hamiltonian path problem

Mathematical optimization

Hamiltonian (control theory)

Political science

Quantum mechanics

Unitary state

Quantum

SIAM Journal on Computing

We examine the problem of determining whether a multiqubit two-local Hamiltonian can be made stoquastic by single-qubit unitary transformations. We prove that when such a Hamiltonian contains one-local terms, then this task can be NP-hard. This is shown by constructing a class of Hamiltonians for which performing this task is equivalent to deciding 3-SAT. In contrast, we show that when such a Hamiltonian contains no one-local terms then this task is easy; namely, we present an algorithm which decides, in a number of arithmetic operations over $\mathbb{R}$ which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.

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