6

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 have this question already posted on the theoretical cs board, because I didn't notice there is this probably more specific one. Let me know if I have to cancel it.

glS
  • 27,510
  • 7
  • 37
  • 125
J.Ask
  • 159
  • 6

2 Answers2

4

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

Norbert Schuch
  • 8,142
  • 1
  • 19
  • 30
2

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.

J.Ask
  • 159
  • 6