A bstract 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.
A bstract 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.
We characterize new universal features of the dynamics of chaotic quantum many-body systems, by considering a hypothetical task of “time estimation”. Most macroscopic observables in a chaotic system equilibrate to nearly constant late-time values. Intuitively, it should become increasingly difficult to estimate the precise value of time by making measurements on the state. We use a quantity called the Fisher information from quantum metrology to quantify the minimum uncertainty in estimating time. Due to unitarity, the uncertainty in the time estimate does not grow with time if we have access to optimal measurements on the full system. Restricting the measurements to act on a small subsystem or to have low computational complexity leads to results expected from equilibration, where the time uncertainty becomes large at late times. With optimal measurements on a subsystem larger than half of the system, we regain the ability to estimate the time very precisely, even at late times. Hawking’s calculation for the reduced density matrix of the black hole radiation in semiclassical gravity contradicts our general predictions for unitary quantum chaotic systems. Hawking’s state always has a large uncertainty for attempts to estimate the time using the radiation, whereas our general results imply that the uncertainty should become small after the Page time. This gives a new version of the black hole information loss paradox in terms of the time estimation task. By restricting to simple measurements on the radiation, the time uncertainty becomes large. This indicates from a new perspective that the observations of computationally bounded agents are consistent with the semiclassical effective description of gravity.
Quantum complexity is a measure of the minimal number of elementary operations required to approximately prepare a given state or unitary channel. Recently, this concept has found applications beyond quantum computing—in studying the dynamics of quantum many-body systems and the long-time properties of anti–de Sitter black holes. In this context, Brown and Susskind [] conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly exponential times. In this work, we prove the saturation and recurrence of complexity in two models of chaotic time evolutions based on (i) random local quantum circuits and (ii) stochastic local Hamiltonian evolution. Our results advance an understanding of the long-time behavior of chaotic quantum systems and could shed light on the physics of black-hole interiors. From a technical perspective, our results are based on establishing new quantitative connections between the Haar measure and high-degree approximate designs, as well as the fact that random quantum circuits of sufficiently high depth converge to approximate designs. Published by the American Physical Society 2024
Quantum chaos entails an entropic and computational obstruction to describing a system and thus is intrinsically difficult to characterize. An understanding of quantum chaos is fundamentally related to the mechanism of thermalization in many-body systems and the quantum nature of black holes. In this thesis we adopt the view that quantum information theory provides a powerful framework in which to elucidate chaos in strongly-interacting quantum systems. We first push towards a more precise understanding of chaotic dynamics by relating different diagnostics of chaos, studying the time-evolution of random matrix Hamiltonians, and quantifying random matrix behavior in physical systems. We derive relations between out-of-time ordered correlation functions, spectral quantities, and frame potentials to relate the scrambling of quantum information, decay of correlators, and Haar-randomness. We give analytic expressions for these quantities in random matrix theory to explore universal aspects of late-time dynamics. Motivated by our random matrix results, we define k-invariance in order to capture the onset of random matrix behavior in physical systems. We then refine our diagnostics in order to study chaotic systems with symmetry by considering Haar-randomness with respect to quotients of the unitary group, and in doing so we generalize our quantum information machinery. We further consider extended random matrix ensembles in the context of strongly-interacting quantum systems dual to black holes. Lastly, we study operator growth in classes of random quantum circuits.
We first propose and study a quantum toy model of black hole dynamics. The model is unitary, displays quantum thermalization, and the Hamiltonian couples every oscillator with every other, a feature intended to emulate the color sector physics of large- N matrix models. Considering out of equilibrium initial states, we analytically compute the time evolution of every correlator of the theory and of the entanglement entropies, allowing a proper discussion of global thermalization/scrambling of information through the entire system. Microscopic non-locality causes factorization of reduced density matrices, and entanglement just depends on the time evolution of occupation densities. In the second part of the article, we show how the gained intuition extends to large- N matrix models, where we provide a gauge invariant entanglement entropy for ‘generalized free fields’, again depending solely on the quasinormal frequencies. The results challenge the fast scrambling conjecture and point to a natural scenario for the emergence of the so-called brick wall or stretched horizon. Finally, peculiarities of these models in regards to the thermodynamic limit and the information paradox are highlighted.
The present paper scrutinizes the principle of quantum determinism, which maintains that the complete information about the initial quantum state of a physical system should determine the system's quantum state at any other time. As it shown in the paper, assuming the strong exponential time hypothesis, SETH, which conjectures that known algorithms for solving computational NP-complete problems (often brute-force algorithms) are optimal, the quantum deterministic principle cannot be used generally, i.e., for randomly selected physical systems, particularly macroscopic systems. In other words, even if the initial quantum state of an arbitrary system were precisely known, as long as SETH is true it might be impossible in the real world to predict the system's exact final quantum state. The paper suggests that the breakdown of quantum determinism in a process, in which a black hole forms and then completely evaporates, might actually be physical evidence supporting SETH.
We propose a framework for understanding the information loss paradox in the context of canonical quantum gravity. We first revisit several approaches to black hole evaporation that do not involve an event horizon. In these models, we assume that each time slice corresponds to a coherent state in the gravitational phase space. Due to this property, the quantum state associated with a given spatial configuration will have a nonzero overlap with another spatial configuration. We show how this property can account for both semi-classical dynamics and unitary time evolution. We introduce an explicit toy model that follows semi-classical time evolution at the coarse-grained level; in addition, its time evolution is unitary at the fine-grained level. The only price that one must pay is the violation of the entropy bound; we discuss reasons why this may be justifiable.