The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness

Abstract

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}}⊈{\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}}\ne {\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.