The Complexity of Learning (Pseudo)random Dynamics of Black Holes and Other Chaotic Systems

• URL: http://arxiv.org/abs/2302.11013v2
• Date: Thu, 23 Feb 2023 16:11:09 GMT
• Title: The Complexity of Learning (Pseudo)random Dynamics of Black Holes and Other Chaotic Systems
• Authors: Lisa Yang and Netta Engelhardt
• Abstract summary: We prove that quantum algorithms cannot accurately predict bounded (pseudo)random unitary dynamics. We use the common simplification of modeling black holes and more generally chaotic systems via (pseudo)random dynamics.
• Score: 0.8122270502556374
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Is Planckian discreteness observable in cosmology? [47.03992469282679]
  A Planck scale inflationary era produces the scale invariant spectrum of inhomogeneities with very small tensor-to-scalar ratio of perturbations. Here we evoke the possibility that some of the major puzzles in cosmology would have an explanation rooted in quantum gravity.
  arXiv  Detail & Related papers  (2024-05-21T06:53:37Z)
• Quantum Advantage in Reversing Unknown Unitary Evolutions [9.259390080722206]
  We introduce the Quantum Unitary Reversal Algorithm (QURA), a deterministic and exact approach to universally reverse arbitrary unknown unitary transformations. QURA ensures an exact unitary inversion while the classical counterpart can never achieve exact inversion using a finite number of unitary calls.
  arXiv  Detail & Related papers  (2024-03-07T17:59:11Z)
• Krylov Complexity of Open Quantum Systems: From Hard Spheres to Black Holes [0.0]
  We analytically compute the Krylov complexity of a slowly leaking hard-sphere gas using Berry's conjecture. We then connect it to the holographic complexity of a $d+1$- evaporating black hole using the Complexity=Volume proposal. We model the black hole spacetime by stitching together a sequence of static Schwarzschild patches across incoming negative energy null shock waves.
  arXiv  Detail & Related papers  (2023-08-21T18:00:05Z)
• Constraints on physical computers in holographic spacetimes [49.1574468325115]
  We show that there are computations on $n$ qubits which cannot be implemented inside of black holes with entropy less than $O(2n)$. We argue computations happening inside the black hole must be implementable in a programmable quantum processor.
  arXiv  Detail & Related papers  (2023-04-19T18:00:50Z)
• Temporal Entanglement in Chaotic Quantum Circuits [62.997667081978825]
  The concept of space-evolution (or space-time duality) has emerged as a promising approach for studying quantum dynamics. We show that temporal entanglement always follows a volume law in time. This unexpected structure in the temporal entanglement spectrum might be the key to an efficient computational implementation of the space evolution.
  arXiv  Detail & Related papers  (2023-02-16T18:56:05Z)
• Non-Abelian braiding of graph vertices in a superconducting processor [144.97755321680464]
  Indistinguishability of particles is a fundamental principle of quantum mechanics. braiding of non-Abelian anyons causes rotations in a space of degenerate wavefunctions. We experimentally verify the fusion rules of the anyons and braid them to realize their statistics.
  arXiv  Detail & Related papers  (2022-10-19T02:28:44Z)
• The black hole interior from non-isometric codes and complexity [0.0]
  We show how quantum error correction can be used to explain the emergence of the black hole interior. We show that many previous ideas, such as the existence of a large number of "null states", fit naturally into this framework.
  arXiv  Detail & Related papers  (2022-07-13T22:47:45Z)
• Saturation and recurrence of quantum complexity in random local quantum dynamics [5.803309695504831]
  Quantum complexity is a measure of the minimal number of elementary operations required to prepare a given state or unitary channel. 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.
  arXiv  Detail & Related papers  (2022-05-19T17:42:31Z)
• Universality, intertwiners and black hole information [0.0]
  The central question in this article is how information does leak out from black holes. We propose the existence of certain operators whose correlations extend across the black hole atmosphere and range into the interior. We derive the Page curve and argue that information is transferred to the radiation via black hole intertwiners.
  arXiv  Detail & Related papers  (2020-10-23T17:51:04Z)
• The role of boundary conditions in quantum computations of scattering observables [58.720142291102135]
  Quantum computing may offer the opportunity to simulate strongly-interacting field theories, such as quantum chromodynamics, with physical time evolution. As with present-day calculations, quantum computation strategies still require the restriction to a finite system size. We quantify the volume effects for various $1+1$D Minkowski-signature quantities and show that these can be a significant source of systematic uncertainty.
  arXiv  Detail & Related papers  (2020-07-01T17:43:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.