arXiv:1802.03408 · Nature Communications

On the computational complexity of curing non-stoquastic Hamiltonians

Milad Marvian, Daniel A. Lidar, Itay Hen

Published Apr 5, 2019• 58 citations

Abstract

Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.

DOI: 10.1038/s41467-019-09501-6

Related papers

Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing

Marios Ioannou, Stephen Piddock, Milad Marvian +2 more

arXiv:2007.11964Jul 23, 20200 citations

Sign-curing local Hamiltonians: termwise versus global stoquasticity and the use of Clifford transformations.

Marios Ioannou, Stephen Piddock, Milad Marvian +2 more

Jul 23, 20203 citations

Easing the Monte Carlo sign problem

Dominik Hangleiter, Ingo Roth, Daniel Nagaj +1 more

arXiv:1906.02309Science AdvancesAug 14, 202086 citations

Complexity of stoquastic frustration-free Hamiltonians

Sergey B. Bravyi, Barbara M. Terhal

arXiv:0806.1746Jun 10, 20083 citations

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

Joel Klassen, Milad Marvian, Stephen Piddock +3 more

arXiv:1906.08800SIAM Journal on ComputingJan 1, 202024 citations

Complexity of Stoquastic Frustration-Free Hamiltonians

Sergey B. Bravyi, Barbara M. Terhal

SIAM Journal on ComputingNov 20, 2009124 citations

arXiv:1802.03408 · Nature Communications

On the computational complexity of curing non-stoquastic Hamiltonians

Milad Marvian, Daniel A. Lidar, Itay Hen

Published Apr 5, 2019• 58 citations

arXiv HTML PDF

Abstract

DOI: 10.1038/s41467-019-09501-6

Related papers

Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing

Marios Ioannou, Stephen Piddock, Milad Marvian +2 more

We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is $\textbf{StoqMA}$ -complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove $\textbf{coNP}$ -hardness of deciding global stoquasticity in a fixed basis and $Σ_2^p$ -hardness of deciding global stoquasticity under single-qubit transformations. As a last result, we expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D $XYZ$ Hamiltonians.We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is $\textbf{StoqMA}$-complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove $\textbf{coNP}$-hardness of deciding global stoquasticity in a fixed basis and $Σ_2^p$-hardness of deciding global stoquasticity under single-qubit transformations. As a last result, we expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D $XYZ$ Hamiltonians.

arXiv:2007.11964Jul 23, 20200 citations

Sign-curing local Hamiltonians: termwise versus global stoquasticity and the use of Clifford transformations.

Marios Ioannou, Stephen Piddock, Milad Marvian +2 more

We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We prove coNP-hardness of deciding global stoquasticity in a fixed basis and $\Sigma_2^p$ -hardness of deciding global stoquasticity under single-qubit transformations. We expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D XYZ Hamiltonians.We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We prove coNP-hardness of deciding global stoquasticity in a fixed basis and $\Sigma_2^p$-hardness of deciding global stoquasticity under single-qubit transformations. We expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D XYZ Hamiltonians.

Jul 23, 20203 citations

Easing the Monte Carlo sign problem

Dominik Hangleiter, Ingo Roth, Daniel Nagaj +1 more

Quantum Monte Carlo (QMC) methods are the gold standard for studying equilibrium properties of quantum many-body systems. However, in many interesting situations, QMC methods are faced with a sign problem, causing the severe limitation of an exponential increase in the runtime of the QMC algorithm. In this work, we develop a systematic, generally applicable, and practically feasible methodology for easing the sign problem by efficiently computable basis changes and use it to rigorously assess the sign problem. Our framework introduces measures of non-stoquasticity that-as we demonstrate analytically and numerically-at the same time provide a practically relevant and efficiently computable figure of merit for the severity of the sign problem. Complementing this pragmatic mindset, we prove that easing the sign problem in terms of those measures is generally an NP-complete task for nearest-neighbor Hamiltonians and simple basis choices by a reduction to the MAXCUT-problem.Quantum Monte Carlo (QMC) methods are the gold standard for studying equilibrium properties of quantum many-body systems. However, in many interesting situations, QMC methods are faced with a sign problem, causing the severe limitation of an exponential increase in the runtime of the QMC algorithm. In this work, we develop a systematic, generally applicable, and practically feasible methodology for easing the sign problem by efficiently computable basis changes and use it to rigorously assess the sign problem. Our framework introduces measures of non-stoquasticity that-as we demonstrate analytically and numerically-at the same time provide a practically relevant and efficiently computable figure of merit for the severity of the sign problem. Complementing this pragmatic mindset, we prove that easing the sign problem in terms of those measures is generally an NP-complete task for nearest-neighbor Hamiltonians and simple basis choices by a reduction to the MAXCUT-problem.

