技术摘要：弱相互作用费米子累积量展开与多项式时间算法的收敛性

1. 问题陈述

本文解决了在固定逆温度 $\beta$ 下，估计弱相互作用费米子系统对数配分函数 $\log Z$ 的计算挑战。该系统由 $d$ 维晶格上的 $N$ 个费米子模组成，受哈密顿量 $H = H_0 + V$ 控制，其中 $H_0$ 是二次（自由）哈密顿量，$V$ 代表弱相互作用势。

尽管量子吉布斯采样（Quantum Gibbs sampling）最近已证明可以在多项式时间内制备此类系统的热态，但对于计算配分函数的具有多项式运行时间的严格数学类经典算法仍处于空白。现有的经典方法（如图表量子蒙特卡洛 QMC）依赖于马尔可夫链蒙特卡洛（MCMC）方法，其效率取决于未知的混合时间，这阻碍了提供严格的多项式时间保证。相反，严格的簇展开（cluster expansion）方法在历史上受到局限于高温度自旋系统或特定的非相互作用极限，无法直接应用于弱相互作用费米子，因为后者的无扰动态是一个相关的高斯态，而非积态（product state）。

目标是提供一种经典算法，能在多项式时间内将 $\log Z$ 的近似误差控制在 $\epsilon N$ 以内（即每个模的误差为 $\epsilon$），且运行时间相对于系统规模 $N$ 和逆精度 $1/\epsilon$ 为多项式级别。

2. 方法论

2.1 累积量展开与收敛性分析

作者从 $\log Z$ 的累积量展开式开始：
$$\log(Z/Z_0) = \sum_{s=1}^{\infty} \frac{(-1)^s}{s!} \sum_{P_1, \dots, P_s \in \mathcal{P}} v_{P_1} \dots v_{P_s} \int_{[0,\beta]^s} d\tau_1 \dots d\tau_s \, E_c(\{P_i, \tau_i\}_{i \in [s]})$$
其中 $E_c$ 表示连通部分的时间有序相关函数。标准的图表展开将 $E_c$ 表示为连通费曼图的求和。然而，此类图表的数量呈阶乘级增长 ($\sim (2s)!$)，导致逐项求值时具有拟多项式复杂度。

为了克服这一点，本文引入了一种树-行列式展开（tree-determinant expansion）。它将对连通费曼图的求和重新组织为对标记树（labeled trees）的求和（利用严谨量子场论中的树图恒等式）。具体而言，累积量被表示为：
$$E_c(\{P_i, \tau_i\}) = \sum_{T \in \mathcal{T}([s])} \sum_{\chi \in A(T)} \alpha_{T,\chi} \left( \prod_{(i,j) \in T} g_{\tau_i, \tau_j}(P_i, P_j, \chi_{ij}) \right) h_\tau(P_1, \dots, P_s, T, \chi)$$
这里的求和是对树 $T$ 而非图表进行的。树的数量按 $s^{s-2}$ 增长（根据凯莱公式），当结合 $1/s!$ 预因子时，其增长为指数级而非阶乘级。项 $h_\tau$ 封装了剩余的收缩项，表现为由非相互作用格林函数构造的矩阵行列式的线性组合。

2.2 收敛性证明

作者证明了当相互作用强度 $U$ 低于一个独立于 $N$ 的阈值 $C(\beta)$ 时，该级数呈指数级收敛。证明依赖于两个关键技术组件：

1. 行列式界限： 利用广义 Gram 不等式和特定的格林函数嵌入映射，他们建立了 $h_\tau$ 中出现的行列式的一致界限，表明这些行列式最多以指数级增长。
2. 可求和性： 通过利用相互作用势的 $L_V$-可求和性以及非相互作用格林函数的 $L_g$-可求和性（或指数衰减性），他们界定了对相互作用项 $P_1, \dots, P_s$ 的求和。树状结构使得这种求和可以通过局部因子的乘积进行界定，从而确保第 $s$ 阶项按 $N \cdot \rho^s$ 缩放，其中 $\rho < 1$。

2.3 通过重要性采样的随机算法

