Why is it impossible to solve a QMA-hard problem by cooling?

Question

The complexity class $QMA$ is the quantum complexity analogue of the complexity class NP. See https://en.wikipedia.org/wiki/QMA.

One of the main results about $QMA$ is that the problem "2-local Hamiltonian" is QMA-hard (and therefore NP-hard). (See the introduction of https://arxiv.org/abs/quant-ph/0504050).

On the other hand, I imagine that one could just build the Hamiltonian and cool it down to solve any instance of the problem.

Why doesn't this work?

Background information: A 2-local Hamiltonian $H$ is an operator on the Hilbert space $(\mathbb{C}^2)^{\otimes n}$ which is of the form $H = \sum_j H_j$ where each $H_j$ acts non-trivially on at most $2$ qubits.

Let in the following $\lambda(H)$ denote the smallest eigenvalue of $H$.

The problem "2-local Hamiltonian" is defined by given a 2 local Hamiltonian on $n$ qubits and two real numbers $\alpha, \beta$ such that $ \beta -\alpha \geq \frac{1}{poly(n)}$ and a promise that either $\lambda(H) \leq \alpha$ or $\lambda(H) \geq \beta$ then determine which of the two cases you are in.

Answer 1

I imagine that one could just build the Hamiltonian and cool it down to solve any instance of the problem.

The word "just" is doing a lot of heavy lifting here. Leaving aside the practicalities of engineering a clean realisation of a given many-body Hamiltonian (which is generally extremely difficult), cooling down to the ground state is cooling to zero temperature, i.e. $T=0$. This would violate the third law of thermodynamics.

While the third law has sometimes been regarded as more heuristic than its two ironclad siblings, recent years have seen significant progress in establishing the third law of thermodynamics as a rigorous result under clearly defined conditions. As shown here and here, one needs either a diverging time or some other unbounded resource to reach $T=0$.

Answer 2

For the exact same reason why it's hard to solve NP-hard problems by cooling a classical system.

While it's very difficult to prove anything rigorously, it is strongly believed that if you were to perform your experiment, then the system would indeed eventually settle into the ground state and therefore solve the problem - but it would take an exponentially long time (typically many times longer than the age of the universe) to do so.

That's because the underlying microscopic physics that controls the dynamical equilibration process is presumably local and effectively uncorrelated over macroscopic distances. So (with high probability) it almost always makes local moves, and so is liable to get stuck in metastable local (but not global) minima of the energy landscape for very long times.

So your proposed procedure will indeed solve the problem - but not efficiently.