  The quantum-Extended Church-Turing thesis is a principle of physics as well
as computer science. It asserts that the laws of physics will prevent the
construction of a machine that can efficiently determine the results of any
calculation which cannot be done efficiently by a quantum Turing machine (or a
universal quantum circuit). In this note I will argue that an observer falling
into a black hole can learn the result of such a calculation in a very short
time, thereby seemingly violating the thesis. A viable reformulation requires
that the thesis only applies to observers who have access to the holographic
boundary of space. The properties of the horizon play a crucial a role in
protecting the thesis. The arguments are closely related to, and were partially
motivated by a recent paper by Bouland, Fefferman, and Vazirani, and by a
question raised by Aaronson.
