### Summary Constraints on physical computers in holographic spacetimes arxiv.org

13,686 words - PDF document - View PDF document

### One Line

The study introduces the covariant entropy bound (CEB) and suggests that larger black holes may allow for state-independent recovery of computations.

### Slides

### Slide Presentation (12 slides)

### Key Points

- The study investigates the power of computers in holographic spacetimes, specifically inside black holes.
- The authors show that there are computations on n qubits that cannot be implemented inside black holes with entropy less than O(2^n).
- The study establishes constraints on physical computers by proving that certain unitaries with short descriptions cannot be implemented inside black holes.
- The authors discuss complexity theory and propose studying the full set of constraints on physical computers within the context of quantum gravity.
- The study provides insights into the limitations of computations inside black holes and explores the connection between models of computation and physical computers in the presence of gravitational constraints.

### Summaries

### 22 word summary

The study explores constraints on computations inside black holes, proposing the covariant entropy bound (CEB) and larger black holes for state-independent recovery.

### 58 word summary

This study examines the limitations of computations inside black holes. The authors introduce the covariant entropy bound (CEB) as a constraint on the size of the computer. They propose using a larger black hole to allow for state-independent recovery. The authors also discuss the relationship between models of computation and physical computers in the context of gravitational constraints.

### 409 word summary

The study examines the limitations of computations inside black holes and explores why certain unitaries cannot be implemented in these spacetimes. The size of the computer, represented by nP, should be physically constrained rather than chosen. The authors introduce the covariant entropy bound (CEB) as a constraint on nP based on the black hole horizon. However, they find that at the upper limit of the CEB, state-independent recovery is violated. To address this, they propose using a larger black hole to allow for state-independent recovery.

The size of the inputs, represented by nA, can be much smaller than the black hole entropy. The authors derive an inequality that ensures state-independent recovery and applies to the average success probability of the diagonal unitary game run inside a black hole. They define a set of forbidden unitaries based on a threshold probability and argue that these unitaries cannot be implemented inside the black hole due to information theoretic constraints.

The authors discuss the relationship between models of computation and physical computers in the context of gravitational constraints. They acknowledge previous work on the connection between energy limits and computation speed but note the challenge of obtaining a precise bound on computation from a direct gravity perspective.

In their holographic thought experiment, Alice prepares a randomly drawn string while Bob prepares a state on the A system. The authors contend that certain computations are computationally forbidden inside a black hole and suggest that the complexity of these computations may explain their prohibition.

The authors mention the complexity of the AdS/CFT dictionary, which relates to recovering bulk data from the boundary. They clarify that their argument does not depend on this complexity but rather on its state independence within a subspace of states.

Finally, the authors discuss the optimality of a naive algorithm for decompressing the description of a forbidden unitary. They argue that this algorithm provides a lower bound on the number of computational steps required and explain that any improvement in memory usage would also require an improvement in computational steps.

Overall, this study provides insights into the constraints on physical computers in holographic spacetimes, particularly within black holes. The authors highlight the limitations of these computations and offer explanations for the prohibition of certain unitaries. They also explore the relationship between models of computation and physical computers in the presence of gravitational constraints. The findings have implications for understanding the computational power in quantum gravity and may have broader applications.

### 419 word summary

The study "Constraints on physical computers in holographic spacetimes" examines the limitations of computations inside black holes and explores why certain unitaries cannot be implemented in these spacetimes. The authors argue that the size of the computer, represented by nP, should be physically constrained rather than chosen. They introduce the covariant entropy bound (CEB) as a constraint on nP based on the black hole horizon. However, they find that at the upper limit of the CEB, state-independent recovery is violated. To address this, they propose using a larger black hole to allow for state-independent recovery.

The size of the inputs, represented by nA, can be much smaller than the black hole entropy. The authors derive an inequality that ensures state-independent recovery and applies to the average success probability of the diagonal unitary game run inside a black hole. They define a set of forbidden unitaries based on a threshold probability and argue that these unitaries cannot be implemented inside the black hole due to information theoretic constraints.

The authors discuss the relationship between models of computation and physical computers in the context of gravitational constraints. They acknowledge previous work on the connection between energy limits and computation speed but note the challenge of obtaining a precise bound on computation from a direct gravity perspective.

