Theory Group Seminar

Dr. Scott Aaronson, UT-Austin Computer Science

"AdS/CFT and Computational Complexity"

2:00pm, RLM 7.104

Abstract: This talk will explore recent connections between computational complexity and the AdS/CFT correspondence. It's meant as a continuation of the speaker's Geometry Seminar on the black-hole firewall problem, though the two talks stand independently and neither is a prerequisite for the other.

A few years ago, Susskind and others proposed that, within the context of the AdS/CFT correspondence, the CFT dual of certain geometric features -- such as the volume of an expanding wormhole -- is the quantum circuit complexity of the CFT state (that is, the minimum number of elementary unitary transformations needed to prepare the state from some simple initial state). I'll present a recent joint result of myself and Susskind, which shows that, assuming standard hypotheses in theoretical computer science (for example: "PSPACE is not in PP/poly"), the circuit complexity of the CFT state indeed behaves as it would need to for this striking proposal to work. I'll explain some requisite background in classical and quantum computing theory during the talk.