Leonard Susskind (Stanford University)
simons.berkeley.edu/talks/leo...
Quantum Complexity: Quantum PCP, Area Laws, and Quantum Gravity
Computational complexity is a very deep mathematical and logical concept that can give objective meaning to questions as varied as: How difficult is a theorem (some theorems are clearly more difficult than others); to how long a time does it take to produce a given quantum state of a quantum computer. But it has never till now been thought of as a physical property of a system. It was a great surprise that it found its way into black hole physics as a geometric property of black holes---the geometric size of their interiors. The introduction of complexity has greatly clarified the meaning of the black hole horizon. For example we now know that in many cases it is wrong to say that things cannot escape from behind the horizon; it is merely very complex. The horizon is also a censor that forbids an observer outside the black hole from witnessing violations of a profound physical principle: the so-called "quantum extended Church Turing Thesis." I'll try my best to explain these things.