Pseudorandomness and the AdS/CFT Correspondence

Could quantum circuit complexity have physical ramifications? In the context of AdS/CFT, Susskind has suggested that it might, as circuit complexity could be the CFT dual to AdS wormhole volume. Here we explore this proposal using cryptographic techniques. We first show how to create pseudorandom quantum states in the CFT, thereby arguing that their quantum circuit complexity is not "feelable", in the sense that it cannot be approximated by any efficient experiment. By contrast we argue that the wormhole volume is "feelable" in some general but non-physical sense. The duality between a "feelable" quantity and an "unfeelable" quantity implies that some aspect of this duality -- either the AdS/CFT dictionary, or else the dynamics of quantum gravity -- must have exponential complexity. While at first sight this might seem to justify the discomfort of complexity theorists with equating complexity with a physical quantity, a further examination of our arguments shows that these conclusions are an inevitable consequence of the "wormhole growth paradox" which inspired this proposal in the first place. Based largely on https://arxiv.org/abs/1910.14646