The AdS/CFT correspondence conjectures a duality between a theory of quantum gravity in Anti de Sitter space and a conformal field theory.  Susskind identified an interesting paradox in this correspondence: namely some aspects of the behavior of eternal black holes, which partition space-time into two distinct regions connected by a “wormhole”, do not have an obvious CFT analogue. The conundrum is that the volume of the wormhole grows for a very long time, whereas in the dual space the CFT dynamics of most black hole systems are conjectured to be “scrambling” --- the expectation values of local operators saturate very quickly to their equilibrium values. What quantity in the CFT could possibly then be dual to the wormhole volume? Susskind conjectured that the dual quantity is the circuit complexity of the CFT state, which continues to increase even after the system  equilibriates.

But Susskind's conjecture raises its own issues --- we show that for the kinds of quantum states in the CFT, their quantum circuit complexity is exponentially hard to approximate, whereas in the dual AdS space, the wormhole volume can be efficiently approximated. Or to put it in other words, the circuit complexity of the CFT states is not “feelable”, that is, it is not a quantity which can be observed with polynomial-time quantum experiments, in contrast to wormhole volume. One consequence is that the dictionary map which exhibits the AdS/CFT correspondence must itself be exponentially hard to compute. Formally, a key part of this argument appeals to a fundamental notion from cryptography known as computational pseudorandomness, where ensembles of states of low circuit complexity can masquerade as high complexity states to any casual observer.

The talk will be self contained and will include an introduction to the basic notions of computational pseudorandomness.

Based on joint work with Adam Bouland and Bill Fefferman.