Скачать с ютуб Scott Aaronson: Black Holes, Firewalls, and the Complexity of States and Unitaries в хорошем качестве

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

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.