离散体重构

根据AdS/CFT对应关系，某些时空的几何形状完全由边界上的量子态决定——实际上，由这些边界态部分的冯·诺依曼熵决定。这项工作研究了几何几何可以在多项式时间内从熵重构到什么程度。Bouland, Fefferman和Vazirani(2019)认为，如果想重建黑洞内部等区域，AdS/CFT地图可以呈指数级复杂。我们的主要结果提供了一种相反的结果:我们表明，在单一一维边界的特殊情况下，如果输入数据由相邻边界区域的熵列表组成，并且如果熵满足一个称为强次可加性的单一不等式，那么我们可以在线性时间内为该块构造一个图模型。此外，体图是平面的，它有O(N^2)个顶点(信息论的最小值)，而且它是“通用的”，只有边权取决于特定的熵。从组合的角度来看，我们的问题可以归结为著名的最小切割问题的“逆”:不是给出一个图并要求找到一个最小切割，这里我们给出了分离各种顶点集的最小切割的值，并且需要找到一个与这些值一致的加权无向图。我们对这个问题的解决方案依赖于“无体积”图的概念，这可能是AdS/CFT的独立兴趣。我们还在多个一维边界的情况下取得了初步进展——其中边界可以连接虫洞——包括一个平面体图存在时O(N^4)个顶点的上界(因此将问题纳入复杂性类NP)。