2023/04/19 by Aleksander M. Kubicki, Alex May, David Pérez-Garcia +1 · 1 voice · 1 citation
Physics and Astronomy · #Black Holes and Theoretical Physics #Noncommutative and Quantum Gravity Theories #Cosmology and Gravitation Theories
paper · pdf · doi:10.21468/scipostphys.16.1.024
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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mi>n</mml:mi> </mml:math> qubits which cannot be implemented inside of black holes with entropy less than O(2n) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo stretchy="true" form="prefix">(</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> <mml:mo stretchy="true" form="postfix">)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . 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.