Spectral Certificates and Non-commutative Sum-of-Squares Lower Bounds for Hamiltonians

技术摘要：谱证书与非交换求和平方（Sum-of-Squares）哈密顿量的下界

1. 问题陈述

本文解决的核心问题是估计 $k$-局部哈密顿量系统的基态能量（或通过符号翻转来估计最大能量），这一任务对于量子多体物理学至关重要，并且在复杂度类 QMA 中是完备的。作者关注两种特定的模型：

• 量子 $k$-自旋哈密顿量（Quantum $k$-spin Hamiltonians）： 半随机模型，其哈密顿量是带有高斯系数的有符号 $k$-局部泡利算符之和。
• 哈密顿量 $k$-XOR（Hamiltonian $k$-XOR）： 一种特定的模型，其哈密顿量是 $\pm 1$ 有符号 $k$-局部泡利投影算符之和。这作为经典 $k$-XOR 约束满足问题（CSP）的直接量子模拟。

本文研究了这些系统的平均情况复杂度，特别是证伪问题（refutation problem）：给定一个随机或半随机实例，能否高效地证明一个关于最大能量的上界（例如，证明能量接近 $1/2$ 而不是 $1$）？相反，本文通过构造某些哈密顿量，研究了最坏情况限制，在这些哈密里量中，标准的经典松弛技术（如 Sum-of-Squares）即使在高阶数下也无法提供良好的近似。

2. 研究方法

A. 通过哈密顿量 Kikuchi 矩阵进行谱证伪
为了解决半随机哈密顿量的平均情况证伪问题，作者将最初为经典 CSP 开发的 Kikuchi 矩阵 方法引入到量子设置中。

• 构造： 他们为哈密顿量 $H_I$ 定义了一个“第 $\ell$ 层” Kikuchi 矩阵 $K^{(\ell)}_I$。该矩阵构建在度数为 $\ell$ 的泡利算符空间上。其条目由泡利算符 $Q, R$ 的邻接性决定，其中 $Q^\dagger R = P$（$P$ 是哈密顿量中的一项），且它们的支撑集以特定方式（$\ell - k/2$）相交。
• 谱界限： 核心技术洞察是，最大能量 $\lambda_{\max}(H_I)$ 受限于该 Kikuchi 矩阵（具体为度正则化版本）的谱范数。
• 分析： 利用矩阵集中不等式（特别是针对 Rademacher 和高斯序列），他们证明了对于足够稠密的随机实例，Kikuchi 矩阵的谱范数紧密集中在 $1/2 + \epsilon$ 附近。这产生了一个高效可计算的证书（即谱范数），该证书可以作为有效的能量上界。

B. 非交换求和平方（ncSoS）框架
为了理解谱方法的局限性并建立下界，作者形式化了**非交换求和平方（ncSoS）**层级结构。

• 定义： ncSoS 将对密度矩阵的优化放宽为对“伪密度算符（pseudo-density operators）”的优化。这些算符满足直到度数 $d$ 的归一化和正定性约束，但不一定对应于物理态。
• 与 Kikuchi 的联系： 作者证明了他们的谱 Kikuchi 算法可以被一个度数为 $2\ell$ 的 ncSoS 证明所捕捉。这确立了 Kikuchi 方法本质上是针对这些特定哈密顿量的 ncSoS 层级的程序化简化。
• 提升下界： 他们展示了如何将经典的 SoS 下界“提升”到 ncSoS 设置中。通过将经典 $k$-XOR 实例嵌入到交换哈密顿量中（特别是在 $Z$ 基底中），他们表明如果一个经典实例对于 SoS 是困难的，那么对应的哈密顿量对于 ncSoS 也是困难的。

C. XZ-$k$-XOR 模型
为了研究真正的量子硬度（超越交换哈密顿量），作者引入了 XZ-$k$-XOR 模型，该模型结合了两个经典的 $k$-XOR 实例，一个在 $X$ 基底，一个在 $Z$ 基底。

• 证伪逻辑： 他们将该模型的证伪特征化为源自单基底内的经典 XOR 证伪，或是源自 $X$ 与 $Z$ 项之间的反对易关系（anticommutation relations）。
• 构造： 他们构造了一族基于量子 Tanner 代码（NLTS 哈密顿量）并经过修改以包含 NP-hard 线性系统 PCP 的 XZ-$k$-XOR 哈密顿量。