由于该级数呈指数级收敛，因此可以在阶数 $S = O(\log(1/\epsilon))$ 处截断。随后的挑战在于如何高效地评估截断后的求和。作者并未采用暴力求和，而是提出了一种随机重要性采样算法：

1. 树采样： 使用 Prüfer 编码均匀采样一个标记树 $T$。
2. 变量采样： 在给定树和虚时间的情况下，从与绝对贡献成正比的分布中采样相互作用项 $P_1, \dots, P_s$。由于树的结构，该分布在树上构成一个马尔可夫随机场（MRF），可以使用**置信传播（Belief Propagation, BP）**进行高效采样。
3. 估计量构建： 对于每个样本，计算一个无偏权重 $w_s$。最终的估计值是这些权重在多次采样下的平均值。

估计量的方差在相互作用较弱的条件下与 $N$ 独立，这确保了只需 $O(1/\epsilon^2)$ 个样本即可达到所需的精度。

3. 主要贡献与结果

3.1 主要定理

• 定理 1.1 (收敛性)： 确立了对于几何局部费米子哈密顿量，当相互作用强度低于一个与系统规模无关的阈值时，累积量展开呈指数级收敛。
• 定理 1.2 (有限温度算法)： 提供了一种随机经典算法，对于几何局部系统，能在 $\tilde{O}(N \epsilon^{-2})$ 时间内以至少 $2/3$ 的概率估计 $\log Z$ 至 $\epsilon N$ 的加性误差。对于平移不变系统，运行时间优化至 $\tilde{O}(\epsilon^{-2})$，与 $N$ 无关。
• 推论 1.3 (局部可观测量)： 通过利用对数配分函数作为生成函数，将该算法扩展到计算局部可观量的热期望值，运行时间为 $\tilde{O}(\epsilon^{-2})$，与系统规模无关。
• 定理 1.4 (一般相互作用)： 将结果推广到满足求和条件（$L_V$ 和 $L_g$）的长程相互作用，产生了一个多项式时间算法（尽管对 $N$ 的次数依赖高于严格局部情况）。

3.2 复杂度分析

• 查询复杂度： 在一般情况下，算法需要 $O(|\mathcal{P}|^2 \epsilon^{-2} \text{polylog}(1/\epsilon))$ 次查询；对于几何局部势，则需要 $O(N \epsilon^{-2} \text{polylog}(N/\epsilon))$ 次查询。
• 运行时间： 结合计算非相互作用格林函数的代价（一般为 $O(N^2 \text{polylog}(1/\epsilon))$，但对于有限范围的 $H_0$ 为 $O(\text{polylog}(N/\epsilon))$），总运行时间是 $N$ 和 $1/\epsilon$ 的多项式。
• 最优性： 文中指出，对于局部系统，其对 $N$ 的线性依赖关系本质上是优化的，因为读取哈密顿量本身就需要线性时间。

4. 意义与主张

本文声称提供了第一个用于计算弱相互作用费米子对数配分函数的多项式时间经典算法。其意义体现在以下领域：

1. 弥合物理学与严谨复杂性之间的鸿沟： 它成功地连接了受物理启发且缺乏严格运行时间保证的图表方法，与此前难以处理费米子基态相关性的严谨算法技术。
2. 通过抵消克服“符号问题”： 与可能发散的玻色子或经典系统中的摄动展开不同，作者证明了费米子反对易关系诱导的抵消作用，使得即使在低温度下也能存在正的收敛半径。
3. 与量子算法的比较： 结果表明，对于弱相互作用费米子，估计配分函数可能不存在超多项式级的量子优势，因为经典算法可以匹配近期量子吉布斯采样方法的多项式缩放。
4. 方法论创新： 将树-行列式展开与用于重要性采样的置信传播相结合，为评估量子多体系统的高阶摄动级数提供了一种新范式，避免了基于 MCMC 的图表 QMC 中固有的混合时间问题。

作者对零温应用保持谨慎，指出虽然其方法依赖于格林函数的衰减（这在有能隙系统中成立），但将算法扩展到基态领域仍需进一步研究。他们还澄清，其结果适用于弱相互作用机制，即相互作用强度相对于温度和非相互作用能隙较小，并且并不声称解决了通用的强相互作用情况。