What is the computational complexity of simulating a given Hamiltonian? What is the computational complexity of finding its ground state?

These questions are fundamental to condensed matter physics, to computational complexity but also have deep practical merit. Ground state quantum computation (e.g. adiabatic quantum computation) utilize properties of the ground states of Hamiltonians to compute.

Adiabatic quantum computing generally relies on the idea of embedding a problem instance into a physical system, such that the systems lowest energy configuration stores the problem instance solution. […]