Constraints on physical computers in holographic spacetimes

Abstract

Within the setting of the AdS/CFT correspondence, we ask about the power of computers in the presence of gravity. We show that there are computations on $n$ qubits which cannot be implemented inside of black holes with entropy less than $O(2^n)$. To establish our claim, we argue computations happening inside the black hole must be implementable in a programmable quantum processor, so long as the inputs and description of the unitary to be run are not too large. We then prove a bound on quantum processors which shows many unitaries cannot be implemented inside the black hole, and further show some of these have short descriptions and act on small systems. These unitaries with short descriptions must be computationally forbidden from happening inside the black hole.

References in corpus (19)

• Strengths and Weaknesses of Quantum Computing
• The maximum speed of dynamical evolution
• A Covariant Entropy Conjecture
• Quantum Extremal Surfaces: Holographic Entanglement Entropy beyond the Classical Regime
• Programmable quantum gate arrays
• Proof of Classical Versions of the Bousso Entropy Bound and of the Generalized Second Law
• Asymptotic teleportation scheme as a universal programmable quantum processor
• Entanglement Wedge Reconstruction via Universal Recovery Channels
• Proof of a Quantum Bousso Bound
• Learning the Alpha-bits of Black Holes
• Leading order corrections to the quantum extremal surface prescription
• Large Breakdowns of Entanglement Wedge Reconstruction
• Fast quantum computation at arbitrarily low energy
• Holographic scattering requires a connected entanglement wedge
• Complexity and entanglement in non-local computation and holography
• The black hole interior from non-isometric codes and complexity
• Resource Quantification for the No-Programming Theorem
• Quantum tasks in holography
• Holography as a resource for non-local quantum computation