In their holographic thought experiment, Alice prepares a randomly drawn string while Bob prepares a state on the A system. The authors contend that certain computations are computationally forbidden inside a black hole and suggest that the complexity of these computations may explain their prohibition.

The authors mention the complexity of the AdS/CFT dictionary, which relates to recovering bulk data from the boundary. They clarify that their argument does not depend on this complexity but rather on its state independence within a subspace of states.

Finally, the authors discuss the optimality of a naive algorithm for decompressing the description of a forbidden unitary. They argue that this algorithm provides a lower bound on the number of computational steps required and explain that any improvement in memory usage would also require an improvement in computational steps.

Overall, this study provides insights into the constraints on physical computers in holographic spacetimes, particularly within black holes. The authors highlight the limitations of these computations and offer explanations for the prohibition of certain unitaries. They also explore the relationship between models of computation and physical computers in the presence of gravitational constraints. The findings have implications for understanding the computational power in quantum gravity and may have broader applications.

### 443 word summary

The study "Constraints on physical computers in holographic spacetimes" explores the limitations of computations inside black holes and investigates why certain unitaries are forbidden from being implemented in these spacetimes. The authors argue that the size of the computer, represented by nP, should be physically constrained rather than a choice. They introduce the covariant entropy bound (CEB) as a constraint on nP related to the black hole horizon. However, they find that at the upper limit of the CEB, they violate state-independent recovery. To address this, they introduce an assumption that allows for state-independent recovery using a larger black hole.

The value of nA, representing the size of the inputs, can be chosen to be much smaller than the black hole entropy. The authors derive an inequality that ensures state-independent recovery and applies to the average success probability of the diagonal unitary game run inside a black hole. They define a set of forbidden unitaries based on a threshold probability and argue that these unitaries cannot be implemented inside the black hole due to information theoretic constraints.

The authors discuss the connection between models of computation and physical computers in the context of gravitational constraints. They highlight previous work on the relationship between energy limits and computation speed but acknowledge the difficulty of obtaining a precise bound on computation from a direct gravity perspective.

In their holographic thought experiment, Alice prepares a randomly drawn string and Bob prepares a state on the A system. The authors argue that certain computations are computationally forbidden inside a black hole. They suggest that the complexity of these forbidden computations may explain why they are forbidden.

The authors mention the complexity of the AdS/CFT dictionary, which relates to the recovery of bulk data from the boundary. They clarify that their argument does not rely on the complexity of this map but rather on its state independence within a subspace of states.

Finally, the authors discuss the optimality of a naive algorithm for decompressing the description of a forbidden unitary. They argue that this algorithm provides a lower bound on the number of computational steps needed and explain that any improvement in memory usage would also require an improvement in computational steps.

Overall, this study provides insights into the constraints on physical computers in holographic spacetimes, particularly in the context of computations inside black holes. The authors highlight the limitations of these computations and offer explanations for why certain unitaries are forbidden. They also discuss the connection between models of computation and physical computers in the presence of gravitational constraints. The findings have implications for understanding the power of computers in quantum gravity and may have broader applications.

### 1167 word summary

In the study "Constraints on physical computers in holographic spacetimes," the authors investigate the power of computers in the presence of gravity within the framework of the AdS/CFT correspondence. They show that there are computations on n qubits that cannot be implemented inside black holes with entropy less than O(2^n). To establish this claim, they argue that computations happening inside a black hole must be implementable in a programmable quantum processor, as long as the inputs and description of the unitary to be run are not too large. They then prove a bound on quantum processors that shows many unitaries cannot be implemented inside the black hole, and further show that some of these unitaries have short descriptions and act on small systems. These unitaries with short descriptions must be computationally forbidden from happening inside the black hole.

The authors begin by discussing complexity theory, which deals with the power of mathematical models of computation. They note that while these models capture the computational abilities of physical computers, making the connection precise is difficult. They propose studying the full set of constraints on physical computers and the full physical setting that can be exploited by a computer within the context of quantum gravity.

