Hardness and ease of curing the sign problem for two-local qubit Hamiltonians
Joel Klassen (TU Delft - QCD/Terhal Group, TU Delft - QuTech Advanced Research Centre)
Milad Marvian (Massachusetts Institute of Technology)
Stephen Piddock (University of Bristol)
Marios Ioannou (Ludwig Maximilians University)
Itay Hen (University of Southern California)
Barbara M. Terhal (TU Delft - Quantum Computing, TU Delft - QCD/Terhal Group, TU Delft - QuTech Advanced Research Centre)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.