Complexity and entanglement in non-local computation and holography
arXiv:2204.00908 · doi:10.22331/q-2022-11-28-864
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.
arXiv commentv5 adds doi's to bibliography
References in corpus (48)
- The Large N Limit of Superconformal Field Theories and Supergravity
- Aspects of Holographic Entanglement Entropy
- A Covariant Holographic Entanglement Entropy Proposal
- Improved Simulation of Stabilizer Circuits
- Generalized gravitational entropy
- Ultimate physical limits to computation
- The maximum speed of dynamical evolution
- A Covariant Entropy Conjecture
- Quantum Extremal Surfaces: Holographic Entanglement Entropy beyond the Classical Regime
- Quantum corrections to holographic entanglement entropy
- The entropy of bulk quantum fields and the entanglement wedge of an evaporating black hole
- Holography from Conformal Field Theory
- Reconstruction of Bulk Operators within the Entanglement Wedge in Gauge-Gravity Duality
- Relative entropy equals bulk relative entropy
- Maximin Surfaces, and the Strong Subadditivity of the Covariant Holographic Entanglement Entropy
- The Gravity Dual of a Density Matrix
- Causality & holographic entanglement entropy
- Deriving covariant holographic entanglement
- Proof of Classical Versions of the Bousso Entropy Bound and of the Generalized Second Law
- Local bulk S-matrix elements and CFT singularities
- Entropy, Extremality, Euclidean Variations, and the Equations of Motion
- Entanglement Wedge Reconstruction via Universal Recovery Channels
- A Monogamy-of-Entanglement Game With Applications to Device-Independent Quantum Cryptography
- Simplified instantaneous non-local quantum computation with applications to position-based cryptography
- Proof of a Quantum Bousso Bound
- Quantum teleportation scheme by selecting one of multiple output ports
- Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints
- BQP-completeness of Scattering in Scalar Quantum Field Theory
- Position-Based Quantum Cryptography: Impossibility and Constructions
- Leading order corrections to the quantum extremal surface prescription
- Location-Dependent Communications using Quantum Entanglement
- Quantum algorithm for Petz recovery channels and pretty good measurements
- Large Breakdowns of Entanglement Wedge Reconstruction
- Probing phase transitions of holographic entanglement entropy with fixed area states
- Fast quantum computation at arbitrarily low energy
- Enhanced corrections near holographic entanglement transitions: a chaotic case study
- Practical Position-Based Quantum Cryptography
- Valence bond solid formalism for d-level one-way quantum computation
- Holographic scattering requires a connected entanglement wedge
- Quantum secret sharing for general access structures
- Asymptotic performance of port-based teleportation
- Holographic quantum tasks with input and output regions
- Geometry of Banach spaces: a new route towards Position Based Cryptography
- Quantum tasks in holography
- The Garden-Hose Model
- Holography as a resource for non-local quantum computation
- Bulk private curves require large conditional mutual information
- Non-local computation of quantum circuits with small light cones
Cited by in corpus (16)
- Quantum Null Geometry and Gravity
- Holographic Codes from Hyperinvariant Tensor Networks
- Optimality of the pretty good measurement for port-based teleportation
- Relating non-local quantum computation to information theoretic cryptography
- Holographic scattering and non-minimal RT surfaces
- Minimal Port-based Teleportation
- Code-routing: a new attack on position verification
- Port-based entanglement teleportation via noisy resource states
- Linear gate bounds against natural functions for position-verification
- Security of quantum position-verification limits Hamiltonian simulation via holography
- Cryptographic tests of the python's lunch conjecture
- Constraints on physical computers in holographic spacetimes
- From port-based teleportation to Frobenius reciprocity theorem: partially reduced irreducible representations and their applications
- Asymptotic teleportation schemes bridging between standard and port-based teleportation
- A resource theory of asynchronous quantum information processing
- On the distinguishability of geometrically uniform quantum states