Black Holes and Complexity Classes

Abstract

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.

13 pages, 3 figures

References in corpus (1)

• Complexity and Shock Wave Geometries

Cited by in corpus (9)

• Linear growth of quantum circuit complexity
• Models of quantum complexity growth
• Aspects of The First Law of Complexity
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• The Generalized OTOC from Supersymmetric Quantum Mechanics: Study of Random Fluctuations from Eigenstate Representation of Correlation Functions
• Holographic Subregion Complexity in Einstein-Born-Infeld theory
• Complexity growth of rotating black holes with a probe string
• The arithmetic geometry of AdS${}_2$ and its continuum limit
• Switchback effect of holographic complexity in multiple-horizon black holes