<p>You are right, but there is no contradiction. The Local Hamiltonian Problem <em>promises</em> that the spectral gap is large enough. This is by definition, and it may not be satisfying depending on your problem domain. There do exist Hamiltonian operators that violate this promise, and we say, therefore, that finding their ground states is not in QMA. </p>

<p>It's worse, because the (Promise) LH Problem "finds" the state only by receiving it from Merlin. It would not be accurate to say that it constructs a ground state, for reasons below. More accurately, the protocol only verifies whether the state received from Merlin has sufficiently small energy, but <em>it does not verify that the given state is the ground state</em>. Arthur is given numbers <span class="math-container">$a&lt;b$</span> with <span class="math-container">$|b-a|&gt;\frac{1}{poly(n)}$</span> and he is promised that the Hamiltonian has no eigenstates with energy <span class="math-container">$e$</span> in <span class="math-container">$a\leq e\leq b$</span>. However, there may be an exponential number of states below a given energy <span class="math-container">$a$</span>, and an exponential number of states with energies larger than <span class="math-container">$b$</span>. In the context of QMA, the promise is only that <span class="math-container">$|b-a|&gt;\frac{1}{poly(n)}$</span>, but the promise does not specify how many states have lower or higher energy.</p>

<p>At the time of writing, it is unclear whether Hamiltonian ground states (or even any low-energy state) can be constructed using polynomial-size quantum circuits. If so, then the complexity class equality <span class="math-container">$QCMA=QMA$</span> follows (the classical certificate of a QMA problem that Merlin will send is a description of a quantum circuit that produces a ground state from <span class="math-container">$|0&gt;$</span>). This question, of the "descriptive complexity" of ground states, is investigated in [1,5,6].</p>

<p>The question of <em>isolating</em> a single ground state from a Hamiltonian which may have a large number of low-energy states was first considered in [2]. In this context, the challenge is, given a Local Hamiltonian, to produce a new Hamiltonian which has only one low-energy state if the old Hamiltonian had any low-energy states, and otherwise has only high-energy states. The authors of [2] succeed when the witness is classical, but the general case of QMA is unresolved. In [3], the authors succeed when it is promised that the given Hamiltonian has only a small number of low-energy states (i.e. energy below <span class="math-container">$a$</span>)</p>

<p>Perhaps the most difficult open question is to improve the promised spectral gap from inverse polynomial to just a constant. The best promise gap right now, afaik, is still due to Vyalyi's original proof that the Local Hamiltonian is QMA-Complete [4], and delivers a spectral gap of <span class="math-container">$\Omega(\frac{1}{n^2})$</span>. Improving this gap is known as the Quantum PCP Conjecture [5]. The authors of [6] argue that understanding how difficult it is to construct a quantum state may have implications for the Quantum PCP Conjecture.</p>

<p>[1] Aaronson, Scott, and Andrew Drucker. "A full characterization of quantum advice." SIAM Journal on Computing 43.3 (2014): 1131-1183.</p>

<p>[2] Aharonov, Dorit, et al. "The pursuit for uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings." arXiv preprint arXiv:0810.4840 (2008).</p>

<p>[3] Jain, Rahul, et al. "On the power of a unique quantum witness." arXiv preprint arXiv:0906.4425 (2009).</p>

<p>[4] Kitaev, Alexei Yu, et al. Classical and quantum computation. No. 47. American Mathematical Soc., 2002.</p>

<p>[5] Aharonov, Dorit, Itai Arad, and Thomas Vidick. "Guest column: the quantum PCP conjecture." Acm sigact news 44.2 (2013): 47-79.</p>

<p>[6] Grilo, Alex Bredariol, Iordanis Kerenidis, and Jamie Sikora. "QMA with subset state witnesses." International Symposium on Mathematical Foundations of Computer Science. Springer, Berlin, Heidelberg, 2015.</p>

CC BY-SA 4.0
2018-11-16T12:37:26.910Z
2018-11-16T12:37:26.910Z
Lieuwe Vinkhuijzen
<p>There needs to be a gap between the eigenvalue of the groundspace and the first excited state that is inverse-polynomial in the system size, and indeed such a promise is required for the QMA-complete Local Hamiltonian problem. Please refer to the formal definition of the Local Hamiltonian problem and the QMA-completness proof, e.g. Definition 10 and Theorem 1 in <a href="http://arxiv.org/pdf/0808.2117v1.pdf" rel="nofollow">Nagaj's thesis</a>. If the gap is inverse-exponentially small, then the promise is not satisfied by that local Hamiltonian instance and the QMA-completness proof does not apply since a key assumption is not satisfied.</p>