3. 主要结果

结果 1：半随机哈密顿量的谱证伪（定理 1.3）
对于任何常数 $\ell$，存在一个运行时间为 $n^{O(\ell)}$ 的经典谱算法，输出一个证书 $algval(H_I)$。

• 保证： 对于任何实例，$algval(H_I) \ge \lambda_{\max}(H_I)$。
• 准确度： 如果项数 $|H|$ 为 $\Omega(n) \cdot \binom{n}{\ell}^{k/2-1} \log(n) \cdot \epsilon^{-4}$，则对于随机实例，以高概率有 $algval(H_I) \le 1/2 + \epsilon$。
• 意义： 这为半随机量子 $k$-自旋和 $k$-XOR 哈密顿量提供了高效的证伪方法，匹配了已知于经典 $k$-XOR 证伪的权衡。

结果 2：具有 ncSoS 下界的 NP-hard NLTS 哈密顿量（定理 1.5）
作者构造了一族同时满足以下三个属性的交换 XZ-$k$-XOR 哈密顿量：

1. NLTS 属性： 所有低能态（在距最大能量一个常数间隔内）都需要深度为 $\Omega(\log n)$ 的量子电路。
2. NP-困难性： 区分最大能量 $\le \alpha$ 与 $\ge \beta$（其中常数 $1/2 \le \alpha < \beta \le 1$）是 NP-困难的。
3. ncSoS 完整性间隙（Integrality Gap）： 度数为 $\Omega(n)$ 的 ncSoS 放宽值为 $1$，而真实的最大能量被限制在远离$1$ 的地方。

• 意义： 这表明 NLTS 哈密顿量的复杂度对于强大的 ncSoS 层级也是稳健的，后者是一种比低深度电路描述更宽松的经典描述方法。

结果 ：随机哈密顿量的 ncSoS 界限（定理 1.6）
对于完全随机的 $k$-XOR 哈密顿量（其中反对易对非常丰富）：

• 弱证伪： 度数为 $2k$ 的 ncSoS 放宽可以证明一个大约为 $1/2 + \frac{1}{2}\sqrt{1/3 + n/|H|}$ 的上界。这打破了在交换情况下存在的“完美完备性（perfect completeness）”障碍（值等于 1），利用反对易性推导出了证伪。
• 下界： 尽管存在反对易性，度数为 $\Omega(\ell)$ 的 ncSoS 放宽值仍至少为 $1/2 + \frac{1}{2 \cdot 3^k} - o(1)$。
• 意义： 这证明了随机哈密顿量存在常数级的完整性间隙，表明即使在稀疏机制下，ncSoS 也无法实现强证伪（接近 $1/2$），尽管它可以检测出缺乏完美完备性的情况。

4. 意义与主张

本文声称弥合了平均情况约束满足问题与量子哈密顿量复杂度之间的鸿沟。

• 算法贡献： 它将状态最先进的 Kikuchi 矩阵证伪技术从经典 CSP 扩展到量子哈密顿量，为半随机量子 $k$-自旋模型提供了首个高效的谱证书。
• 理论洞察： 它建立了 Kikuchi 矩阵方法与非交换求和平方（ncSoS）层级之间的形式等价性，阐明了这些量子优化问题的“计算速度极限”。
• 复杂度图景： 通过构造既对低深度电路（NLTS）困难又对高阶 ncSoS 放宽困难的哈密顿量，这项工作提供了证据，表明局部哈密顿量的复杂度在不同的经典描述范式下都是稳健的。
• 局限性： 作者谦虚地指出，他们的技术（由 ncSoS 捕捉）不足以在亚常数能量机制下（类似于 SYK 等模型的统计物理方法）获得精确的定量结果，并且他们对随机哈密顿量的硬度结果由于完整性间隙的存在，仅限于弱证伪。

这项工作并非提出用于实验实现的物理新模型，而是通过分析现有的理论模型（量子 $k$-自旋、NLTS）的计算复杂度，以更好地理解可计算与不可计算量子系统的边界。