Abstract
The AdS/CFT correspondence is central to efforts to reconcile gravity and quantum mechanics. It posits a duality between a quantum gravity theory and a quantum mechanical theory, embodied in a map known as the "dictionary" which is a homomorphism between the theories. This dictionary map is not well understood and has only been computed on special, structured instances. In this talk we introduce cryptographic ideas to the study of AdS/CFT, and provide evidence that either the dictionary must be exponentially hard to compute, or else the quantum Extended Church-Turing thesis must be false in quantum gravity. The basic argument is that Susskind's "wormhole growth paradox" requires the dictionary to map a quantity which is hard to compute -- essentially the circuit complexity of the dual quantum state -- to something which is easy to compute in the quantum gravity theory. Therefore the dictionary itself must be hard to compute. Our argument requires creating a custom quantum pseudorandomness construction inspired by block ciphers such as the AES and DES cryptosystems. No background in quantum gravity will be assumed. Based on joint work with Bill Fefferman and Umesh Vazirani.