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

技術要約：結合スキームにおけるシュライバー・デルスアルテ硬性（Schrijver–Delsarte Rigidity）と量子グラフ準同型の決定不能性

問題設定
本論文は、量子グラフ準同型問題、すなわち $\text{CSP}_q(G')$ の計算複雑性に焦点を当てている。固定されたターゲットグラフ $G'$ が与えられたとき、この問題は、入力グラフ $G$ が $G'$ への量子準同型を許容するかどうかを問うものである。古典的なバージョンのこの問題はよく理解されている（非二部グラフの場合はNP完全、二部グラフの場合は多項式時間）。しかし、量子の景観はまだ十分に解明されていない。制約のない量子戦略については、$MIP^* = RE$ 定理により、問題がRE完全（再帰的に列挙可能完全）であることが知られている。しかし、特定の非一様（non-uniform）なターゲットグラフに対してRE完全性を確立するには、「可換性ガジェット（commutativity gadgets）」、すなわち量子戦略に古典的（非文脈的）に振る舞うことを強制するか、あるいは既知の困難な問題からの還元を可能にする構造の存在を証明する必要がある。

著者らは、結合スキーム（association schemes）から派生した、クネーザーグラフ（Kneser graphs）、$q$-クネーザーグラフ、$q$-グラスマングラフの補グラフ、およびジョンソングラフ、グラスマングラフ、ハムミンググラフの補グラフを含む特定のグラフ族を分類するための体系的なアプローチを展開している。中心となる課題は、これらのグラフがいつ可換性ガジェットを保持するかを決定することであり、これは量子多項式（quantum polymorphisms）の理論において、すべての量子多項式が非文脈的（non-contextual）であることを証明することと同値である。

手法
本論文は、量子多項式の非文脈性を確立するためのスペクトル的手法を開発している。このアプローチは、以下の3つの理論的柱を組み合わせている：

1. シュライバーの $\theta$ と射影パッキング（Projective Packings）： 著者らは、独立数 $\alpha(G)$ を上界とする、ロバス・テータ関数 $\vartheta(G)$ の強化版であるシュライバーのパラメータ $\vartheta^-(G)$ を利用している。彼らは、$\vartheta^-(G)$ が射影パッキング数 $\alpha_p(G)$ も上界となるというロバートソンの結果を利用しており、さらに $\alpha_p(G)$ は量子独立数 $\alpha_q(G)$ を上界とする。彼らの手法の核心は、これらの境界がタイト（$\alpha(G) = \alpha_p(G) = \vartheta^-(G)$）である場合に依存している。
2. 硬性と等価性の解析（Rigidity and Equality Analysis）： 境界がタイトである場合、著者らはこの等価性を証跡する「証明書（certificate）」行列の構造を分析する。彼らは、もしグラフが特定の種類の「シュライバー硬性（Schrijver-rigid）」を持つ表現を認めるならば、完全な量子戦略を定義する射影演算子は制限された部分空間（証明書の核）内に存在しなければならないことを証明する。この制限は、射影演算子間の線形恒等式を強制する。
3. タメな離散表現（Tame Disjointness Representations）と結合スキーム： スペクトル条件をチェック可能な基準へと翻訳するために、著者らは「タメな離散表現」を導入している。これは、グラフの頂点から特徴集合への単射写像であり、隣接する頂点は互いに素な集合に写される。彼らは、表現が「シュライバー硬性」を持つと定義しており、これは最適なシュライバー証明書の核が、その表現の包含空間と一致することを意味する。
   • 決定的なことに、結合スキーム（ジョンソン、グラスマン、ハムミング）に由来するグラフについて、著者らはシュライバー硬性が「デルスアルテ硬性（Delsarte-rigidity）」と等価であることを証明している。デルスアルテ硬性は、ボーーズ・メスナー代数（Bose–Mesner algebra）の線形計画法（LP）の枠組み内で完全に定式化された条件であり、スキームの固有値行列が与えられれば計算量的に検証可能である。
   • さらに、グラフが「タメな」シュライバー硬性を持つ表現を持つ場合、スペクトル制約から導かれる線形恒等式によって、量子多項式におけるすべての射影演算子が可換（非文脈的）になることが強制されることを示している。

主要な貢献と結果
本論文の主要な貢献は、古典的な計量結合スキームから派生したいくつかのグラフ族によってパラメータ化された量子準同型問題のRE完全性を証明したことである。

• 主定理 (Theorem 1.1): 以下のグラフのいずれかへの入力グラフの量子準同型の存在を判定する問題がRE完全であることを、著者らは証明している：

  • $n > 2k \ge 2$ であるクネーザーグラフ $KG(n, k)$。
  • $n > 2k \ge 4$ であるジョンソングラフの補グラフ $\overline{J(n, k)}$。
  • $n > 2k \ge 2$ かつ $q$ が素数冪である $q$-クネーザーグラフ $KG_q(n, k)$。
  • $n > 2k \ge 4$ かつ $q$ が素数冪であるグラスマングラフの補グラフ $\overline{J_q(n, k)}$。
  • $d \ge 2$ かつ $q \ge 3$ であるハムミンググラフの補グラフ $\overline{H(d, q)}$。

• 未解決問題の解決： この結果は、「奇数グラフ（odd graphs）」（$O_n = KG(2n-1, n-1)$）の複雑性の問題を解決した。これは、可換性ガジェットの存在がこれまで未解決であったグラフクラスである。著者らは、オラクル設定および非オラクル設定の両方において、これらのグラフに対するRE完全性を確立している。

• 技術的枠組み： 本論文は、スペクトルグラフ理論（シュライバーの境界）と結合スキームの代数的理論（デルスアルテのLP境界）の間の架け橋を築いている。これらの対称的な構造においては、非文脈性のための複雑なSDP条件が、スキームの固有値に関するLP条件のチェックへと簡約できることを示している。

意義と主張
本論文は、グラフ準同型問題を多項式時間で解けるものとRE完全なものへと二分化することを目指す「量子ヘル・ネシェトリル分類（quantum Hell–Nešetřil classification）」に向けた大きな進展であると主張している。可換性ガジェットを保証するスペクトル基準（シュライバー硬性）を提供することで、著者らは新しいグラフ族を分析するための体系的なツールを提示している。

しかし、著者らは自身のメソッドの範囲について謙虚である。彼らは、自身のスペクトル的アプローチがRE完全な問題の全貌を捉えているわけではないことを明示的に述べている。彼らは以下の反例を挙げている：

• ダイヤモンドグラフやモザースピンル（Moser spindle）のようなグラフは、RE完全であるが、可換性ガジェットを持たない（したがって非文脈性条件を満たさない）。
• 長さ5以上の奇数サイクルのようなグラフは、可換性ガジェットを持つが、シュライバーの境界がタイトではないため、スペクトル基準を満たさない。

したがって、著者らは、完全な分類には、スペクトル硬性のみに頼るのではなく、コンテクスト性分岐（contextuality bifurcations）などの組合せ論的手法とスペクトル論的議論を組み合わせることが必要になるであろうと結論付けている。本研究は、新しい実験プロトコルを提案するものではなく、特定のグラフ準同型ゲームにおけるもつれ（entanglement）の計算能力を理解するための厳密な理論的枠組みを提供するものである。