Complexity and entanglement in non-local computation and holography
- URL: http://arxiv.org/abs/2204.00908v6
- Date: Fri, 18 Nov 2022 23:34:13 GMT
- Title: Complexity and entanglement in non-local computation and holography
- Authors: Alex May
- Abstract summary: We study the question using the AdS/CFT computation, 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- 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.
Related papers
- Nonlocality under Computational Assumptions [51.020610614131186]
A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations.
We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
arXiv Detail & Related papers (2023-03-03T16:53:30Z) - Extending the Known Region of Nonlocal Boxes that Collapse Communication
Complexity [1.1970409518725493]
Non-signalling boxes (NS) are theoretical resources defined by the principle of no-faster-than-light communication.
Some of them are known to collapse communication complexity (CC)
In the present letter, we find a better sufficient condition for a nonlocal box to collapse CC, thus extending the known collapsing region.
arXiv Detail & Related papers (2023-02-01T14:50:08Z) - Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
The percolation transition is defined through the appearance of the infinite cluster.
We show that the exponentially increasing dimensionality of the Hilbert space makes its covering by finite-size hyperspheres inefficient.
Our approach to the percolation transition in compact metric spaces may prove useful for its rigorous treatment in other contexts.
arXiv Detail & Related papers (2022-10-15T13:53:21Z) - From locality to irregularity: Introducing local quenches in massive
scalar field theory [68.8204255655161]
We consider the dynamics of excited local states in massive scalar field theory in an arbitrary spacetime dimension.
We identify different regimes of their evolution depending on the values of the field mass and the quench regularization parameter.
We also investigate the local quenches in massive scalar field theory on a cylinder and show that they cause an erratic and chaotic-like evolution of observables.
arXiv Detail & Related papers (2022-05-24T18:00:07Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space.
We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states.
Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
arXiv Detail & Related papers (2022-03-11T17:19:26Z) - Bounds on quantum evolution complexity via lattice cryptography [0.0]
We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators.
Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries.
arXiv Detail & Related papers (2022-02-28T16:20:10Z) - Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
We formulate novel fast NonLocal blocks, capable of reducing complexity from quadratic to linear with no loss in performance.
The proposed method, which we dub as "Poly-NL", is competitive with state-of-the-art performance across image recognition, instance segmentation, and face detection tasks.
arXiv Detail & Related papers (2021-07-06T19:51:37Z) - Holographic quantum tasks with input and output regions [0.0]
In this article we consider tasks where inputs and outputs are encoded into extended spacetime regions.
We show that this leads to stronger constraints than have been derived in the point based setting.
arXiv Detail & Related papers (2021-01-21T21:09:45Z) - Local Propagation in Constraint-based Neural Network [77.37829055999238]
We study a constraint-based representation of neural network architectures.
We investigate a simple optimization procedure that is well suited to fulfil the so-called architectural constraints.
arXiv Detail & Related papers (2020-02-18T16:47:38Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.