Semiclassical Gravity Efficiently Solves $\mathsf{NP}$-Complete Problems

技术摘要：半经典引力高效解决 NP 完全问题

问题陈述
本文探讨了一个基本问题：引力本质上是量子还是经典的？虽然量子化引力是理论物理学中的一个标准假设，但确凿的实验证据仍然难以寻觅。作者研究了一个“半经典”世界的计算后果——在这种世界中，引力场被视为通过半经典爱因斯坦场方程（EFEs）与量子物质耦合的经典实体。具体而言，他们探讨了这种框架是否允许高效解决 NP 完全问题，而这类问题在标准量子力学下被广泛认为对于物理设备是难以处理的。

方法论
作者结合了三种不同的理论框架来构建其论证：

1. 半经典引力动力学： 他们利用半经典爱因斯坦场方程，$R_{\mu\nu} - \frac{1}{2}g_{\mu\nu}R = 8\pi\langle\Psi|\hat{T}_{\mu\nu}|\Psi\rangle$。在弱场、非相对论极限下，这些方程简化为薛定谔-牛顿（SN）方程。该方程引入了一个非线性势能 $V_G(\Psi)$，它源于质量粒子的引力自相互作用，并依赖于概率密度 $|\Psi|^2$。
2. 量子比特编码： 他们模拟了一个质量较大的、非相对论性的自旋-1/2 粒子（量子比特），处于自旋向上和自旋向下的叠加态。SN 动力学由于非线性自引力势的作用，会在这些分量之间诱导出依赖于初始条件的非平凡相位差 ($\Delta\phi_{SN}$)。
3. 计算复杂度降低： 作者采用了由 Abrams 和 Lloyd [22] 建立并由 Bao、Bouland 和 Jordan [21] 推广的算法框架。该框架证明，任何量子力学的非线性理论都可以通过利用区分在标准线性量子力学中指数级接近的量子态的能力，来高效解决 NP 完全问题。

该方法的核心在于将一个 NP 问题（具体为：判断一个语言 $L$ 是否存在有效的证明）映射为一个状态判别任务。利用 Valiant–Vazirani 定理，该问题被归约为区分两个特定的单量子比特态 $|\phi_0\rangle = |0\rangle$ 和 $|\phi_1\rangle$，这两者在指数级接近。作者随后展示了非线性演化算符 $S_{SN}$（由 SN 方程导出）在量子态流形上表现为一个非幺正微分同胚。根据 Bao–Bouland–Jordan 定理，此类映射必然会“拉伸”量子态流形上的测地线，从而放大接近态之间的距离。通过交替应用 $S_{SN}$ 与幺正旋转，算法可以在多项式时间内将指数级接近的态 $|\phi_0\rangle$ 和 $|\phi_1\rangle$ 分离到常数距离，从而实现高效判别并解决 NP 完全问题。

主要贡献与结果

• 非线性的导出： 本文确立了如果引力是经典的且通过半经典 EFEs 与物质耦合，则质量粒子的弱场动力学本质上是非线性的（即薛定谔-牛顿方程）。
• 算法构建： 作者证明了这种特定的非线性满足 Bao–Bouland–Jordan 算法所需的条件。他们证明了可以利用 SN 动力学来高效区分在标准线性量子力学中无法区分的量子态。
• 违反 PECTT： 主要结果是，一个受半经典引力支配的宇宙将允许高效（多项式时间）解决 NP 完全问题。这直接违反了物理扩展丘奇-图灵论题（PECTT），该论题假定没有任何物理过程能在多项式时间内判定 NP 完全问题。

意义与主张
本文认为，从半经典引力中获得的计算能力并非一种可被利用的特性，而是针对该理论本身的一种归谬法（reductio ad absurdum）。作者声称，高效解决 NP 完全问题的能力与我们对物理现实的理解（以 PECTT 为体现）之间存在“深刻的张力”。

因此，论文得出结论，以下两种可能性之一必然成立：

1. 引力在根本上不是经典的。
2. 引力是经典的，但半经典爱因斯坦场方程不能正确描述物质与引力之间的耦合。

作者倾向于第一种结论，暗示其结果为引力的量子化提供了新的计算论据。他们假设，将时空度规量子化将使弱场动力学线性化（消除自引力势项），从而恢复线性并保持 PECTT。本文将 PECTT 不仅仅视为一个计算机科学猜想，而是将其视为一种基本的物理原则，可以作为寻找一致的量子引力理论时的指导性约束。