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

Joel Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, Barbara M. Terhal

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)
15 Downloads (Pure)


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 languageEnglish
Pages (from-to)1332-1362
JournalSIAM Journal on Computing
Issue number6
Publication statusPublished - 2020


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


Dive into the research topics of 'Hardness and ease of curing the sign problem for two-local qubit Hamiltonians'. Together they form a unique fingerprint.

Cite this