Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism

技术摘要：关联方案中的 Schrijver–Delsarte 刚性与量子图同态的不可判定性

问题陈述
本文探讨了量子图同态问题的计算复杂度，记作 $\text{CSP}_q(G')$。给定一个固定的目标图 $G'$，该问题询问输入图 $G$ 是否存在一个到 $G'$ 的量子同态。虽然经典版本的该问题已有成熟的研究（对于非二部目标图是 NP-完全，对于二部目标图是多项式时间可解），但量子领域的图景尚不明确。已知对于不受限制的量子策略，由于 $MIP^* = RE$ 定理，该问题是 RE-完全（递归可枚举完全）的。然而，要为特定的、非均匀的目标图建立 RE-完全性，需要证明“交换性小部件”（commutativity gadgets）的存在——这类结构能迫使量子策略表现得像经典（非上下文）行为，或者允许从已知的硬问题进行归约。

作者专注于通过一种系统化的方法，对源自关联方案（包括 Kneser 图、$q$-Kneser 图，以及 Johnson、Grassmann 和 Hamming 图的补图）的特定图族进行复杂度分类。核心挑战在于确定这些图何时拥有交换性小部件，根据量子多态（quantum polymorphisms）理论，这等价于证明该图的所有量子多态都是非上下文的（non-contextual）。

方法论
本文开发了一种谱方法来建立量子多态的非上下文性。该方法结合了三个理论支柱：

1. Schrijver 的 $\theta$ 与射影填充（Projective Packings）： 作者利用了 Schrijver 参数 $\vartheta^-(G)$，它是 Lovász $\theta$ 函数的一种加强版本，用于上界化独立数 $\alpha(G)$。他们利用 Roberson 的结果，即 $\vartheta^-(G)$ 也上界化了射影填充数 $\alpha_p(G)$，而 $\alpha_p(G)$ 进而上界化了量子独立数 $\alpha_q(G)$。他们方法的核心在于这些界限达到紧致（tight）的情况（即 $\alpha(G) = \alpha_p(G) = \vartheta^-(G)$）。
2. 刚性与等式分析： 当界限紧致时，作者分析了见证这一等式的“证书”（certificate）矩阵的结构。他们证明，如果一个图具有特定类型的“Schrijver-刚性”表示，那么定义任何完美量子策略的投影算子必须位于一个受限的子空间内（即证书的核）。这种限制强制要求投影算子之间存在线性恒等关系。
3. 驯服不交表示（Tame Disjointness Representations）与关联方案： 为了将谱条件转化为可检查的准则，作者引入了“驯服不交表示”。这些是从图顶点到特征集的单射映射，其中相邻顶点映射到不相交的集合。他们定义一个表示为 Schrijver-刚性，如果最优 Schrijver 证书的核与该表示的关联空间一致。
   • 至关重要的是，对于源自关联方案（Johnson、Grassmann、Hamming）的图，作者证明了 Schrijver-刚性等价于 Delsarte-刚性。Delsarte-刚性是在 Bose–Mesner 代数的线性规划（LP）框架内完全可以表述的条件，给定方案的特征值矩阵，该条件是计算可验证的。
   • 他们进一步表明，如果一个图具有“驯服”的 Schrijver-刚性表示，那么由谱约束导出的线性恒等式将迫使量子多态中的所有投影算子都相互交换（非上下文）。

主要贡献与结果
主要贡献在于证明了由经典度量关联方案衍生的若干图族参数化的量子同态问题是 RE-完全的。

• 主定理 (Theorem 1.1)： 作者证明，判定输入图是否包含到以下任一图的量子同态是 RE-完全的：

  • Kneser 图 $KG(n, k)$，其中 $n > 2k \ge 2$。
  • Johnson 图的补图 $\overline{J(n, k)}$，其中 $n > 2k \ge 4$。
  • $q$-Kneser 图 $KG_q(n, k)$，其中 $n > 2k \ge 2$ 且 $q$ 为素幂。
  • Grassmann 图的补图 $\overline{J_q(n, k)}$，其中 $n > 2k \ge 4$ 且 $q$ 为素幂。
  • Hamming 图的补图 $\overline{H(d, q)}$，其中 $d \ge 2$ 且 $q \ge 3$。

• 解决开放问题： 本研究解决了“奇图”（odd graphs, $O_n = KG(2n-1, n-1)$）的复杂度问题，这是一类此前关于是否存在交换性小部件仍未解决的图类。作者在有预言机（oracular）和无预言机（non-oracular）设置下均确立了其 RE-完全性。

• 技术框架： 本文在谱图论（Schrijver 界限）与关联方案的代数理论（Delsarte LP 界限）之间建立了桥梁。他们展示了对于这些对称结构，用于非上下文性的复杂 SDP 条件可以简化为对方案特征值的 LP 条件的检查。

意义与主张
本文声称在迈向“量子 Hell–Nešetřil 分类”方面取得了显著进展，该分类旨在将图同构问题划分为多项式时间可解和 RE-完全两类。通过提供一个保证 RE-完全性的谱准则（Schrijver-刚性），作者为分析新的图族提供了系统化工具。

然而，作者对其方法的适用范围保持审慎。他们明确指出，其谱方法并不能涵盖整个 RE-完全问题的全貌。他们提供了反例：

• 某些图（如钻石图或 Moser 纺锤体）是 RE-完全的，但不具备交换性小部件（因此不满足非上下文条件）。
• 其他图（如长度 $\ge 5$ 的奇圈）具备交换性小部件，但由于 Schrijver 界限在它们上面不紧致，因此无法通过谱准则。

因此，作者得出结论，全面的分类可能需要将他们的谱论证与组合方法（如上下文分叉/contextuality bifurcations）相结合，而不仅仅依赖于谱刚性。这项工作并非提出新的实验协议，而是为理解特定图同构博弈中纠缠的计算能力提供了一个严谨的理论框架。