$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+?

  • $\begingroup$ "The promise gap is 0" makes no sense. Also, you are asking two different questions. $\endgroup$ Mar 25, 2021 at 7:46
  • $\begingroup$ The promised gap is glued to $0$. The suspect is that this is the relevant difference between QSAT and LH, and projectors vs hamiltonians don't change the complexity. So it better had be a unique question. $\endgroup$
    – J.Ask
    Mar 25, 2021 at 8:05
  • $\begingroup$ This is not the promise gap. The promise gap is the absence of energies between y and n. $\endgroup$ Mar 25, 2021 at 8:06
  • $\begingroup$ If I write "starts from $0$" it is more clear? Feel free to suggest a better phrase $\endgroup$
    – J.Ask
    Mar 25, 2021 at 8:09
  • $\begingroup$ Whatever you fancy. $\endgroup$ Mar 25, 2021 at 8:11

1 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.

  • $\begingroup$ Can you give an example with 3 qubits? $\endgroup$ Mar 25, 2021 at 19:21
  • $\begingroup$ Sorry, I realized I confused myself trying to deal with exact and fixed promise gaps, which doesn't make sense. QSAT+ and QSAT are equivalent $\endgroup$
    – J.Ask
    Mar 25, 2021 at 19:35
  • $\begingroup$ However note that the higher energies of the hamiltonians are relevant for the ground energy of the total $H$ when this is frustrated, so in general they can be relevant for the promise gap $\endgroup$
    – J.Ask
    Mar 25, 2021 at 19:47
  • $\begingroup$ Sure, never claimed otherwise. $\endgroup$ Mar 25, 2021 at 20:22
  • $\begingroup$ Your answer says they are irrelevant, which is true for the decision problem. But here one have first to show that the reduction (hamiltonians to projectors with the same groundstate) lowerbounds the ground state of the original hamiltonian linearly respect to the gap in the new hamiltonian (for example considering the least second eigenvalue of the hamiltonians). $\endgroup$
    – J.Ask
    Mar 25, 2021 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.