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?


3 Answers 3


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


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


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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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