  Quantum Hamiltonian complexity studies computational complexity aspects of
local Hamiltonians and ground states; these questions can be viewed as
generalizations of classical computational complexity problems related to local
constraint satisfaction (such as SAT), with the additional ingredient of
multi-particle entanglement. This additional ingredient of course makes
generalizations of celebrated theorems such as the PCP theorem from classical
to the quantum domain highly non-trivial; it also raises entirely new questions
such as bounds on entanglement and correlations in ground states, and in
particular area laws.
  We propose a simple combinatorial tool that helps to handle such questions:
it is a simplified, yet more general version of the detectability lemma
introduced by us in the more restricted context on quantum gap amplification a
year ago. Here, we argue that this lemma is applicable in much more general
contexts. We use it to provide a simplified and more combinatorial proof of
Hastings' 1D area law, together with a less than 1 page proof of the decay of
correlations in gapped local Hamiltonian systems in any constant dimension. We
explain how the detectability lemma can replace the Lieb-Robinson bound in
various other contexts, and argue that it constitutes a basic tool for the
study of local Hamiltonians and their ground states in relation to various
questions in quantum Hamiltonian complexity.
