Complexity and entanglement in non-local computation and holography

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.

v5 adds doi's to bibliography

References in corpus (9)

• Holography from Conformal Field Theory
• Causality & holographic entanglement entropy
• Deriving covariant holographic entanglement
• Local bulk S-matrix elements and CFT singularities
• Proof of a Quantum Bousso Bound
• Quantum teleportation scheme by selecting one of multiple output ports
• Location-Dependent Communications using Quantum Entanglement
• Fast quantum computation at arbitrarily low energy
• Holography as a resource for non-local quantum computation

Cited by in corpus (13)

• Quantum Null Geometry and Gravity
• Holographic Codes from Hyperinvariant Tensor Networks
• Relating non-local quantum computation to information theoretic cryptography
• Holographic scattering and non-minimal RT surfaces
• Port-based entanglement teleportation via noisy resource states
• Linear gate bounds against natural functions for position-verification
• Constraints on physical computers in holographic spacetimes
• Cryptographic tests of the python's lunch conjecture
• Security of quantum position-verification limits Hamiltonian simulation via holography
• Asymptotic teleportation schemes bridging between standard and port-based teleportation
• From port-based teleportation to Frobenius reciprocity theorem: partially reduced irreducible representations and their applications
• A resource theory of asynchronous quantum information processing
• On the distinguishability of geometrically uniform quantum states