The complexity of learning (pseudo)random dynamics of black holes and other chaotic systems
Open Access
- 20 March 2025
- journal article
- research article
- Published by Springer Nature in Journal of High Energy Physics
- Vol. 2025 (3) , 1-65
Abstract
It has been recently proposed that the naive semiclassical prediction of non-unitary black hole evaporation can be understood in the fundamental description of the black hole as a consequence of ignorance of high-complexity information. Validity of this conjecture implies that any algorithm which is polynomially bounded in computational complexity cannot accurately reconstruct the black hole dynamics. In this work, we prove that such bounded quantum algorithms cannot accurately predict (pseudo)random unitary dynamics, even if they are given access to an arbitrary set of polynomially complex observables under this time evolution; this shows that “learning” a (pseudo)random unitary is computationally hard. We use the common simplification of modeling black holes and more generally chaotic systems via (pseudo)random dynamics. The quantum algorithms that we consider are completely general, and their attempted guess for the time evolution of black holes is likewise unconstrained: it need not be a linear operator, and may be as general as an arbitrary (e.g. decohering) quantum channel.Keywords
All Related Versions
This publication has 65 references indexed in Scilit:
- Cryptographic CensorshipJournal of High Energy Physics, 2025
- Scalable Pseudorandom Quantum States2020
- Pseudorandom Quantum States2018
- Comments on holographic complexityJournal of High Energy Physics, 2017
- Complexity of formation in holographyJournal of High Energy Physics, 2017
- Localized shocksJournal of High Energy Physics, 2015
- Quantum extremal surfaces: holographic entanglement entropy beyond the classical regimeJournal of High Energy Physics, 2015
- Black holes and the butterfly effectJournal of High Energy Physics, 2014
- Quantum Signatures of Chaos1991
- Particle creation by black holesCommunications in Mathematical Physics, 1975