Complexity of Quantum Satisfiability vs Local Hamiltonians

Question

$k$QSAT$c$ is the promise problem where the input, given in an explicit encoding with finite number of bits, is a set $\{p_{1},p_{2},\ldots p_{m}\}$ of $k$-local projectors over a $n$-qbits register, such that the least eigenvalue $\varepsilon_{\min}$ of $\sum_{i=1}^{m}p_{i}$ is either $\varepsilon_{\min}=0\tag{y}\label{eq:QSATy-1}$ or $\varepsilon_{\min}(n)\geq n^{-c}\tag{n}\label{eq:QSATn-1}$ and the answer is yes (no) in the y (n) case.

$k$LH$c$ is the promise problem where the input, given in an explicit encoding with finite number of bits, is a set $\{h_{1},h_{2},\ldots h_{m}\}$ of $k$-local hamiltonians, with eigenvalues in $[0,1]$, over a $n$-qbits register, such that the least eigenvalue $\varepsilon_{\min}$ of $\sum_{i=1}^{m}p_{i}$ is either $\varepsilon_{\min}\leq\varepsilon\tag{y}\label{eq:LHy-1}$ where $\varepsilon$ is a parameter given in input, or $\varepsilon_{\min}(n)\geq\varepsilon+n^{-c}\tag{n}\label{eq:LHn-1}$ and the answer is yes (no) in the y (n) case.

With same constants, the QSAT problem restricts LH in two things. First, its promise gap is glued to $0$. Second, its hamiltonian terms are projectors. So I can define two new problems.

QSAT+ Same as QSAT but with general local hamiltonians with eigenvalues in $[0,1]$.

LH- Same as LH but with local projectors.

As pointed out in the answer of a previous question, the classical 5local construction clearly works for projectors, so 5LH- is QMA-hard. Then, since 5LH is in QMA, there is a polynomial reduction from 5LH to 5LH- via a quantum circuit verification for 5LH. Of course, I expect in this case way more natural reductions. However, for $k=2$, we know that 2LH is QMA-hard, and 2QSAT is in P. So what is the complexity of 2LH- and of 2QSAT+?

Answer 1

"2QSAT+" can be defined in two different ways:

• You can define it such that you allow for general Hamiltonians, but you demand that for a "yes"-instance, the ground state has the property that it minimizes the energy of each term individually. (This is really the spirit of QSAT.) Then, this does not change the complexity, because the energy you assign to all states above the ground space is irrelevant.

• You define it such that you want to check if the ground state energy is <=0 or >= 1/poly(n). Then, the problem is QMA-hard, since you can use the Hamiltonian terms to incorporate the energy shift to general energy bounds.

• In the latter case, you could impose the promise that the energy is exactly zero, or $\ge 1/\mathrm{poly}(N)$. It is not clear how much knowing that the energy would be exactly zero in that case would help.