引言
这篇物理中的计算理论，将进一步阐释物理系统的 NP 困难的内涵和外延，同时将结合量子蒙特卡洛算法的符号问题，进一步解释当一个物理系统被证明 NP 困难时，到底意味着什么。这一篇内容，除了给出引用的部分外，主要是我自己思考的一些结果。
NP困难的物理系统
定义
无论是多自由度的经典系统还是量子系统，都可以统一的定义系统的NP困难：
给定系统的参数和能量\(E_0\)，是否存在构型（或波函数）使得系统能量不大于\(E_0\)，该问题记为基态能量判别问题。
如果某类系统的基态能量判别问题是NP困难的，则称对应的物理系统是NP困难。
正如在经典自旋系统的NP完全中指出的，如果基态能量判别问题都是NP困难的，自然配分函数等统计性质的求解也是NP困难的。但是本来物理中也不期望对任何稍微复杂的系统得到多项式时间复杂度的严格解决，因此，我们更关心是否能够在多项式的时间里利用数值方法得到比较有效的近似，下面将看到NP困难本身对于近似的限制。
BPP＝P
对于NP困难物理系统近似的限制，主要源自两个方面。第一个就是 BPP=P。在计算复杂度理论概念备忘中，已经提到过了BPP＝P这一假设，当然这一假设还没有证明，但依旧算是普遍共识。就像我们所有的工作证明NP困难，但这些问题真的困难还依赖于\(P\neq NP\) 的假设一样，因此我们这篇直接默认其正确性。
BPP＝P对于基态能量判别问题这一具体情况，就是说，如果有依赖于随机数的算法，可以在多项式时间内对该问题的答案是或否给出超过\(1/2\)的概率正确的回答，那么这一基态能量判别问题一定可以在多项式时间给出严格正确的判定。因此对于 NP 困难的系统，\(P\neq NP, P=BPP\)，两个未被证明的假设就联合保证了，没有任何算法可以在多项式时间给出该问题正确率超过\(1/2\)的答案。某种程度上，这就宣告了所有数值方法的失效，因为你甚至都无法找到任何多项式时间算法，给出哪怕超过瞎猜一点点正确率的答案。换句话说，对于NP困难系统，任何多项式算法尝试解决基态能量判别问题都等价于扔硬币瞎猜。
strong NP-completeness
对于NP困难物理系统，另一个强烈限制近似算法成功的因素就是 strong NPC。这次我们考虑的是对应判别问题的基态能量优化问题（NPO），换句话说就是考虑物理学家最常做的事情，如何给出系统基态能量的最佳近似。所谓有效可行的近似方案，其实就是计算理论中说的 FPTAS，相关定义及之后出现概念的解释，都请参考之前的计算复杂度理论概念备忘。
考虑之前经典自旋系统的NP完全给出的3D spin glass，这样系统的能量判别问题显然是 strong NPC，因为所有的数值都限制在\(\pm1, 0\)，而问题还是NP完全的。同时根据定义，自旋自由度和 coupling 都是整数，那么优化目标－基态能量也必然是整数。 之前我们已经看到 integer valued strong NPC 问题一定没有 FPTAS。也就是说，3D spin glass 的基态能量不可能有任何有效的算法或数值方法可以进行有效的逼近。对于有外磁场的2D自旋系统也是同理。这就彻底毁灭了这类NP困难物理系统，用数值方法一定程度上解决的希望。因此如果一个物理系统的基态能量判别问题被证明是 integer valued strong NPC，那么理智的人就应该躲开这种问题，否则还不如直接去解决 \(P\neq NP\)。
当然还有另一个路线，就是尝试从证明了NP完全的系统中，尝试分离出一些不在NP完全的子问题。一个问题是NP完全，指的是将该问题完全通用的解决是NP完全，并不排除有一些特殊的子问题不是NP完全。但鉴于总问题是NP完全，其解决算法可以是分类讨论，那么也就暗示了该问题中至少有一些子问题是NP完全。因此更精细化的工作，就是从笼统的NP完全系统向外“抢救”一些对称性比较高，或者无序比较小的系统，并在 P 时间近似这些问题。这一工作，就有点像我们在cubic-graph-上的-NP-完全问题做的那样，要对更精细的子问题进行刻画。比如证明任意图上的 MAX CUT 是NP完全很容易，但是证明 cubic 图上的 MAX CUT 是NP完全就要难一些。同时任意图的子问题中的 quadratic graph 上的 MAX CUT 又显然是 trivial。因此证明了一大类物理系统是NP完全，不代表这些系统全都无法有效解决和数值计算，需要更多的工作来区分，其中到底哪些子问题是本质困难的。
最后的 subtlety 来自系统能量不是离散取值的，这一情况在量子系统中非常明显。对于一个格点量子模型，即使所有的哈密顿量参数都是整数，也无法保证对应的能量离散取值。在这种情形，似乎没有对 FPTAS 的明显阻止。对于这种系统，证明相应问题是APX完全的，才可以充分阻止 FPTAS。另一方面也要注意，量子图灵机在复杂度上和经典确定图灵机不等价，这方面还有很多问题待解决，因此我们讨论的量子问题的NP完全，仅指经典计算机模拟时的复杂度分析。
NP困难系统的特征
事实上，注意到NP困难系统的基态能量判别问题，可以被各种各样的所有的NP问题在多项式时间内归约到。这一事实已经在一定程度上给出了NP困难系统的特征。我们观察不同的NP完全问题，无论是计算机科学中的还是物理中的，都隐约包含着“无穷个”自由度输入这一特征。比如我们证明的 3D spin glass 系统在两层方格子上是NP完全的，其所包含的输入自由度，即是所有边上的 coupling 的取值可能是 \(\pm 1,0\)。而对于我们证明的 2D 有磁场的自旋系统，其磁场均匀，且所有的自旋耦合均相等，输入自由度来自于任意 planar graph。因此，任何一个NP完全问题，总要以某种形式接受包含有大量自然自由度的输入，否则很难想象，解决一个只依赖一个简单参数的问题都解决，可以导致形式多样的所有NP问题的解决。换句话说，NP完全问题的输入，是以某种形式 encoding 了所有的NP问题。这样解决了一个NP完全问题，那么对于这个NP完全问题的某类具体输入的解，就可以对应回某个具体的NP问题。
这一输入编码高自由度的特征，很具启发性。这也在一定程度上解释了，为何被证明是NP困难的物理系统，都是伴随着无序，要么就得要求哈密顿量作用的格点图任意。这都是为了可以在问题的输入中编码进更高的自由度，这两种例子也恰好对应了我们证明的两个NP完全物理系统。
从这个意义上说，一些物理学家希望尝试的圣杯，比如 fermion Hubbard model on 2D square lattice，很难被证明是NP困难的，因为该模型只有两个参数 \(U,\mu\)。我们无法想象输入只包含两个自由度的问题，可以对应到所有NP问题的解。另一方面，这不阻止我们去证明 Hubbard model 在任意 planar graph 上是NP困难的。（该问题似乎还没有证明，但很可能是对的。）问题在于，即使我们证明了任意2D lattice 上的 Hubbard model 是NP困难的，也没能完全阻止物理学家继续研究该模型。因为方格子这一更强的子问题，极大可能不是NP完全问题。
量子蒙特卡洛方法
现在我们以 quantum Monte Carlo 方法为例，具体看一下NP完全系统对于数值方法的适用有哪些影响。
sign problem is in NP-hard
这一部分思路参考了 [1]。事实上不需要考虑符号问题的解决，整个 QMC 就是 NP 困难的。否则我们可以把经典模型的自旋简单替换为 Pauli 矩阵，装作是量子问题来用 QMC 解决，既然3维经典自旋系统都是NP完全的，那么QMC一定是NP困难的。否则在极低温度使用 QMC 来求得系统能量的期望，就有超过一半的成功率回答对基态能量判别问题。根据 P＝BPP（这一点 [1] 没有提，但实际上是证明必不可少的条件），QMC 无法多项式时间得出能量期望，因此 QMC 是NP困难的。这一证明如此 trivial，但我觉得其贡献要比 [1] 的分离出符号问题更彻底。何必证明符号问题的解决是NP困难的，即使证明了，也还会有人说是否存在其他与现在不同的 QMC 实现方案，可以不这么处理符号问题，那证明就没用了。还不如直接简洁明快，对整个 QMC 直接盖棺论定，存在绕不过的NP困难，似乎是一个更强的结论。
[1] 中本来的处理，是考虑将 QMC 作为把符号问题的处理和对概率一直取正号的系统的经典 MC 两部分来解耦。利用三维经典spin glass的 QMC 计算，通过 coupling 恒为正的三维自旋系统存在有效的 MC 模拟，来说明本质的困难是在符号问题的部分。
事实上，何止 QMC，通过以上证明可以看出经典 MC 也是NP困难的。由此看出NP困难的物理系统，给数值方法解决问题的能力带来了很强的约束。
critical slowing down 和 sign problem 等价
事实上，通过以上3D spin glass 的 Monte Carlo 处理，我们发现 critical slowing down 和 sign problem 只不过是一个难度表现的两个侧面。如果用 classcial MC，阻止该NP完全系统有效近似的，是 MC 过程更新构型时面临的 slowing down。也即 energy landscape 使得 local update 很难有效的到达其他能量的极小值点，从而造成 correlation time 长度指数增加，阻止了 MC 在多项式时间的高效近似。而当我们用 QMC 来解决这个经典系统的时候，我们则面临了 sign problem，符号的涨落在指数量级，从而阻止了 QMC 的多项式时间的有效近似。
从这种视角来看，构型更新的 slowing down 和 QMC 中的 sign problem 实际上在某种程度上等价的，是同一种难度的两个侧面。可能有人会认为 critical slowing down 可以通过找到有效的 cluster update algorithm 来克服，因此不是本质的困难。实际上，这种认识是完全错误的。NP完全物理系统的存在，就保证了对于大量模型，不存在有效的集团更新方案。正如 sign problem 在某些特别的模型也可以巧妙避免一样，不能因为有算法可以解决一些子问题，就认为该问题的难度不本质。这也再次重复了上节的观点，单独证明 sign problem 的解决方案是NP困难的并没有抓住问题的重点。问题的重点在于，由于NP完全系统的存在， MC 本质上就是NP困难的。这一困难可以表现在 slowing down，也可以表现在符号问题，这只是本质难度的不同表现外化而已。从这个角度说，符号问题也没什么神秘之处，只是 critical slowing down 换了个马甲罢了。
Reference
- M. Troyer and U.-J. Wiese, Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations, Phys. Rev. Lett. 94, 170201 (2005).
EOF