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

2019/06/20 by Joel Klassen, Milad Marvian, Klassen, Joel +9 · 1 citation
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.1906.08800

openalex publication_date 2019/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We examine the problem of determining whether a multi-qubit two-local\nHamiltonian can be made stoquastic by single-qubit unitary transformations. We\nprove that when such a Hamiltonian contains one-local terms, then this task can\nbe NP-hard. This is shown by constructing a class of Hamiltonians for which\nperforming this task is equivalent to deciding 3-SAT. In contrast, we show\nthat when such a Hamiltonian contains no one-local terms then this task is\neasy, namely we present an algorithm which decides, in a number of arithmetic\noperations over \ℝ which is polynomial in the number of qubits,\nwhether the sign problem of the Hamiltonian can be cured by single-qubit\nrotations.\n

Cited by

• Stoquasticity is not enough: towards a sharper diagnostic for Quantum Monte Carlo simulability

Related

• Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing
• Complexity classification of local Hamiltonian problems
• Complexity of geometrically local stoquastic Hamiltonians
• Universal quantum dynamics from two 2-local Hamiltonians
• The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians