Scott Aaronson: Black Holes, Firewalls, and the Complexity of States and Unitaries

Channel:

QuICS

Subscribers:

2,470

Published on October 6, 2015 5:11:07 PM ● Video Link: https://www.youtube.com/watch?v=zJdTtL3ajaI

Duration: 50:35

3,410 views

53

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.