机构名称：
¥ 2.0
复杂性理论涉及计算数学模型的能力。人们普遍认为这些模型捕捉到了物理计算机的计算能力，但要使这种联系精确起来却很困难。例如，考虑一个量子电路模型，我们可能倾向于将电路深度等同于在物理计算机上实现计算所需的时间。通过假设能量有一个界限，可以通过 Margolus-Levinin 定理 [1] 精确地建立这种联系。然而，对于任何给定的幺正，都可以构造一个汉密尔顿量，它可以任意快速地实现该幺正，即使在有界能量的情况下 [2]。这意味着在这个汉密尔顿计算模型中，能量界限不足以将计算和物理时间概念联系起来。诸如此类的观察使得如何将物理计算机的极限与计算的数学模型联系起来变得不清楚。在本文中，我们朝着理解物理计算机的极限迈出了初步的一步。为了考虑物理计算机上的全部约束以及计算机可以利用的完整物理设置，我们考虑在量子引力背景下的计算。我们在 AdS / CFT 框架内工作，该框架声称渐近反德西特 (AdS) 空间中的量子引力与存在于该时空边界的纯量子力学理论（共形场论，CFT）等价。我们的主要结果是构建了一个幺正族，这是在熵为 S bh 的黑洞内部运行的计算机无法执行的，其中计算是在 n 个量子比特上进行的，并且 log S bh ≤ n ≪ S bh ，我们构建的族的大小为 2 o ( S bh )。因为 n ≪ S bh ，所以计算的输入本身并不与引力强耦合。相反，受到限制的必须是对这些小输入的计算。虽然我们最终感兴趣的是宇宙中计算机的物理极限，但在 AdS / CFT 对应背景下工作为我们提供了量子引力的精确框架。同样，计算机科学的一个基本观察是，计算机的能力对于计算模型细节的“合理”变化具有很强的鲁棒性：经典计算机可以用图灵机、均匀电路等来描述，解决给定计算问题所需的资源只会发生多项式变化。量子计算机同样具有同样的鲁棒性。这种鲁棒性表明，了解 AdS 中计算机的能力可能会产生更广泛适用的见解。天真地说，体量子引力理论和量子力学边界之间的 AdS / CFT 对偶表明量子引力中计算机的能力应该在某种程度上等同于量子计算机。我们可以想象在量子计算机上模拟 CFT，从而产生在对偶体图像中运行的任何计算的结果。然而，这种方法很复杂，因为边界 CFT 描述和体引力描述之间的映射可能呈指数级复杂度 [ 3 – 6 ] 。因此，从边界模拟确定体计算的结果本身可能非常复杂，从而导致体和边界之间的效率差异。一个有趣的观察是，这为量子引力计算机比量子计算机强大得多留下了可能性 [ 7 ] 。在这项工作中，我们给出了一种利用边界量子力学描述的存在来限制体计算的策略。我们假设体到边界映射的关键属性是状态独立性，在 AdS / CFT 中，当重建适当小的体子系统时，我们就拥有了这种属性。我们还利用这个映射是等距的。1
全息时空中物理计算机的约束
主要关键词
相关文件推荐
