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

Journal article (2020)

Authors

J.D. Klassen QuTech Advanced Research Centre, QCD/Terhal Group - 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
B.M. Terhal QuTech Advanced Research Centre, QuTech Advanced Research Centre, QCD/Terhal Group - QuTech Advanced Research Centre
Affiliation
QuTech Advanced Research Centre
Copyright: © 2020 J.D. Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, B.M. Terhal
DOI: https://doi.org/10.1137/19M1287511
Quantum Computational complexity Quantum Monte Carlo Sign problem Stoquastic
More Info
expand_more

Published Date

2020

Language

English

Reuse Rights

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.

Affiliation

QuTech Advanced Research Centre

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.

Files

19m1287511.pdf
(.pdf | 0.756 Mb)