# Complexity and entanglement in non-local computation and holography

Article · Alex May

- Archive id: arxiv:2204.00908
- Published: 2022-11-28
- Venue: Quantum
- DOI: https://doi.org/10.22331/q-2022-11-28-864
- arXiv: https://arxiv.org/abs/2204.00908
- Citations: 23
- Source URL: https://doi.org/10.22331/q-2022-11-28-864
- PDF: https://quantum-journal.org/papers/q-2022-11-28-864/pdf/
- Provenance: openalex+arxiv

## Abstract

Does gravity constrain computation? We study this question using the AdS/CFT correspondence, where computation in the presence of gravity can be related to non-gravitational physics in the boundary theory. In AdS/CFT, computations which happen locally in the bulk are implemented in a particular non-local form in the boundary, which in general requires distributed entanglement. In more detail, we recall that for a large class of bulk subregions the area of a surface called the ridge is equal to the mutual information available in the boundary to perform the computation non-locally. We then argue the complexity of the local operation controls the amount of entanglement needed to implement it non-locally, and in particular complexity and entanglement cost are related by a polynomial. If this relationship holds, gravity constrains the complexity of operations within these regions to be polynomial in the area of the ridge.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Gravity & Holography](https://space-kitty.com/topics/quantum-gravity-holography)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.