Scott Aaronson (MIT)
Black Holes, Firewalls, and the Complexity of States and Unitaries
QuICS Workshop on the Frontiers of Quantum Information and Computer Science (September 30, 2015)
I will discuss some recent results, motivated by the black-hole firewall paradox and the AdS/CFT correspondence, about the quantum circuit complexity of preparing certain entangled states and implementing certain unitary transformations.
One result is a strengthening of an argument by Harlow and Hayden. I will show that, under plausible assumptions, “decoding” useful information from Hawking radiation, as called for by the AMPS “firewall” thought experiment, requires the computational power to invert arbitrary cryptographic one-way functions, something we think not even quantum computers could do in sub-astronomical time.
A second result, joint with Lenny Susskind of Stanford University, considers the circuit complexity of the kinds of states that could arise in AdS/CFT and shows that, under a reasonable conjecture about complexity classes (PSPACE is not in PP/poly), the complexity indeed becomes superpolynomially large, as predicted by a conjectured relationship between complexity and geometry.
I will also discuss more general problems about the complexities of states and unitary transformations, which I find fascinating even apart from the quantum-gravity motivation.