<p>Your original problem formulation is not correct. It's missing some normalization on <span class="math-container">$H$</span>, otherwise it could be the case that all eigenvalues of <span class="math-container">$H$</span> are always smaller than <span class="math-container">$a$</span>, making the problem completely trivial, so it couldn't possibly be QMA-complete.</p>
<p>One natural normalization is <span class="math-container">$||H||\leq 1$</span>, which you can enforce by saying that if <span class="math-container">$H$</span> is expressed as the sum of <span class="math-container">$m$</span> local terms, then each term should have norm at most <span class="math-container">$1/m$</span>. Now all eigenvalues of <span class="math-container">$H$</span> must lie in <span class="math-container">$[-1,1]$</span>. 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.</p>

CC BY-SA 4.0
2021-03-20T12:36:37.163Z
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
J.Ask
CC BY-SA 4.0
2021-03-20T12:56:30.470Z
$\|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).
Norbert Schuch
CC BY-SA 4.0
2021-03-21T09:10:38.580Z
@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?
Robin Kothari
CC BY-SA 4.0
2021-03-21T09:18:10.517Z
@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.
Robin Kothari
CC BY-SA 4.0
2021-03-21T11:00:02.893Z
@RobinKothari In the standard survey [link](https://arxiv.org/pdf/quant-ph/0210077.pdf) as well as in original Kitaev's book [link](https://www.ams.org/books/gsm/047/gsm047-endmatter.pdf) the normalization is like that. The total hamiltonian is then "normalized" to $m$. And the gap can be constant. As a newbie of the argument I was taking the word "constant" in the QPCP statement literally, and I wanted to make sure with this question. But it seems by the answers that there is indeed some confusion with the different conventions
J.Ask
CC BY-SA 4.0
2021-03-21T11:31:11.137Z
@RobinKothari I don't know. It depends whether they are talking about Quantum PCP or not. From a more physics-motivated point of view, it seems very relevant whether a constant gap for a system where each term is normalized is hard: This is in between a 1/poly(n) gap and the QPCP gap, which does not make sense for systems with spatially local interactions. So both questions are interesting! It is just that I would describe QPCP as "constant fraction of total energy/total $\|H\|$.)
Norbert Schuch
CC BY-SA 4.0
2021-03-21T11:32:32.880Z
Note that also from a non-physics point (where you don't care about spatial locality of the interaction) it is natural to normalize the Hamiltonian this way: Hamiltonians are, pretty much by definition, sums of individual terms (whether spatially local or k-local, or something else), and these local terms are the fundamental constitutents. Normalizing the fundamental constituents certainly seems the most natural thing to do.
Norbert Schuch
CC BY-SA 4.0
2021-03-21T11:33:32.860Z
@J.Ask I don't think anyone is confused as to what QPCP means.
Norbert Schuch
CC BY-SA 4.0
2021-03-22T17:55:30.687Z
@J.Ask This paper by Aharonov et al (https://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.
Robin Kothari
CC BY-SA 4.0
2021-03-20T01:46:47.040Z
2021-03-20T01:46:47.040Z
Robin Kothari
<p>Copied from my answer to the same question at qc.se:</p>
<hr />
<p>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
<span class="math-container">$$
H=\sum h_i
$$</span>
with <span class="math-container">$k$</span>-local terms <span class="math-container">$h_i$</span> is chosen such that <span class="math-container">$\|h_i\|\le1$</span> (with <span class="math-container">$\|\cdot\|$</span> the operator norm). Otherwise, any statement about the difficulty of the problem would be vacuous, as you could just rescale the Hamiltonian <span class="math-container">$H\to cH$</span> with some constant <span class="math-container">$c&gt;0$</span>, just as your &quot;repeat each term <span class="math-container">$x$</span> times&quot; argument does.</p>
<p>(Overall, one has to be more careful since it depends where the terms act and you can re-group terms, but if <span class="math-container">$k$</span> 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.)</p>

CC BY-SA 4.0
2021-03-20T12:57:19.600Z
2021-03-20T12:57:19.600Z
Norbert Schuch
<p>In the <a href="https://arxiv.org/pdf/1309.7495.pdf" rel="nofollow noreferrer">standard survey</a> LH is defined with normalization 1 on the single terms <span class="math-container">$h_{i}$</span>. The actual promised gap <span class="math-container">$b-a$</span> for the least eigenvalue of the total hamiltonian <span class="math-container">$H=\sum_{i}^{m}h_{i}$</span> is referred to as the &quot;absolute promise gap&quot;, and <span class="math-container">$(b-a)/m$</span> is referred to as the &quot;relative promise gap&quot; or simply the promise gap. The &quot;Quantum PCP by gap amplification&quot; conjecture states that LH is QMA-hard with constant relative promise gap.<br />
So the answer is the OP (myself) didn't read the quantum PCP statement correctly.</p>

CC BY-SA 4.0
2021-03-22T17:54:41.603Z
2021-03-22T17:54:41.603Z
J.Ask
<p>Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum <span class="math-container">$H$</span> of local hamiltonians, such that the least eigenvalue of <span class="math-container">$H$</span> is either <span class="math-container">$\leq a$</span> or <span class="math-container">$\geq b$</span>, with <span class="math-container">$b-a$</span> 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.</p>
<p>I read often, for example in <a href="https://en.wikipedia.org/wiki/PCP_theorem#Quantum_analog_of_the_PCP_theorem" rel="nofollow noreferrer">wikipedia</a>, that for constant gap QMA-hardness is a <em>conjecture</em> (equivalent to a quantum version of the PCP theorem). However, I sometimes read the opposite: for example <a href="https://arxiv.org/pdf/1301.2632.pdf" rel="nofollow noreferrer">Gharibian's phd thesis</a> problem 1.7, or <a href="https://arxiv.org/pdf/1302.0290.pdf" rel="nofollow noreferrer">Gosset, Nagaj</a> definition 4 for the qsat subcase.</p>
<p>Effectively, I don't understand why I cannot repeat each term in <span class="math-container">$H$</span> 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 &quot;constant gap&quot; is just a fast way to say something more specific?</p>
<p>PS. I posted this on the <a href="https://quantumcomputing.stackexchange.com/questions/16589/the-complexity-of-lh-with-constant-gap">quantum computing</a> board too, where is probably more inherent. I noted the board after posting here, let me know if I have to cancel this.</p>

CC BY-SA 4.0
2021-03-20T07:16:40.777Z
Please [do not post the same question simultaneously on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
CC BY-SA 4.0
2021-03-20T12:51:28.003Z
Thanks, I didn't know of the other board. Now i think it's better to leave both of them, or aggregate the answers
J.Ask
<cc.complexity-theory><quantum-computing><qma>
The complexity of LH with constant gap
J.Ask
# The complexity of LH with constant gap

(Asked by: username_0 on 2021-03-19)

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](https://en.wikipedia.org/wiki/PCP_theorem#Quantum_analog_of_the_PCP_theorem), 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](https://arxiv.org/pdf/1301.2632.pdf) problem 1.7, or [Gosset, Nagaj](https://arxiv.org/pdf/1302.0290.pdf) 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](https://quantumcomputing.stackexchange.com/questions/16589/the-complexity-of-lh-with-constant-gap) board too, where is probably more inherent. I noted the board after posting here, let me know if I have to cancel this.

**Tags:** cc.complexity-theory, quantum-computing, qma

> **Comments:**
> **username_1**: Please [do not post the same question simultaneously on multiple sites](https://meta.stackexchange.com/q/64068).  
> **username_0**: Thanks, I didn't know of the other board. Now i think it's better to leave both of them, or aggregate the answers  

---

## 3 answers

### Answer by username_2 on 2021-03-20. Score: 3

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.

> **Comments:**
> **username_0**: 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  
> **username_3**: $\|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).  
> **username_2**: @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?  
> **username_2**: @username_0: 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.  
> **username_0**: @RobinKothari In the standard survey [link](https://arxiv.org/pdf/quant-ph/0210077.pdf) as well as in original Kitaev's book [link](https://www.ams.org/books/gsm/047/gsm047-endmatter.pdf) the normalization is like that. The total hamiltonian is then "normalized" to $m$. And the gap can be constant. As a newbie of the argument I was taking the word "constant" in the QPCP statement literally, and I wanted to make sure with this question. But it seems by the answers that there is indeed some confusion with the different conventions  
> **username_3**: @RobinKothari I don't know. It depends whether they are talking about Quantum PCP or not. From a more physics-motivated point of view, it seems very relevant whether a constant gap for a system where each term is normalized is hard: This is in between a 1/poly(n) gap and the QPCP gap, which does not make sense for systems with spatially local interactions. So both questions are interesting! It is just that I would describe QPCP as "constant fraction of total energy/total $\|H\|$.)  
> **username_3**: Note that also from a non-physics point (where you don't care about spatial locality of the interaction) it is natural to normalize the Hamiltonian this way: Hamiltonians are, pretty much by definition, sums of individual terms (whether spatially local or k-local, or something else), and these local terms are the fundamental constitutents. Normalizing the fundamental constituents certainly seems the most natural thing to do.  
> **username_3**: @username_0 I don't think anyone is confused as to what QPCP means.  
> **username_2**: @username_0 This paper by Aharonov et al (https://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.  

---

### Answer by username_3 on 2021-03-20. Score: 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 by username_0 on 2021-03-22. Score: 0

In the [standard survey](https://arxiv.org/pdf/1309.7495.pdf) 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.


---

