Automated search for highly contextual Kochen-Specker proofs

技术摘要：高上下文相关性 Kochen-Specker 证明的自动化搜索

问题陈述
基于观测量的 Kochen-Specker (KS) 证明利用多比特泡利观测量的配置，这些配置被分组为“上下文”（一组相互对易的观测量），其乘积为 $\pm I^{\otimes n}$。这些证明展示了状态无关的量子上下文相关性（contextuality）。此类证明对实验噪声的鲁棒性通过每个上下文的可容忍误差 $\varepsilon$ 来量化，其中 $\varepsilon = 2d/|H|$，$d$ 是上下文度数（无法由任何经典赋值重现的最小上下文符号数量），$|H|$ 是总上下文数。

以往对高 $\varepsilon$ 证明的搜索很大程度上局限于“魔术集”（magic sets），即观测量位于偶数个上下文中，且负上下文为奇数个。虽然这保证了上下文相关性，但也将其限制在配置空间的狭窄区域内，例如 Peres-Mermin 方格（$\varepsilon \approx 0.33$）和 Mermin 五角星（$\varepsilon = 0.40$）便是其中的小型示例。本研究的目标是系统地搜索具有更高 $\varepsilon$ 值的配置，从而超越魔术集的约束。

方法论
作者利用了**超图文（hypergram）**的概念，这是一个由上下文超图 $(V, H)$ 和反对易图 $(V, G)$ 组成的抽象结构三元组。来自先前工作 [MG25a] 的一个关键理论见解是：上下文度数是超图文本身的性质，独立于具体的比特数或泡利标记。

为了优化搜索，作者提出了一个反转传统枚举顺序的流水线：

1. 图优先枚举： 作者不是先枚举超图再检查是否存在兼容的反对易图，而是首先枚举简单的、简化的反对易图 $G$。
2. 超图支撑（Hypergraph Support, $HS(G)$）： 对于每个图 $G$，他们构建超图支撑 $HS(G)$，它包含了所有可能的上下文（满足可赋值性所需奇偶条件的 $G$ 的独立集）。
3. 规范候选选择： 流水线并不测试 $HS(G)$ 的所有子集，而是检查每个图中的单个超图文 $(V, HS(G), G)$。这个“极大”配置被假设为能产生最高的 $\varepsilon$。
4. 搜索空间： 该流水线通过两个不同的来源进行了两轮搜索：
   • House of Graphs 数据库：13,864 个连通的、简化的、顶点数 $\le 30$ 的图。
   • 顶点传递图（vertex-transitive graphs）普查：所有顶点数 $\le 24$ 的此类图（18,948 个图），涵盖范围比 House of Graphs 子集更广。
5. 验证： 通过矩阵条件（在 $\mathbb{F}_2$ 上 $H \cdot G = 0$）检查可赋值性。使用 SAT 求解器（精确计算）或启发式求解器（针对大型实例）计算上下文度数。

主要贡献

1. 系统化搜索流水线： 本文建立了一个完整的、自动化的 KS 证明发现流水线，通过在由反对易图导出的抽象超图文层面进行操作，消除了搜索阶段对显式比特标记的需求。
2. 发现高 $\varepsilon$ 配置： 搜索到的配置显著超过了之前发表的记录 $\varepsilon = 0.424$（来自 [TLC22a]，该记录受限于魔术集）。
3. 结构性见解：
   • 线图（Line Graphs）： 作者证明（定理 4）基图 $H$ 的每一个完美匹配都构成了其线图 $L(H)$ 中的一个上下文。这解释了为什么线图经常产生高 $\varepsilon$ 配置，并将 Peres-Mermin 方格和 doily 识别为此类无限族中的首批成员。
   • 不相交并（Disjoint Unions）： 研究表明，不相交并图能产生更优的结果。由于不相交并中的上下文数量是乘性的，而观测量数量是加性的，通过堆叠小型、高性能图（如 Petersen 图或 $L(K_{3,3})$）的副本，可以极大地提高 $\varepsilon$。
4. 几何解释： 本文提供了对称极化空间（$W_n$）中顶层配置的有限几何描述，将其与特定的结构（如 ovoids、双曲二次型和 Fano 平面）联系起来。

结果
该流水线成功恢复了已知配置（Peres-Mermin 方格、Mermin 五角星、doily），并发现了新的、具有高度上下文相关性的配置：

• 打破记录的 $\varepsilon$： 找到的最佳配置是 3-Petersen 图（三个不相交的 Petersen 图副本），其 $\varepsilon = 0.707$。这超过了之前的记录 0.424 以及未发表的记录 0.5。
• 其他显著配置：
  • $3L(K_{3,3})$（三个不相交的 $K_{3,3}$ 线图副本）：$\varepsilon = 0.637$。
  • $2L(K_6)$：$\varepsilon = 0.612$。
  • $L(K_{5,5})$（Rook's graph）：$\varepsilon = 0.600$。
  • $L(C(10, \{1, 3\}))$：$\varepsilon = 0.500$（被识别为 [Mul25] 中发现的配置）。
• 数据库统计： 搜索覆盖了来自 House of Graphs 数据库的 13,864 个图和 18,948 个顶点传递图。只有极小比例的图产生了有效的、具有上下文相关性的超图文。结果证实，高对称性（顶点传递性）和特定的结构属性（作为线图或不相交并）与高 $\varepsilon$ 相关。

意义与主张
本文声称，通过将搜索重点从特定的量子配置转向底层的抽象超图文，可以发现具有显著更高噪声鲁棒性的 KS 证明。作者强调，图的不相交并是最大化 $\varepsilon$ 最有效的结构特征，因为它利用了上下文生成的乘性本质。

研究将 Peres-Mermin 方格和 doily 视为并非孤立的异常现象，而是由线图生成的无限族中的初始成员。此外，作者指出，虽然目前的搜索受限于计算能力（SAT 求解器在超过 ~1,000 个上下文时难以处理），但启发式方法表明，更大的配置（例如 $K_6 \square K_6$）可能会产生更高的 $\varepsilon$ 值，甚至可能趋近于 1。论文最后建议，未来的工作可以涉及使用 AI 来提出图族和猜想的自动化循环，尽管目前的结果是基于对现有数据库的人类引导式探索。