半经典引力高效解决NP完全问题

# 半经典引力高效解决NP完全问题
来源：https://arxiv.org/html/2606.14806
††致谢：所有作者贡献均等。
Matthew Fox
Chaitanya Karamchedu
[email protected] (mailto:[email protected])
马里兰大学计算机科学系，College Park, MD 20742, 美国
Sotirios Mygdalas
[email protected] (mailto:[email protected])
Perimeter理论物理研究所, Waterloo, ON N2L 2Y5, 加拿大
滑铁卢大学物理与天文学系, Waterloo, ON N2L 3W8, 加拿大

###### 摘要

假设引力场是经典的，并通过半经典爱因斯坦场方程与量子场耦合，我们证明一个有质量且非相对论的量子比特的弱场动力学原则上可以用于在多项式时间内解决NP完全问题。我们将这种巨大的计算能力归因于半经典爱因斯坦场方程所提供的非线性动力学。因此，上述两个假设意味着物理扩展丘奇-图灵论题被违反，我们认为这是引力量子化的证据。

## I引言

通往量子引力的道路并不容易。我们困在扶手椅中，几乎没有实验指导，谨慎起见，我们应该思考为何我们相信引力是量子力学的。会不会相反，引力从根本上不是量子的，而是经典的？当然，这个问题并不新鲜。它有着悠久而丰富的历史，可以追溯到20世纪60年代Møller【Møller, C. “广义相对论及相关问题中的能量-动量复形”，载于：Lichnerowicz, M. A. and Tonnelat, M. A. (1962 (https://arxiv.org/html/2606.14806#bib.bib1))】和Rosenfeld【Rosenfeld (1963 (https://arxiv.org/html/2606.14806#bib.bib2))】的开创性工作。

将引力视为经典而物质视为量子力学，这构成了*半经典引力*，它自然地分为两部分。第一部分是弯曲时空对量子场的影响。这一部分已得到充分理解（已有完整的著作如Wald (1995 (https://arxiv.org/html/2606.14806#bib.bib3))；Birrell and Davies (1982 (https://arxiv.org/html/2606.14806#bib.bib4))；Mukhanov and Winitzki (2007 (https://arxiv.org/html/2606.14806#bib.bib5))；Parker and Toms (2009 (https://arxiv.org/html/2606.14806#bib.bib6))），并且由于Hawking的发现——引力场可以产生粒子【Hawking (1975 (https://arxiv.org/html/2606.14806#bib.bib7))】，它已被证明是无价的。第二部分是量子场对弯曲时空的影响。这一部分远不如第一部分那样被理解，主要是因为不清楚叠加时空意味着什么，而这似乎是不可避免的【Wald (1994 (https://arxiv.org/html/2606.14806#bib.bib8))】。

在量子引力学界，半经典引力通常被视为对尚未发现的量子引力理论的一种近似【Wald (1995 (https://arxiv.org/html/2606.14806#bib.bib3))；Birrell and Davies (1982 (https://arxiv.org/html/2606.14806#bib.bib4))；Mukhanov and Winitzki (2007 (https://arxiv.org/html/2606.14806#bib.bib5))；Parker and Toms (2009 (https://arxiv.org/html/2606.14806#bib.bib6))】。然而，尽管有许多正在进行的实验（例如，Marletto and Vedral (2017 (https://arxiv.org/html/2606.14806#bib.bib9))；Berglund *et al.* (2023 (https://arxiv.org/html/2606.14806#bib.bib10))；Namdar *et al.* (2023 (https://arxiv.org/html/2606.14806#bib.bib11))；Tobar *et al.* (2024 (https://arxiv.org/html/2606.14806#bib.bib12))），目前还没有决定性的实验证据表明引力是量子化的。因此，量子引力主要依靠理论论证，例如Eppley和Hannah【Eppley and Hannah (1977 (https://arxiv.org/html/2606.14806#bib.bib13))】以及Page和Geilker【Page and Geilker (1981 (https://arxiv.org/html/2606.14806#bib.bib14))】提出的论证。然而，这些论证中有许多被认为是不结论性的【Mattingly (2005 (https://arxiv.org/html/2606.14806#bib.bib15),2006 (https://arxiv.org/html/2606.14806#bib.bib16))；Carlip (2008 (https://arxiv.org/html/2606.14806#bib.bib17))；Großardt (2022 (https://arxiv.org/html/2606.14806#bib.bib18))；Bahrami *et al.* (2014 (https://arxiv.org/html/2606.14806#bib.bib19))；Kent (2018 (https://arxiv.org/html/2606.14806#bib.bib20))】，这凸显了为引力量子化提出新论据的必要性。

在本文中，我们通过探索一个基本半经典世界的计算后果来提供这样一个论据。特别是，我们证明如果半经典引力（如半经典爱因斯坦场方程所描述）是正确的，那么就有可能在多项式时间内解决NP完全问题。由于这对关于什么能被物理设备有效计算、什么不能的普遍信念（这些信念被概括为丘奇-图灵论题的一个强大物理版本）构成了挑战，我们的结果表明半经典引力不能是对物理现实的正确描述。

我们的主要结果依赖于Bao、Bouland和Jordan的一个算法【Bao *et al.* (2016 (https://arxiv.org/html/2606.14806#bib.bib21))】，该算法本身基于Abrams和Lloyd的一个更早算法【Abrams and Lloyd (1998 (https://arxiv.org/html/2606.14806#bib.bib22))】。本质上，Abrams-Lloyd算法展示了如何利用Weinberg的非线性量子力学理论【Weinberg (1989 (https://arxiv.org/html/2606.14806#bib.bib23))】来高效解决困难的计算问题（例如，NP完全问题）。几年后，Bao-Bouland-Jordan算法扩展了这一结果，并表明这实际上是一个更普遍的现象：基本上*任何*非线性量子力学理论都可以用来高效解决困难的计算问题。我们的结论来自于将Bao-Bouland-Jordan算法与Bahrami等人【Bahrami *et al.* (2014 (https://arxiv.org/html/2606.14806#bib.bib19))】以及Giulini等人【Giulini *et al.* (2023 (https://arxiv.org/html/2606.14806#bib.bib24))】的论证相结合，这些论证认为半经典引力中一个质量量子比特的弱场演化必然是非线性的。顺便提一下，我们的工作与Kent等人的相关工作是一致的【Kent (2005 (https://arxiv.org/html/2606.14806#bib.bib25),2021 (https://arxiv.org/html/2606.14806#bib.bib26))；Fedida and Kent (2026 (https://arxiv.org/html/2606.14806#bib.bib27))】，我们将在第五节 (https://arxiv.org/html/2606.14806#S5) 中讨论这些工作。

## IINP与物理扩展丘奇-图灵论题

计算复杂性理论试图根据问题的内在难度对其进行分类，通常通过量化解决它们所需的资源（例如时间或内存）来实现。在本文中，我们主要关注当提供一个候选解决方案或*证明*时，问题难度如何变化。事实上，许多问题在*寻找*解决方案所需时间与*验证*解决方案所需时间之间表现出不对称性。例如，考虑一个数独谜题：检查一个填好的格子远比从头构建一个要容易得多。然而，目前尚不清楚这种区别是否反映了计算难度上的真正差异。在计算复杂性理论中，这个问题被形式化为著名的P对NP问题，我们现在就来讨论。

直观上，复杂性类P（“多项式时间”）包含了所有可以被经典计算机高效求解（即*判定*）的计算问题。111实际上，有效经典计算机能够解决的计算问题集合不是P，而是BPP（“有界错误概率多项式时间”），即P的概率模拟。然而，普遍认为P = BPP【Arora and Barak (2009 (https://arxiv.org/html/2606.14806#bib.bib28))】，因此在本讨论中我们只谈论P。例如，判断一个二进制字符串是否为回文串属于P。更形式化地，设{0,1}^n为所有n位二进制字符串的集合，{0,1}^*为所有有限长度二进制字符串的集合（即{0,1}^* = ⋃_{n≥1} {0,1}^n），|x|为字符串x的长度。那么，P包含所有这样的函数L: {0,1}^* → {0,1}（即*语言*），使得存在一个确定性的多项式时间经典算法M（即一个*确定性的多项式时间图灵机*），对于所有输入x ∈ {0,1}^*，L(x)=1当且仅当M(x)=1。

另一方面，复杂性类NP（“非确定性多项式时间”）包含了所有可以通过经典计算机有效检查有效证明的计算问题。例如，判断一个逻辑布尔公式如(x1 ∨ x2) ∧ (x3 ∨ ¬x2)，其中x1, x2, x3 ∈ {0,1}，是否存在一个有效赋值，属于NP。222这个问题与布尔可满足性问题SAT密切相关【Arora and Barak (2009 (https://arxiv.org/html/2606.14806#bib.bib28))】。特别地，L ∈ NP当且仅当存在一个确定性的多项式时间算法M和一个多项式p，使得对于所有输入x ∈ {0,1}^*，L(x)=1当且仅当存在y ∈ {0,1}^{p(|x|)}（通常称为*证明*、*证书*或*见证*），使得M(x,y)=1。换句话说，L ∈ NP当且仅当对于所有x ∈ {0,1}^*，如果L(x)=1，则存在一个证明会使M接受x；如果L(x)=0，则不存在任何证明会使M接受x。

显然，P ⊆ NP，而P是否等于NP是一个重大的未解问题（事实上，是一个千禧年大奖难题【Carlson *et al.* (2023 (https://arxiv.org/html/2606.14806#bib.bib29))】）。普遍共识是P ≠ NP，因为相反的情况将意味着证明一个数学命题与验证给定证明的正确性一样容易，而这与数学经验相悖【Impagliazzo (1995 (https://arxiv.org/html/2606.14806#bib.bib30))】。

现在，量子计算的整个前提是它改变了关于在物理世界中什么可以高效计算、什么不可以的叙事。特别是，存在一些被广泛认为属于NP\P的问题，可以在量子计算机上高效解决。最著名的此类问题是整数因式分解，Shor为此展示了其同名的多项式时间量子算法【Shor (1997 (https://arxiv.org/html/2606.14806#bib.bib31))】。

话虽如此，人们普遍预期NP中最难的问题——即所谓的*NP完全*问题——没有有效的量子算法【Nielsen and Chuang (2010 (https://arxiv.org/html/2606.14806#bib.bib32))；Aaronson (2005 (https://arxiv.org/html/2606.14806#bib.bib33))】。这种信念部分源于这样一种观点：NP完全问题似乎缺乏实现指数级量子加速所需的结构【Aaronson (2005 (https://arxiv.org/html/2606.14806#bib.bib33))】。当然，这并不是说量子计算机对这些问题的解决没有优势。例如，Grover算法解决任何NP完全问题的速度比任何经典暴力算法都快二次方【Grover (1998 (https://arxiv.org/html/2606.14806#bib.bib34))】。然而，这种优势是适度的，并不能提供在量子计算机上多项式时间内解决NP完全问题所需的指数级加速。同样值得注意的是，如果量子计算机不能多项式时间内解决NP完全问题，那么P ≠ NP【Nielsen and Chuang (2010 (https://arxiv.org/html/2606.14806#bib.bib32))】。

更一般地，量子信息理论以及计算理论本身的一个信条是，没有物理上合理的计算模型（也许甚至比量子计算更强大）能够高效解决NP完全问题。这一期望被规定在*物理扩展丘奇-图灵论题*中，该论题最初由Freedman、Kitaev、Larsen和Wang在21世纪初提出【Freedman *et al.* (2002 (https://arxiv.org/html/2606.14806#bib.bib35))】，并扩展了Deutsch在20世纪80年代提出的丘奇-图灵论题的早期“物理”版本【Deutsch (1985 (https://arxiv.org/html/2606.14806#bib.bib36))】。

###### 物理扩展丘奇-图灵论题 (PECTT)。

没有任何物理过程可以在多项式步数内判定一个NP完全问题。

虽然该论题源于计算机科学，但它主要是关于物理世界的一个假设，因为它阐明了物理设备能够高效计算什么、不能计算什么。因此，在区分不同物理理论时，PECTT规定：如果一个候选理论可以被用来高效解决NP完全问题，则它应被视为不可信的。最终，我们将证明半经典引力就是这样一个理论。

## III半经典引力及其弱场极限

历史上，最流行的半经典引力理论由*半经典爱因斯坦场方程*描述，333我们采用自然单位制，其中c = G = ħ = 1。

R_{μν} - (1/2) g_{μν} R = 8π ⟨Ψ| T̂_{μν} |Ψ⟩, (1)

其中（未量子化的）度规g_{μν}由量子物质能量-动量张量T̂_{μν}在时空中的期望值来源【Giulini *et al.* (2023 (https://arxiv.org/html/2606.14806#bib.bib24))】。这一理论实现了Møller【Møller, C. “广义相对论及相关问题中的能量-动量复形”，载于：Lichnerowicz, M. A. and Tonnelat, M. A. (1962 (https://arxiv.org/html/2606.14806#bib.bib1))】和Rosenfeld【Rosenfeld (1963 (https://arxiv.org/html/2606.14806#bib.bib2))】的最初提议，并且更形式化地，已知它可以从一个作用量原理导出【Kibble (1978 (https://arxiv.org/html/2606.14806#bib.bib37))；Kibble and Randjbar-Daemi (1980 (https://arxiv.org/html/2606.14806#bib.bib38))】。尽管存在一些技术上的担忧（参见Carlip (2008 (https://arxiv.org/html/2606.14806#bib.bib17))及其参考文献），期望值⟨Ψ|T̂_{μν}|Ψ⟩可以以一种一致且公理化的方式构建【Wald (1995 (https://arxiv.org/html/2606.14806#bib.bib3))；Giulini *et al.* (2023 (https://arxiv.org/html/2606.14806#bib.bib24))】。此外，当T̂_{μν}在状态|Ψ⟩中的涨落不是很大时，即当宏观的能量-动量构型未被置于叠加态时，半经典爱因斯坦场方程是良好定义的【Diósi (1984 (https://arxiv.org/html/2606.14806#bib.bib39))；Page and Geilker (1981 (https://arxiv.org/html/2606.14806#bib.