Quantum computation has taught us that, in general, quantum systems are exponentially powerful. This is a double-edged sword: while making quantum computers possible, it is also an enormous obstacle to analyzing and understanding physical systems. Indeed, this is not just an abstract concern; with the major push in condensed matter physics towards studying and creating highly entangled states of matter, the computational complexity of these systems has moved to the fore as a major issue, and this is the main focus of the emerging area of Quantum Hamiltonian Complexity. Here is a list of three basic questions in this area: 1. Can "typical" states of ?naturally occurring? quantum systems be described succinctly (i.e. polynomial rather than exponential in the number of particles)? 2. Does the exponential complexity of general quantum systems persist at high temperature? 3. Is the scientific method sufficiently powerful to be applicable to general quantum systems?
Each of these can be formulated as a precise computational question -- the first is a natural generalization of a question about the complexity class NP, the second about the celebrated PCP theorem and the third about interactive proof systems. Over the last few years the outline of remarkable positive answers to some of these questions has emerged, and there are in place some of the basic techniques necessary to tackle these questions. This project aims to pursue this line of inquiry.
This project is interdisciplinary at the deepest level. It brings a computational lens to bear on some of the most basic issues in condensed matter physics and in the philosophy of science. Conversely, it extends the core concepts of computational complexity theory in important new directions, at the same time drawing on deep insights from physics to make progress on fundamental questions.
