The Complexity of the Local Hamiltonian Problem

Sergey B. Bravyi, Matthew B. Hastings

We study complexity of several problems related to the Transverse field Ising Model (TIM). First, we consider the problem of estimating the ground state energy known as the Local Hamiltonian Problem (LHP). It is shown that the LHP for TIM on degree-3 graphs is equivalent modulo polynomial reductions to the LHP for general k-local `stoquastic' Hamiltonians with any constant $k\ge 2$. This result implies that estimating the ground state energy of TIM on degree-3 graphs is a complete problem for the complexity class StoqMA - an extension of the classical class MA. As a corollary, we complete the complexity classification of 2-local Hamiltonians with a fixed set of interactions proposed recently by Cubitt and Montanaro. Secondly, we study quantum annealing algorithms for finding ground states of classical spin Hamiltonians associated with hard optimization problems. We prove that the quantum annealing with TIM Hamiltonians is equivalent modulo polynomial reductions to the quantum annealing with a certain subclass of k-local stoquastic Hamiltonians. This subclass includes all Hamiltonians representable as a sum of a k-local diagonal Hamiltonian and a 2-local stoquastic Hamiltonian.

Ryo Kawasaki, Harumichi Nishimura

S. Narayanaswami

André Chailloux, Or Sattath

In this paper, we study variants of the canonical Local Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local Hamiltonian problem. The input for the Separable Local Hamiltonian problem is the same as the Local Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable Sparse Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable Sparse Hamiltonian problem is QMA(2)-Complete, while Separable Local Hamiltonian is in QMA. This should be compared to the Local Hamiltonian problem, and the Sparse Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable Sparse Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.

Bei Zeng, Xie Chen, D. L. Zhou +1 more

Itay Shalit, Mark Zhandry

The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.