Dorit Aharonov (Hebrew University of Jerusalem)

The title of this talk is the name of a program being hosted this semester at the Simons Institute for the Theory of Computing. It is also the name of an exciting and rapidly growing subarea of quantum information science, which focuses on the interplay between condensed matter physics and the theory of computation. The starting point of this area is the curious fact that a central problem in theoretical computer science, called the "constraint satisfaction problem," is a special case of a central problem in condensed matter physics, namely, finding ground states of local Hamiltonians. This intriguing link suggests a computational lens on many-body quantum physics, a viewpoint which has already led to a rich set of new questions and insights. In my talk I will survey some ideas related to the main questions underlying this exciting direction:

- Can states of "natural" quantum systems be described succinctly?
- Does the exponential complexity of general quantum systems persist at high temperature?
- Is the scientific method sufficiently powerful to test and understand general quantum systems?

No prior knowledge of quantum mechanics or quantum computation will be assumed.

Light refreshments will be served before the lecture at 3:30 p.m.