HARDNESS AND EASE OF CURING THE SIGN PROBLEM FOR TWO-LOCAL QUBIT HAMILTONIANS

Klassen, Joel; Marvian, Milad; Piddock, Stephen; Ioannou, Marios; Hen, Itay und Terhal, Barbara M. (2020): HARDNESS AND EASE OF CURING THE SIGN PROBLEM FOR TWO-LOCAL QUBIT HAMILTONIANS. In: Siam Journal on Computing, Bd. 49, Nr. 6: S. 1332-1362

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.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Physik
• Themengebiete: 500 Naturwissenschaften und Mathematik > 530 Physik
• ISSN: 0097-5397
• Sprache: Englisch