论文标题
非本地计算和全息图中的复杂性和纠缠
Complexity and entanglement in non-local computation and holography
论文作者
论文摘要
重力会限制计算吗？我们使用ADS/CFT对应关系研究了这个问题，其中重力存在的计算可能与边界理论中的非重力物理有关。在ADS/CFT中，在批量上本地发生的计算以边界中的特定非本地形式实施，这通常需要分布式纠缠。更详细地，我们回想起，对于一大批散装子区域，称为山脊的表面面积等于边界中可用的相互信息，以非局部进行计算。然后，我们认为本地操作的复杂性控制非局部实施所需的纠缠量，特别是复杂性和纠缠成本与多项式相关。如果这种关系成立，重力将这些区域内的操作的复杂性限制为在山脊区域中是多项式的。
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.
