Quantum Computation vs. Firewalls

In this paper we discuss quantum computational restrictions on the types of thought experiments recently used by Almheiri, Marolf, Polchinski, and Sully to argue against the smoothness of black hole horizons. We argue that the quantum computations required to do these experiments take a time which is exponential in the entropy of the black hole under study, and we show that for a wide variety of black holes this prevents the experiments from being done. We interpret our results as motivating a broader type of non-locality than is usually considered in the context of black hole thought experiments, and claim that once this type of non-locality is allowed there is no need for firewalls. Our results do not threaten the unitarity of of black hole evaporation or the ability of advanced civilizations to test it.