5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Mar 20, 2021 at 7:16
  • 2
    $\begingroup$ I guess you are not reading quantum PCP conjecture correctly. See here for a more precise statement. Essentially you need the fraction $ \gamma = \frac{b - a}{m} $ to be constant. $\endgroup$
    – tsgeorgios
    Mar 20, 2021 at 10:01

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
12
  • $\begingroup$ This is a good answer I think but is there not a subtle difference between the promise gap and the spectral gap? There could be a promised gap even in a classical problem unrelated to hamiltonians. $\endgroup$
    – Mark S
    Mar 20, 2021 at 3:27
  • $\begingroup$ I'm not sure I'm getting your answer. Are you saying that a proper statement of the LH problem should require that the sum of each term acting on the same subregister should be normalized to $1$?. Then, when this is not stated, it is not a conjecture that LH is QMA hard for constant gap, but only for $O(m)$ gap. $\endgroup$
    – J.Ask
    Mar 20, 2021 at 12:45
  • $\begingroup$ @MarkS There is a big difference, not even a subtle difference. But both behave the same under rescaling, so for both it is crucial to set the scale. $\endgroup$
    – Norbert Schuch
    Mar 20, 2021 at 12:54
  • $\begingroup$ @J.Ask There is always some scale setting involved, otherwise O(1), O(m), O(exp(m)) etc. are all completely vacuous. Do you have a reference of a paper which treats the subject thoroughly yet does not define such a scale? $\endgroup$
    – Norbert Schuch
    Mar 20, 2021 at 12:55
  • $\begingroup$ @NorbertSchuch In the standard survey link as well as in original Kitaev's book link the normalization is on the single terms. So for that definition LH is QMA-complete for constant gap. Do we agree? $\endgroup$
    – J.Ask
    Mar 20, 2021 at 15:53
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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