arXiv:1906.02309Science AdvancesAug 14, 202086 citations

Complexity of stoquastic frustration-free Hamiltonians

Sergey B. Bravyi, Barbara M. Terhal

We study several problems related to properties of non-negative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a "frustration free" ground-state. A Hamiltonian belongs to this class iff it can be represented as $H=\sum_a H_a$ where (1) every term $H_a$ acts non-trivially on a constant number of qubits, (2) every term $H_a$ has real non-positive off-diagonal matrix elements in the standard basis, and (3) the ground-state of $H$ is a ground-state of every term $H_a$ . Secondly, we generalize the Cook-Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA -- a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call "stoquastic k-SAT" such that stoquastic k-SAT is contained in MA for any constant $k$ , and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first non-trivial example of a MA-complete promise problem.We study several problems related to properties of non-negative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a "frustration free" ground-state. A Hamiltonian belongs to this class iff it can be represented as $H=\sum_a H_a$ where (1) every term $H_a$ acts non-trivially on a constant number of qubits, (2) every term $H_a$ has real non-positive off-diagonal matrix elements in the standard basis, and (3) the ground-state of $H$ is a ground-state of every term $H_a$. Secondly, we generalize the Cook-Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA -- a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call "stoquastic k-SAT" such that stoquastic k-SAT is contained in MA for any constant $k$, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first non-trivial example of a MA-complete promise problem.

arXiv:0806.1746Jun 10, 20083 citations

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

Joel Klassen, Milad Marvian, Stephen Piddock +3 more

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 $\mathbb{R}$ which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.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 $\mathbb{R}$ which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.

arXiv:1906.08800SIAM Journal on ComputingJan 1, 202024 citations

Complexity of Stoquastic Frustration-Free Hamiltonians

Sergey B. Bravyi, Barbara M. Terhal

We study several problems related to properties of nonnegative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a “frustration-free” ground-state. A Hamiltonian belongs to this class iff it can be represented as $H=\sum_{a}H_{a}$ where (1) every term $H_{a}$ acts nontrivially on a constant number of qubits, (2) every term $H_{a}$ has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term $H_{a}$ . Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call “stoquastic k-SAT” such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.We study several problems related to properties of nonnegative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a “frustration-free” ground-state. A Hamiltonian belongs to this class iff it can be represented as $H=\sum_{a}H_{a}$ where (1) every term $H_{a}$ acts nontrivially on a constant number of qubits, (2) every term $H_{a}$ has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term $H_{a}$. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call “stoquastic k-SAT” such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.

SIAM Journal on ComputingNov 20, 2009124 citations

We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is

\textbf{StoqMA}

-complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove

\textbf{coNP}

-hardness of deciding global stoquasticity in a fixed basis and

Σ_2^p

-hardness of deciding global stoquasticity under single-qubit transformations. As a last result, we expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D

XYZ

Hamiltonians.

\Sigma_2^p

-hardness of deciding global stoquasticity under single-qubit transformations. We expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D XYZ Hamiltonians.

H=\sum_a H_a

where (1) every term

H_a

acts non-trivially on a constant number of qubits, (2) every term

H_a

has real non-positive off-diagonal matrix elements in the standard basis, and (3) the ground-state of

H

is a ground-state of every term

H_a

. Secondly, we generalize the Cook-Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA -- a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call "stoquastic k-SAT" such that stoquastic k-SAT is contained in MA for any constant

k

, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first non-trivial example of a MA-complete promise problem.

\mathbb{R}

which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.

H=\sum_{a}H_{a}

where (1) every term

H_{a}

acts nontrivially on a constant number of qubits, (2) every term

H_{a}

has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term

H_{a}

. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call “stoquastic k-SAT” such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.