CC BY-SA 3.0
2013-12-27T08:42:59.787Z
2013-12-27T09:26:06.987Z
2013-12-27T09:26:06.987Z
Martin Schwarz
<p>The reason is you are not exactly finding the ground energy, you are finding an <em>approximation</em> of ground energy within some accuracy. So you cannot see it from the definition directly, you need additional property from the reduction (i.e. lower bound of the spectral gap of Hamiltonian in the Kitaev's QMA-hardness proof). </p>

<p>Taking the following definition of <span class="math-container">$k$</span>-local Hamiltonian problem (see Definition 3 in <a href="https://arxiv.org/abs/quant-ph/0406180" rel="nofollow noreferrer">Kempe-Kitaev-Regev's paper</a>): </p>

<blockquote>
  <p>The (promise) problem <span class="math-container">$k$</span>-LOCAL HAMILTONIAN is defined as follows. We
  are given a <span class="math-container">$k$</span>-local Hamiltonian on <span class="math-container">$n$</span>-qubits <span class="math-container">$H=\sum_{j=1}^r H_j$</span>
  with <span class="math-container">$r=poly(n)$</span>. Each <span class="math-container">$H_j$</span> has a bounded operator norm <span class="math-container">$\|H_j\| \leq  poly(n)$</span> and its entries are specified by <span class="math-container">$poly(n)$</span> bits. In addition,
  we are given two constants <span class="math-container">$a$</span> and <span class="math-container">$b$</span> with <span class="math-container">$a &lt; b$</span>. In YES instances,
  the smallest eigenvalue of <span class="math-container">$H$</span> is at most <span class="math-container">$a$</span>. In NO instances, it is
  larger than <span class="math-container">$b$</span>. We should decide which one is the case.</p>
</blockquote>

<p>Assume that the spectral gap of <span class="math-container">$k$</span>-LH is inverse exponential, and the promise gap between <span class="math-container">$a$</span> and <span class="math-container">$b$</span> is inverse polynomial. Then in the YES case, even you have an approximation of ground energy within an inverse polynomial accuracy, it also could be an approximation of energy of excited states within an inverse polynomial accuracy -- it is an approximation of ground states doesn't mean that it <em>cannot</em> be an approximation of other excited states within the same accuracy! </p>

<p>However, I thought the Hamiltonian in the Kitaev's QMA-hardness proof is lowered bound by some inverse polynomial. <a href="http://Bohdanowicz-Crosson-Nirkhe-Yuen" rel="nofollow noreferrer">Bohdanowicz-Crosson-Nirkhe-Yuen's recent paper</a> showed that for any depth <span class="math-container">$D$</span> quantum circuit on n qubits there is an associated spacetime circuit-to-Hamiltonian construction (it is a variant of the construction in the Kitaev's QMA-hardness proof) with spectral gap <span class="math-container">$\Omega(n^{-3.09} D^{-2} \log^{-6}(n))$</span>. Hence, the constructed Hamiltonian is the QMA-hardness cannot have an exponentially small spectral gap. </p>

CC BY-SA 4.0
2018-11-16T08:30:29.673Z
2018-11-16T08:30:29.673Z
Yupan Liu
<p>Why is finding the ground stte of a Hamiltonian in QMA?</p>

<p>It's in QMA to figure out if a hamiltonian has any energy eigenvalue within a certain window range which is at least inverse polynomial in size. But what if the energy gap for the ground state is inverse exponentially small? Then why is specifying the ground state in QMA? It takes an exponential time to measure energy up to inverse exponential accuracy, right? So, Arthur needs more than polynomial time to verify, right?</p>

<quantum-computing>
Why is finding the ground state of a Hamiltonian in QMA?
James
# Why is finding the ground state of a Hamiltonian in QMA?

(Asked by: username_0 on 2013-12-26)

Why is finding the ground stte of a Hamiltonian in QMA?

It's in QMA to figure out if a hamiltonian has any energy eigenvalue within a certain window range which is at least inverse polynomial in size. But what if the energy gap for the ground state is inverse exponentially small? Then why is specifying the ground state in QMA? It takes an exponential time to measure energy up to inverse exponential accuracy, right? So, Arthur needs more than polynomial time to verify, right?

**Tags:** quantum-computing


---

## 3 answers

### Answer by username_1 on 2018-11-16. Score: 4

You are right, but there is no contradiction. The Local Hamiltonian Problem *promises* that the spectral gap is large enough. This is by definition, and it may not be satisfying depending on your problem domain. There do exist Hamiltonian operators that violate this promise, and we say, therefore, that finding their ground states is not in QMA.

It's worse, because the (Promise) LH Problem "finds" the state only by receiving it from Merlin. It would not be accurate to say that it constructs a ground state, for reasons below. More accurately, the protocol only verifies whether the state received from Merlin has sufficiently small energy, but *it does not verify that the given state is the ground state*. Arthur is given numbers $a with $|b-a|>\frac{1}{poly(n)}$ and he is promised that the Hamiltonian has no eigenstates with energy $e$ in $a\leq e\leq b$. However, there may be an exponential number of states below a given energy $a$, and an exponential number of states with energies larger than $b$. In the context of QMA, the promise is only that $|b-a|>\frac{1}{poly(n)}$, but the promise does not specify how many states have lower or higher energy.

At the time of writing, it is unclear whether Hamiltonian ground states (or even any low-energy state) can be constructed using polynomial-size quantum circuits. If so, then the complexity class equality $QCMA=QMA$ follows (the classical certificate of a QMA problem that Merlin will send is a description of a quantum circuit that produces a ground state from $|0>$). This question, of the "descriptive complexity" of ground states, is investigated in [1,5,6].

The question of *isolating* a single ground state from a Hamiltonian which may have a large number of low-energy states was first considered in [2]. In this context, the challenge is, given a Local Hamiltonian, to produce a new Hamiltonian which has only one low-energy state if the old Hamiltonian had any low-energy states, and otherwise has only high-energy states. The authors of [2] succeed when the witness is classical, but the general case of QMA is unresolved. In [3], the authors succeed when it is promised that the given Hamiltonian has only a small number of low-energy states (i.e. energy below $a$)

Perhaps the most difficult open question is to improve the promised spectral gap from inverse polynomial to just a constant. The best promise gap right now, afaik, is still due to Vyalyi's original proof that the Local Hamiltonian is QMA-Complete [4], and delivers a spectral gap of $\Omega(\frac{1}{n^2})$. Improving this gap is known as the Quantum PCP Conjecture [5]. The authors of [6] argue that understanding how difficult it is to construct a quantum state may have implications for the Quantum PCP Conjecture.

[1] Aaronson, Scott, and Andrew Drucker. "A full characterization of quantum advice." SIAM Journal on Computing 43.3 (2014): 1131-1183.

[2] Aharonov, Dorit, et al. "The pursuit for uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings." arXiv preprint arXiv:0810.4840 (2008).

[3] Jain, Rahul, et al. "On the power of a unique quantum witness." arXiv preprint arXiv:0906.4425 (2009).

[4] Kitaev, Alexei Yu, et al. Classical and quantum computation. No. 47. American Mathematical Soc., 2002.

[5] Aharonov, Dorit, Itai Arad, and Thomas Vidick. "Guest column: the quantum PCP conjecture." Acm sigact news 44.2 (2013): 47-79.

[6] Grilo, Alex Bredariol, Iordanis Kerenidis, and Jamie Sikora. "QMA with subset state witnesses." International Symposium on Mathematical Foundations of Computer Science. Springer, Berlin, Heidelberg, 2015.


---

### Answer by username_2 on 2013-12-27. Score: 4

There needs to be a gap between the eigenvalue of the groundspace and the first excited state that is inverse-polynomial in the system size, and indeed such a promise is required for the QMA-complete Local Hamiltonian problem. Please refer to the formal definition of the Local Hamiltonian problem and the QMA-completness proof, e.g. Definition 10 and Theorem 1 in [Nagaj's thesis](http://arxiv.org/pdf/0808.2117v1.pdf). If the gap is inverse-exponentially small, then the promise is not satisfied by that local Hamiltonian instance and the QMA-completness proof does not apply since a key assumption is not satisfied.


---

### Answer by username_3 on 2018-11-16. Score: 2

The reason is you are not exactly finding the ground energy, you are finding an *approximation* of ground energy within some accuracy. So you cannot see it from the definition directly, you need additional property from the reduction (i.e. lower bound of the spectral gap of Hamiltonian in the Kitaev's QMA-hardness proof).

Taking the following definition of $k$-local Hamiltonian problem (see Definition 3 in [Kempe-Kitaev-Regev's paper](https://arxiv.org/abs/quant-ph/0406180)):

> The (promise) problem $k$-LOCAL HAMILTONIAN is defined as follows. We
> are given a $k$-local Hamiltonian on $n$-qubits $H=\sum\_{j=1}^r H\_j$
> with $r=poly(n)$. Each $H\_j$ has a bounded operator norm $\|H\_j\| \leq poly(n)$ and its entries are specified by $poly(n)$ bits. In addition,
> we are given two constants $a$ and $b$ with $a < b$. In YES instances,
> the smallest eigenvalue of $H$ is at most $a$. In NO instances, it is
> larger than $b$. We should decide which one is the case.

Assume that the spectral gap of $k$-LH is inverse exponential, and the promise gap between $a$ and $b$ is inverse polynomial. Then in the YES case, even you have an approximation of ground energy within an inverse polynomial accuracy, it also could be an approximation of energy of excited states within an inverse polynomial accuracy -- it is an approximation of ground states doesn't mean that it *cannot* be an approximation of other excited states within the same accuracy!

However, I thought the Hamiltonian in the Kitaev's QMA-hardness proof is lowered bound by some inverse polynomial. [Bohdanowicz-Crosson-Nirkhe-Yuen's recent paper](http://Bohdanowicz-Crosson-Nirkhe-Yuen) showed that for any depth $D$ quantum circuit on n qubits there is an associated spacetime circuit-to-Hamiltonian construction (it is a variant of the construction in the Kitaev's QMA-hardness proof) with spectral gap $\Omega(n^{-3.09} D^{-2} \log^{-6}(n))$. Hence, the constructed Hamiltonian is the QMA-hardness cannot have an exponentially small spectral gap.


---

