## Abstract

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 R which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.

Original language | English |
---|---|

Pages (from-to) | 1332-1362 |

Journal | SIAM Journal on Computing |

Volume | 49 |

Issue number | 6 |

DOIs | |

Publication status | Published - 2020 |

## Keywords

- Computational complexity
- Quantum
- Quantum Monte Carlo
- Sign problem
- Stoquastic