The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this article, we take a new direction by introducing the physically motivated notion of “ground state connectivity” of local Hamiltonians, which captures problems in areas ranging from quantum stabilizer codes to quantum memories. Roughly, “ground state connectivity” corresponds to the natural question: Given two ground states |Ψ〉 and |ϕ〉 of a local Hamiltonian H , is there an “energy barrier” (with respect to H ) along any sequence of local operations mapping |Ψ〉 to |ϕ〉? We show that the complexity of this question can range from QCMA-complete to PSPACE-complete, as well as NEXP-complete for an appropriately defined “succinct” version of the problem. As a result, we obtain a natural QCMA-complete problem, a goal which has generally proven difficult since the conception of QCMA over a decade ago. Our proofs rely on a new technical tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution must traverse under certain conditions. We show that this lemma is essentially tight with respect to the length of the unitary evolution in question.The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this article, we take a new direction by introducing the physically motivated notion of “ground state connectivity” of local Hamiltonians, which captures problems in areas ranging from quantum stabilizer codes to quantum memories. Roughly, “ground state connectivity” corresponds to the natural question: Given two ground states |Ψ〉 and |ϕ〉 of a local Hamiltonian H , is there an “energy barrier” (with respect to H ) along any sequence of local operations mapping |Ψ〉 to |ϕ〉? We show that the complexity of this question can range from QCMA-complete to PSPACE-complete, as well as NEXP-complete for an appropriately defined “succinct” version of the problem. As a result, we obtain a natural QCMA-complete problem, a goal which has generally proven difficult since the conception of QCMA over a decade ago. Our proofs rely on a new technical tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution must traverse under certain conditions. We show that this lemma is essentially tight with respect to the length of the unitary evolution in question.

ACM Transactions on Computation TheoryApr 14, 201810 citations

The Complexity of the Local Hamiltonian Problem

Julia Kempe, Alexei Kitaev, Oded Regev

Lecture notes in computer scienceJan 1, 200471 citations

QCMA hardness of ground space connectivity for commuting Hamiltonians

David Gosset, Jenish C. Mehta, Thomas Vidick

In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H . It was shown in [Gharibian and Sikora, ICALP15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H . It was shown in [Gharibian and Sikora, ICALP15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.

arXiv:1610.03582QuantumJul 14, 201710 citations

Ground states of center-of-mass preserving Hamiltonians

Sanjay Moudgalya, Nicolas Regnault, Bogdan Andrei Bernevig

Bulletin of the American Physical SocietyMar 7, 20180 citations

Computing local properties in the trivial phase

Yichen Huang

A translation-invariant gapped local Hamiltonian is in the trivial phase if it can be connected to a completely decoupled Hamiltonian with a smooth path of translation-invariant gapped local Hamiltonians. For the ground state of such a Hamiltonian, we show that the expectation value of a local observable can be computed in time $\text{poly}(1/δ)$ in one spatial dimension and $e^{\text{poly}\log(1/δ)}$ in two and higher dimensions, where $δ$ is the desired (additive) accuracy. The algorithm applies to systems of finite size and in the thermodynamic limit. It only assumes the existence but not any knowledge of the path.A translation-invariant gapped local Hamiltonian is in the trivial phase if it can be connected to a completely decoupled Hamiltonian with a smooth path of translation-invariant gapped local Hamiltonians. For the ground state of such a Hamiltonian, we show that the expectation value of a local observable can be computed in time $\text{poly}(1/δ)$ in one spatial dimension and $e^{\text{poly}\log(1/δ)}$ in two and higher dimensions, where $δ$ is the desired (additive) accuracy. The algorithm applies to systems of finite size and in the thermodynamic limit. It only assumes the existence but not any knowledge of the path.

arXiv:2001.10763Jan 29, 20201 citation

\text{poly}(1/δ)

in one spatial dimension and

e^{\text{poly}\log(1/δ)}

in two and higher dimensions, where

δ

is the desired (additive) accuracy. The algorithm applies to systems of finite size and in the thermodynamic limit. It only assumes the existence but not any knowledge of the path.