Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians

DOI10.1137/19M1287511MaRDI QIDQ3387762zbMATH OpenOpenAlexWikidataFDO

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

Publication date 13 January 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.08800

zbMATH Keywords

computational complexityquantumquantum Monte Carlo Copy pre-keywordsign problemstoquastic

Mathematics Subject Classification ID

Clifford algebras, spinors (15A66) Monte Carlo methods (65C05) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Selfadjoint operator theory in quantum theory, including spectral analysis (81Q10)

Abstract: We examine the problem of determining whether a multi-qubit 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 $mathbbR$ which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.

Recommendations

• On the complexity of two dimensional commuting local Hamiltonians
• Hardness of approximation for quantum problems
• The complexity of stoquastic local Hamiltonian problems
• Strong NP-hardness of the quantum separability problem
• The Complexity of the Local Hamiltonian Problem
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• On the hardnesses of several quantum decoding problems
• Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete
• scientific article

Cites work

• A Guide to Monte Carlo Simulations in Statistical Physics
• Complexity classification of local Hamiltonian problems
• Complexity of stoquastic frustration-free Hamiltonians
• How quantum are non-negative wave functions?
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• Realizable Hamiltonians for universal adiabatic quantum computers
• The complexity of stoquastic local Hamiltonian problems
• The NP-Completeness of Edge-Coloring

This page was built for publication: Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387762)