4
$\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 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.

$\endgroup$
2
2
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ In Kitaev's reduction the terms of $H$ have eigenvalues in $(0,1)$ so the normalization you say is equivalent to $||𝐻||≤m$. This isn't affected if I add terms. So I think the answer is I didn't get the QPCP statement. With Kitaev normalization it would say that LH is QMA-hard with $O(m)$ gap, so in this sense it is not a conjecture that LH is QMA-hard with constant gap $\endgroup$ – J.Ask Mar 20 at 12:36
  • 1
    $\begingroup$ $\|H\|=1$ is not a natural normalization at all! Generally, you want individual terms to be normalized (and rule out artificial "splitting up" of one term into several identical ones), such as each term in the Hamiltonian being a projector. Certainly, this is highly relevant when asking about promise gaps (or anything else) being O(1) or O(N). $\endgroup$ – Norbert Schuch Mar 20 at 12:56
  • $\begingroup$ @NorbertSchuch: When people say "constant gap LH is hard", aren't they using the normalization $H \leq 1$? We really want the promise gap to be a small constant fraction of the total energy of $H$, right? $\endgroup$ – Robin Kothari Mar 21 at 9:10
  • $\begingroup$ @J.Ask: Can you link to the paper you're talking about? With that normalization, the promise gap achieved in the reduction should be small, at most O(1) or so. If it were a constant fraction of $m$, that would prove the QPCP conjecture. $\endgroup$ – Robin Kothari Mar 21 at 9:18
  • 2
    $\begingroup$ @J.Ask This paper by Aharonov et al (arxiv.org/abs/1309.7495) has a formal statement of the problem (Def 1.1) and QPCP conjecture (Conjecture 1.3). It normalizes the Hamiltonian as Norbert suggests, and uses "relative gap", which is gap divided by total energy, as the gap. The conjecture is that the problem is hard for some constant relative gap. $\endgroup$ – Robin Kothari Mar 22 at 17:55
2
$\begingroup$

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

$\endgroup$
0
$\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.

$\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.