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: