Black Holes and Complexity Classes
Black Holes and Complexity Classes
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
L. Susskind
中科院分区：
文献类型：
--
作者：
L. Susskind
目前还不清楚使用量子计算来加速经典计算的局限性。一个例子是加速PSPACE完整计算的能力。我们也不知道经典广义相对论描述黑洞内部几何的持续时间的限制是什么。已知的是，这两个问题密切相关：GR描述黑洞的时间越长，量子计算机的局限性就越大。这个结论，公式化为定理，是斯科特·阿伦森和我自己所做的未发表的工作的结果，我在这里解释。
It is not known what the limitations are on using quantum computation to speed up classical computation. An example would be the power to speed up PSPACE-complete computations. It is also not known what the limitations are on the duration of time over which classical general relativity can describe the interior geometry of black holes. What is known is that these two questions are closely connected: the longer GR can describe black holes, the more limited are quantum computers. This conclusion, formulated as a theorem, is a result of unpublished work done by Scott Aaronson and myself which I explain here.