3:30 pm Thursday, September 22, 2016
Geometry Seminar: Firewalls, AdS/CFT, and Computational Complexity by Scott Aaronson (UT Austin, Computer Science Department) in RLM 9.166
I'll give a general introduction, aimed at mathematicians and physicists, to the recent connections that have been made between (1) questions in quantum gravity (including the black hole information problem, and finding CFT duals for certain geometric features in AdS space) and (2) my own area, the theory of quantum computation. One such connection, made by Harlow and Hayden in 2013, seeks to address the notorious "firewall paradox" of Almheiri et al., by arguing that processing the Hawking radiation from an old black hole, in a way that would cause a breakdown of spacetime at the event horizon, would require a quantum computation that takes time exponential in the black hole's entropy, vastly exceeding the evaporation time. After reviewing the Harlow-Hayden argument and its computer-science underpinnings, I'll present my own improvement to the argument, which depends only on the existence of "injective one-way functions" that are hard to invert using quantum computers. A second connection, made by Susskind and others over the past few years, proposes 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. Submitted by
|
|