5
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ QMA problems are not impossible to solve. Just hard, and slow. Just as cooling can be hard, and slow. $\endgroup$ Oct 11, 2021 at 17:50

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ It is not necessary to go to T=0. $\endgroup$ Oct 11, 2021 at 17:49

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.