The complexity of LH with constant gap

Question

Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue of $H$ is either $\leq a$ or $\geq b$, with $b-a$ vanishing as an inverse polynomial in the size of the original problem. If the gap vanishes faster, the problem is not known to be in QMA, and if the gap is larger the problem is easier.

I read often, for example in wikipedia, that for constant gap QMA-hardness is a conjecture (equivalent to a quantum version of the PCP theorem). However, I sometimes read the opposite: for example Gharibian's phd thesis problem 1.7, or Gosset, Nagaj definition 4 for the qsat subcase.

Effectively, I don't understand why I cannot repeat each term in $H$ a polynomial number of times, and obtain an equivalent problem with constant gap. Is this reasoning naively wrong, or maybe I am not reading the PCP statement correctly. Maybe "constant gap" is just a fast way to say something more specific?

PS. I posted this on the quantum computing board too, where is probably more inherent. I noted the board after posting here, let me know if I have to cancel this.

Answer 1

Your original problem formulation is not correct. It's missing some normalization on $H$, otherwise it could be the case that all eigenvalues of $H$ are always smaller than $a$, making the problem completely trivial, so it couldn't possibly be QMA-complete.

One natural normalization is $||H||\leq 1$, which you can enforce by saying that if $H$ is expressed as the sum of $m$ local terms, then each term should have norm at most $1/m$. Now all eigenvalues of $H$ must lie in $[-1,1]$. For this normalization, the complexity of constant-gap Local Hamiltonian is conjectured to be QMA-hard. Note that this problem is NP-hard because of the classical PCP theorem.

Answer 2

Copied from my answer to the same question at qc.se:

---

The reasoning is naively wrong: When talking about the Local Hamiltonian problem with a specific promise gap (or spectral gap), you need to fix the overall energy scale. Usually, this means that the Hamiltonian $$ H=\sum h_i $$ with $k$-local terms $h_i$ is chosen such that $\|h_i\|\le1$ (with $\|\cdot\|$ the operator norm). Otherwise, any statement about the difficulty of the problem would be vacuous, as you could just rescale the Hamiltonian $H\to cH$ with some constant $c>0$, just as your "repeat each term $x$ times" argument does.

(Overall, one has to be more careful since it depends where the terms act and you can re-group terms, but if $k$ is constant this will not matter (or apply them several times as you suggest). Usually, a safe way is to bound the total norm of all terms which act non-trivially on any given site.)

Answer 3

In the standard survey LH is defined with normalization 1 on the single terms $h_{i}$. The actual promised gap $b-a$ for the least eigenvalue of the total hamiltonian $H=\sum_{i}^{m}h_{i}$ is referred to as the "absolute promise gap", and $(b-a)/m$ is referred to as the "relative promise gap" or simply the promise gap. The "Quantum PCP by gap amplification" conjecture states that LH is QMA-hard with constant relative promise gap.
So the answer is the OP (myself) didn't read the quantum PCP statement correctly.