arXiv:2204.00908 · Quantum

Complexity and entanglement in non-local computation and holography

Alex May

Published Nov 28, 2022• 23 citations

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.

DOI: 10.22331/q-2022-11-28-864

Related papers

Entanglement entropy, holography and gravity

L.R. de Ruiter

In this thesis we review how entanglement entropy is related to the gravitational equations of motion by means of the AdS/CFT correspondence. We consider the entanglement entropy of a ball-shaped spatial region in the CFT vacuum and derive a holographic relation between the relative entropy and the equations of motion in the dual bulk spacetime. For small perturbations around the CFT vacuum, we show that the first law of entanglement entropy requires the dual metric to satisfy the linearized Einstein equation when the entanglement entropy is given by the area of an extremal surface in the bulk. We discuss a recent paper in which the complete Einstein equation is derived and explain why we believe this result is incomplete. This thesis serves both as a commentary on this paper, as well as a detailed review of the relationship between entanglement and gravity.

Jan 1, 20180 citations

Entanglement entropy and algebraic holography

Bernard S. Kay

In 2006, Ryu and Takayanagi (RT) pointed out that (with a suitable cutoff) the entanglement entropy between two complementary regions of an equal-time surface of a d+1-dimensional conformal field theory on the conformal boundary of AdS_{d+2} is, when the AdS radius is appropriately related to the parameters of the CFT, equal to 1/4G times the area of the d-dimensional minimal surface in the AdS bulk which has the junction of those complementary regions as its boundary, where G is the bulk Newton constant. We point out here that the RT-equality implies that, in the quantum theory on the bulk AdS background which is related to the boundary CFT according to Rehren's 1999 algebraic holography theorem, the entanglement entropy between two complementary bulk Rehren wedges is equal to 1/4G times the (suitably cut off) area of their shared ridge. (This follows because of the geometrical fact that, for complementary ball-shaped regions, the RT minimal surface is precisely the shared ridge of the complementary bulk Rehren wedges which correspond, under Rehren's bulk-wedge to boundary double-cone bijection, to the complementary boundary double-cones whose bases are the RT complementary balls.) This is consistent with the Bianchi-Meyers conjecture -- that, in a theory of quantum gravity, the entanglement entropy, S, between the degrees of freedom of a given region with those of its complement is S = A/4G (+ lower order terms) -- but only if the phrase 'degrees of freedom' is replaced by 'matter degrees of freedom'. It also supports related previous arguments of the author -- consistent with the author's 'matter-gravity entanglement hypothesis' -- that the AdS/CFT correspondence is actually only a bijection between just the matter (i.e. non-gravity) sector operators of the bulk and the boundary CFT operators.

arXiv:1605.07872May 25, 20160 citations

Holography as a resource for non-local quantum computation

Kfir Dolev, Sam Cree

If two parties share sufficient entanglement, they are able to implement any channel on a shared bipartite state via non-local quantum computation -- a protocol consisting of local operations and a single simultaneous round of quantum communication. Such a protocol can occur in the AdS/CFT correspondence, with the two parties represented by regions of the CFT, and the holographic state serving as a resource to provide the necessary entanglement. This boundary non-local computation is dual to the local implementation of a channel in the bulk AdS theory. Previous work on this phenomenon was obstructed by the divergent entanglement between adjacent CFT regions, and tried to circumvent this issue by assuming that certain regions are irrelevant. However, the absence of these regions introduces violent phenomena that prevent the CFT from implementing the protocol. Instead, we resolve the issue of divergent entanglement by using a finite-memory quantum simulation of the CFT. We show that any finite-memory quantum system on a circular lattice yields a protocol for non-local quantum computation. In the case of a quantum simulation of a holographic CFT, we carefully show that this protocol implements the channel performed by the local bulk dynamics. Under plausible physical assumptions about quantum computation in the bulk, our results imply that non-local quantum computation can be performed for any polynomially complex unitary with a polynomial amount of entanglement. Finally, we provide a concrete example of a holographic code whose bulk dynamics correspond to a Clifford gate, and use our results to show that this corresponds to a non-local quantum computation protocol for this gate.

arXiv:2210.13500Oct 24, 20225 citations

Holographic scattering requires a connected entanglement wedge

Alex May, Geoff Penington, Jonathan Sorce

A bstract In AdS/CFT, there can exist local 2-to-2 bulk scattering processes even when local scattering is not possible on the boundary; these have previously been studied in con- nection with boundary correlation functions. We show that boundary regions associated with these scattering configurations must have O (1 /G N ) mutual information, and hence a connected entanglement wedge. One of us previously argued for this statement from the boundary theory using operational tools in quantum information theory. We improve that argument to make it robust to small errors and provide a proof in the bulk using focusing arguments in general relativity. We also provide a direct link to entanglement wedge reconstruction by showing that the bulk scattering region must lie inside the con- nected entanglement wedge. Our construction implies the existence of nonlocal quantum computation protocols that are exponentially more efficient than the optimal protocols currently known.

arXiv:1912.05649Journal of High Energy PhysicsAug 1, 202031 citations

Holographic scattering requires a connected entanglement wedge

Alex May

In AdS/CFT, there can exist local 2-to-2 bulk scattering processes even when local scattering is not possible on the boundary; these have previously been studied in con- nection with boundary correlation functions. We show that boundary regions associated with these scattering configurations must have O(1/GN) mutual information, and hence a connected entanglement wedge. One of us previously argued for this statement from the boundary theory using operational tools in quantum information theory. We improve that argument to make it robust to small errors and provide a proof in the bulk using focusing arguments in general relativity. We also provide a direct link to entanglement wedge reconstruction by showing that the bulk scattering region must lie inside the con- nected entanglement wedge. Our construction implies the existence of nonlocal quantum computation protocols that are exponentially more efficient than the optimal protocols currently known.

Jul 4, 202331 citations

Holographic pseudoentanglement and the complexity of the AdS/CFT dictionary

Chris Akers, Adam Bouland, Lijie Chen +3 more

The `quantum gravity in the lab' paradigm suggests that quantum computers might shed light on quantum gravity by simulating the CFT side of the AdS/CFT correspondence and mapping the results to the AdS side. This relies on the assumption that the duality map (the `dictionary') is efficient to compute. In this work, we show that the complexity of the AdS/CFT dictionary is surprisingly subtle: there might be cases in which one can efficiently apply operators to the CFT state (a task we call 'operator reconstruction') without being able to extract basic properties of the dual bulk state such as its geometry (which we call 'geometry reconstruction'). Geometry reconstruction corresponds to the setting where we want to extract properties of a completely unknown bulk dual from a simulated CFT boundary state. We demonstrate that geometry reconstruction may be generically hard due to the connection between geometry and entanglement in holography. In particular we construct ensembles of states whose entanglement approximately obey the Ryu-Takayanagi formula for arbitrary geometries, but which are nevertheless computationally indistinguishable. This suggests that even for states with the special entanglement structure of holographic CFT states, geometry reconstruction might be hard. This result should be compared with existing evidence that operator reconstruction is generically easy in AdS/CFT. A useful analogy for the difference between these two tasks is quantum fully homomorphic encryption (FHE): this encrypts quantum states in such a way that no efficient adversary can learn properties of the state, but operators can be applied efficiently to the encrypted state. We show that quantum FHE can separate the complexity of geometry reconstruction vs operator reconstruction, which raises the question whether FHE could be a useful lens through which to view AdS/CFT.

arXiv:2411.04978Nov 7, 20242 citations