Quantum n-coloring is undecidable for every n $\ge$ 3

技术摘要：量子 n-着色问题对于所有 n ≥ 3 都是不可判定的

问题陈述
本文研究了量子 n-着色（quantum n-coloring）的判定问题。给定一个有限、简单、无向图 $G$，该问题询问是否存在一个针对图 $G$ 的 $n$-着色游戏的“完美量子策略”。在代数层面，这对应于确定 $G$ 是否允许一个量子 $n$-着色，其定义为为每个顶点 $u \in V(G)$ 分配有限维矩阵代数 $C^{d \times d}$ 中的投影算子 $\{P_{u,i}\}_{i=1}^n$，满足：

1. 完备性（Completeness）： 对于每个顶点 $u$，$\sum_{i=1}^n P_{u,i} = I$。
2. 正交性（Orthogonality）： 对于每条边 $u \sim v$ 以及每个颜色 $i$，满足 $P_{u,i} P_{v,i} = 0$。

在此项工作之前，已有研究证明了量子 3-着色是不可判定的（通过向同步非局域游戏和 Slofstra 的线性系统游戏归约）。然而，对于所有 $n \geq 4$ 的可判定性状态仍是一个开放问题。

方法论
作者采用了一种多对一归约（many-one reduction）的方法，将已知的量子 3-着色不可判定性扩展到所有 $n \geq 3$ 的情况。该方法的核心是一种特定的图变换，它将任意图 $G$ 映射到一个新图 $G'$，使得 $G$ 是量子 3-可着色的充要条件是 $G'$ 是量子 $n$-可着色的。

该变换定义为：
$$G' := (G \square K_3) \vee K_{n-3}$$
其中：

• $\square$ 表示笛卡尔积（Cartesian product）。在 $G \square K_3$ 中，每个顶点 $u \in V(G)$ 被替换为一个由三个顶点组成的“纤维”（fibre）$\{(u,1), (u,2), (u,3)\}$。
• $\vee$ 表示连接（join）操作。图 $G'$ 是通过将上述笛卡尔积与一个大小为 $n-3$ 的团（clique）进行连接而形成的（顶点标记为 $4, \dots, n$）。

作者通过两个方向证明了等价关系 $G \xrightarrow{q} K_3 \iff G' \xrightarrow{q} K_n$（引理 3.1）：

1. 正向方向 ($\Rightarrow$)： 给定 $G$ 的一个量子 3-着色，作者构造了 $G'$ 的一个量子 $n$-着色。他们利用现有的 $G$ 的投影，并通过对索引取模 3 来为 $G'$ 中的纤维顶点分配投影。团 $K_{n-3}$ 被分配平凡投影（特定颜色的单位矩阵）以满足约束。
2. 反向方向 ($\Leftarrow$)： 给定 $G'$ 的一个量子 $n$-着色，作者从中恢复出 $G$ 的一个量子 3-着色。通过分析任何顶点 $v$ 的纤维与 $K_{n-3}$ 团所构成的团结构，他们证明了纤维内投影之和与特定顶点 $v$ 无关。他们进一步证明，对于至少一个颜色 $i^*$，“剩余”投影（与团 $K_{n-3}$ 相关）不是单位矩阵，从而允许在某个子空间上将该 $n$-着色限制为有效的 3-着色。

主要贡献与结果

• 不可判定性的泛化： 主要结果（定理 3.2）确立了对于每一个固定的整数 $n \geq 3$，量子 $n$-着色判定问题都是不可判定的。
• 基础归约： 本文提供了一个单一的、多项式时间内可计算的归约，填补了 $n=3$ 情况与所有更高阶 $n$ 之间的空白。
• 鲁棒性： 该证明对于标准的有限维量子模型以及量子交换算子模型（quantum commuting-operator model，其中投影作用在任意的、可能是无限维的希尔伯特空间上）均成立。

意义与主张
作者将这项工作定位为对 Harris [9]、Mančinska [4] 和 Culf [2] 先前结果的决定性扩展。其意义在于填补了量子着色游戏的判定性空白。

论文最后将这些结果置于更广泛的量子同态（quantum homomorphisms）背景下。由于量子 $n$-着色等价于存在一个到完全图 $K_n$ 的量子同态，作者提出了一个关于一般量子 $H$-着色复杂度的猜想：

• 猜想 4.1： 对于每个非二部图 $H$，量子 $H$-着色是不可判定的。

作者指出，虽然该问题对于二部图 $H$ 是可判定的（可归约为经典着色），且对于奇圈是不可判定的，但对于非二部图的一般情况仍是一个开放的研究领域，本文为实现潜在的量子“Hell–Nešetřil 二分性”（Hell–Nešetřil dichotomy）提供了基础性的一步。