The main result of the study is the construction of a family of unitaries that a computer operating inside a black hole with entropy S_bh cannot perform, where the computation is on n qubits with log S_bh ≤ n ≤ S_bh and the family size is 2^(o(S_bh)). The inputs to the computation do not couple strongly to gravity, but it is the computation on these small inputs that is restricted. The authors argue that working within the context of the AdS/CFT correspondence provides a precise framework for studying quantum gravity and may yield insights that apply more broadly.

They also discuss the notion of programmable processors in quantum information theory and provide a bound on a particular class of processors. They show that universal quantum processors do not exist, but finite families of unitaries can be implemented with some error tolerance. They introduce the concept of type constants in Banach spaces and use this to prove a bound on quantum processors implementing a family of diagonal unitaries.

The authors then relate these bounds on programmable processors to computation in holographic spacetimes. They discuss the reconstruction wedge, which is the portion of the bulk degrees of freedom that can be recovered if the bulk state is known within a code space. They show that state-independent reconstruction is possible when the sum of the number of qubits in the program state and the number of qubits in the input state is much smaller than the black hole entropy. They also argue that the map from the bulk subspace to the boundary Hilbert space can be made isometric and independent of the specific state in the code space.

In a holographic thought experiment called the diagonal unitary game, Alice and Bob prepare states and throw them into the black hole, and the referee applies a global reconstruction procedure to recover the state on Bob's system. The authors show that there are computations that cannot be completed in the black hole interior, even when the unitary has a short description. They argue that these computations are computationally restricted from happening inside the black hole and provide a strategy to restrict bulk computation using the existence of the boundary quantum mechanical description.

In conclusion, the study provides constraints on physical computers in holographic spacetimes by showing that certain computations cannot be performed inside black holes. These constraints are derived from the properties of programmable quantum processors and the reconstruction wedge in AdS/CFT. The findings have implications for understanding the power of computers in quantum gravity and may have broader applications.

In this study, the authors investigate the constraints on physical computers in holographic spacetimes, specifically focusing on computations that occur inside black holes. They aim to understand the limitations of these computations and determine why certain unitaries are forbidden from being implemented inside a black hole.

The authors begin by discussing the value of nP, which controls the size of the computer, and the value of nA, which represents the size of the inputs. They argue that nP should be constrained physically rather than as a choice. They introduce the covariant entropy bound (CEB) as a natural constraint on nP, which is related to the black hole horizon. However, they find that at the upper limit of the CEB, they violate a previous guarantee of state-independent recovery. To address this issue, they introduce an assumption that allows them to restore state-independent recovery by using a larger black hole.

Next, the authors consider the value of nA and explain that it can be chosen such that it is much smaller than the black hole entropy. They summarize all the necessary constraints for running the diagonal unitary game inside a black hole and derive an inequality that ensures state-independent recovery and applies to the average success probability of the game.

The authors then define the success probability of a processor and introduce a threshold probability. They define a set of forbidden unitaries based on this threshold probability and explain that there are at least 2^k such unitaries, where k is logarithmic in the black hole entropy. They argue that these forbidden unitaries cannot be implemented inside the black hole due to information theoretic constraints.

In the next section, the authors discuss the relationship between models of computation and physical computers in the context of gravitational constraints. They highlight previous work on the connection between energy limits and computation speed and emphasize the difficulty of obtaining a precise bound on computation from a direct gravity perspective.

The authors then summarize their holographic thought experiment, where Alice prepares a randomly drawn string and Bob prepares a state on the A system. They discuss the computations that can be performed inside a black hole and argue that some computations are computationally forbidden. They suggest that the complexity of these forbidden computations may explain why they are forbidden.

The authors also mention the complexity of the AdS/CFT dictionary, which relates to the recovery of bulk data from the boundary. They clarify that their argument does not rely on the complexity of this map but rather on its state independence within a subspace of states.

In the final section, the authors discuss the optimality of a naive algorithm for decompressing the description of a forbidden unitary. They argue that this algorithm provides a lower bound on the number of computational steps needed and explain that any improvement in memory usage would also require an improvement in computational steps.

Overall, this study provides insights into the constraints on physical computers in holographic spacetimes, particularly in the context of computations inside black holes. The authors highlight the limitations of these computations and offer explanations for why certain unitaries are forbidden. They also discuss the connection between models of computation and physical computers in the presence of gravitational constraints.