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

技術要約：量子 $n$ 彩色はすべての $n \geq 3$ に対して決定不能である

問題設定
本論文は、量子 $n$ 彩色（quantum $n$-coloring）の決定問題を扱う。有限で単純な無向グラフ $G$ が与えられたとき、この問題は、$G$ の $n$ 彩色ゲームに対して「完全な量子戦略」が存在するかどうかを問うものである。代数的には、これは $G$ が量子 $n$ 彩色を認めるかどうかの判定に対応する。ここで、量子 $n$ 彩色とは、各頂点 $u \in V(G)$ に対して、有限次元行列代数 $\mathbb{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$ である。

本研究以前には、同期型非局所ゲームおよびSlofstraの線形システムゲームからの帰着を通じて、量子3-彩色が決定不能であることが確立されていた。しかし、$n \geq 4$ のすべてのケースにおける決定可能性のステータスは未解決の問いであった。

手法
著者らは、既知の量子3-彩色の決定不能性をすべての $n \geq 3$ へと拡張するために、**多対一還元（many-one reduction）**を採用している。手法の核心は、任意のグラフ $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)$ は3つの頂点の集合 $\{(u,1), (u,2), (u,3)\}$ という「ファイバー（fibre）」に置き換えられる。
• $\vee$ は**結合（join）**操作を表す。グラフ $G'$ は、デカルト積とサイズ $n-3$ のクリーク（完全グラフ）との結合によって形成される（頂点は $4, \dots, n$ とラベル付けされる）。

著者らは、補題 3.1 を通じて、等価関係 $G \xrightarrow{q} K_3 \iff G' \xrightarrow{q} K_n$ を証明している。その方向性は以下の通りである：

1. 順方向 ($\Rightarrow$): $G$ の量子3-彩色が与えられたとき、著者らは $G'$ の量子 $n$-彩色を構成する。既存の射影を利用し、インデックスを法3でシフトさせることで $G'$ のファイバー頂点に射影を割り当てる。クリーク $K_{n-3}$ には、制約を満たすために特定の色の単位行列（identity matrices）を割り当てる。
2. 逆方向 ($\Leftarrow$): $G'$ の量子 $n$-彩色が与えられたとき、著者らは $G$ の量子3-彩色を復元する。任意の頂点 $v$ のファイバーと $K_{n-3}$ クリークによって形成されるクリーク構造を分析することで、ファイバー内の射影の和が特定の頂点 $v$ に依存しないことを示す。さらに、少なくとも一つの色 $i^*$ について、「余剰」射影（$K_{n-3}$ に関連するもの）が単位行列ではないことを証明し、それによって有効な3-彩色へと制限された部分空間上の量子 $n$-彩色を導き出す。

主な貢献と結果

• 決定不能性の一般化: 主要な結果（定理 3.2）は、量子 $n$-彩色決定問題がすべての固定された整数 $n \geq 3$ に対して決定不能であることを確立した。
• 初等的な還元: 本論文は、$n=3$ のケースとそれより高いすべての $n$ の間の溝を埋める、単一の多項式時間計算可能な還元を提供している。
• 堅牢性: この証明は、標準的な有限次元量子モデルと、量子交換演算子モデル（投影が任意の、おそらく無限次元のヒルベルト空間上で作用するモデル）の両方に適用される。

意義と主張
著者らは、本研究を Harris [9]、Mančinska [4]、Culf [2] による先行研究の決定的な拡張として位置づけている。その意義は、量子彩色ゲームの決定可能性の空白を埋めたことにある。

本論文は、結果を**量子ホモモルフィズム（quantum homomorphisms）**というより広い文脈の中に位置づけて結論づけている。量子 $n$-彩色は、グラフ $G$ から完全グラフ $K_n$ への量子ホモモルフィズムの存在と同値であるため、著者らは量子 $H$-彩色に関する一般的な複雑性について以下の予想を提示している：

• 予想 4.1: すべての非二部グラフ $H$ について、量子 $H$-彩色は決定不能である。

著者らは、二部グラフ $H$ の場合は（古典的な彩色に帰着するため）決定可能であり、奇数サイクルについては決定不能である一方で、非二部グラフ全般に関するケースは依然として研究領域であることを述べている。本論文は、量子設定における潜在的な「Hell–Nešetřil 分岐（dichotomy）」に向けた基礎的な一歩となるものである。