Quantum Hamiltonian Complexity

We survey the growing field of Quantum Hamiltonian Complexity, which includes the study of Quantum Constraint Satisfaction. In particular, our aim is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this paper: (1) The basic ideas, motivations, and history of the field, (2) a glossary of many-body physics terms explained in computer-science friendly language, (3) overviews of central ideas from many-body physics, such as Mean Field Theory and Tensor Networks, and (4) brief expositions of selected computer science-based results in the area. This paper is based largely on the discussions of the quantum reading group at UC Berkeley in Spring 2013. “Computers are physical objects, and computations are physical processes. What computers can or cannot compute is determined by the laws of physics alone... ” — David Deutsch