# Black Holes and Complexity Classes. (arXiv:1802.02175v1 [hep-th])

It is not known what the limitations are on using quantum computation to

speed up classical computation. An example would be the power to speed up

PSPACE-complete computations. It is also not known what the limitations are on

the duration of time over which classical general relativity can describe the

interior geometry of black holes. What is known is that these two questions are

closely connected: the longer GR can describe black holes, the more limited are

quantum computers. This conclusion, formulated as a theorem, is a result of

unpublished work done by Scott Aaronson and myself which I explain here.

Article web page: