論文要約：素数次数の強正則グラフを区別する量子ウォーク特性多項式

著者: Diego Gerardo Roldán (コロンビア大学国立コロンビア大学)
日付: 2026 年 4 月 3 日
主題: 量子ウォーク、強正則グラフ、グラフ同型判定、巡回グラフ、離散フーリエ変換

1. 問題の背景と目的

グラフ同型判定問題は計算機科学における重要な未解決問題の一つであり、特に強正則グラフ（Strongly Regular Graphs: SRGs）は、スペクトル法（固有値に基づく手法）に基づくアルゴリズムにとって最も困難なインスタンスとして知られています。
従来の古典的な隣接行列のスペクトル（固有値の集合）は、同じパラメータ $(n, k, \lambda, \mu)$ を持つ非同型な強正則グラフを区別することができません（これらは「共スペクトル」であるため）。

本論文の目的は、量子ウォーク特性多項式（Quantum Walk Characteristic Polynomial）$\chi_q(G, \lambda)$ が、素数次数 $p$ を持ち、接続次数 $k \ge 6$ の強正則グラフのクラスにおいて、同型不変量として完全である（つまり、このクラス内の任意の 2 つのグラフが同型であることと、その量子ウォーク特性多項式が一致することは同値である）ことを証明することです。

2. 主要な手法と理論的枠組み

本証明は、線形代数、$\mathbb{Z}_p$ 上の離散フーリエ変換（DFT）、および Turner の定理（素数次数の巡回グラフに関する古典的定理）の 3 つのステップで構成されます。

2.1 量子ウォーク演算子のブロック対角化

グラフ $G$ 上の量子ウォーク演算子 $U_G$ は、コイントス（Grover coin）とシフト演算子の積として定義されます。

• 手法: グラフが素数次数 $p$ の巡回グラフ（Cayley graph）であるという性質を利用し、$\mathbb{Z}_p$ 上の離散フーリエ変換 $F$ を用いて $U_G$ を変換します。
• 結果: $U_G$ は $p$ 個の $k \times k$ ブロック $U_G^{(j)}$ にブロック対角化されます（$j=0, \dots, p-1$）。
  $$F U_G F^\dagger = \bigoplus_{j=0}^{p-1} U_G^{(j)}$$
  このブロック分解により、大域的多項式の問題が $p$ 個の局所的な問題に分解されます。

2.2 特性多項式の明示的公式

各ブロック $U_G^{(j)}$ の特性多項式 $\chi_q(U_G^{(j)}, \lambda)$ について、以下の明示的な公式が導かれます。
$$\chi_q(U_G^{(j)}, \lambda) = (\lambda - 1)^{\frac{k-2}{2}} (\lambda + 1)^{\frac{k-2}{2}} \left( \lambda^2 - 2 \frac{\hat{A}_G(j)}{k} \lambda + 1 \right)$$
ここで、$\hat{A}_G(j)$ はグラフ $G$ の隣接行列の $j$ 番目のフーリエ係数（接続集合 $S$ のフーリエ変換）です。

• 重要な洞察: この公式から、$\pm 1$ 以外の固有値の実部を調べることで、フーリエ係数 $\hat{A}_G(j)$ を一意に復元できることが示されます。
• 条件 $k \ge 6$: この条件は、固有値が $\pm 1$ 以外の複素数（$e^{\pm i\theta}$）を持つことを保証し、フーリエ係数の復元を可能にするために必要です（$k=2$ の場合は別途処理可能）。

2.3 フーリエ係数と接続集合の復元

• 多項式の一意分解: 全体の特性多項式 $\chi_q(G, \lambda)$ は、各ブロックの特性多項式の積です。強正則グラフの性質により、$\hat{A}_G(j)/k$ は 2 つの制限固有値のいずれかの値しか取りません。$\mathbb{C}[\lambda]$ における多項式の一意分解性により、全体の多項式が一致すれば、各ブロックごとの二次因子（$\lambda^2 - 2c_j \lambda + 1$）も一致しなければなりません。
• 逆変換: 各 $j$ に対して $\hat{A}_G(j)$ が復元されれば、逆離散フーリエ変換（式 1）を用いて接続集合 $S$ を完全に復元できます。
• Turner の定理: 素数次数の巡回グラフにおいて、接続集合 $S$ が一致すれば（あるいは $S$ が乗法的に等価であれば）、グラフは同型です。

3. 主要な結果

定理 1.1（主定理）:
$p$ を素数とし、$G, G'$ を次数 $k \ge 6$ の強正則グラフとする。このとき、
$$G \cong G' \iff \chi_q(G, \lambda) = \chi_q(G', \lambda)$$
が成り立つ。

数値検証:
Paley グラフ（$p \in \{13, 17, 29, 41\}$）に対して Python による実装を行い、以下の検証を行いました。

1. ブロック対角化の精度確認。
2. 明示的公式（式 6）の妥当性確認。
3. フーリエ係数からの接続集合 $S$ の完全な復元。
   すべてのテストで、理論と数値計算が一致しました。

4. 意義と貢献

1. グラフ同型判定の決定性:
   素数次数の強正則グラフのクラスにおいて、量子ウォークスペクトルを用いることで、グラフ同型判定が多項式時間で決定可能であることを示しました。これは、Babai による一般的な準多項式時間アルゴリズム（2016 年）に依存せず、より構造的な解決策を提供します。

2. 古典スペクトルとの比較:
   古典的な隣接行列のスペクトルでは区別できないグラフを、量子ウォーク特性多項式は完全に区別できることを証明しました。これは、量子ウォークが古典的なスペクトル情報よりも厳密に多くの情報を含んでいることを示す理論的根拠となります。

3. 構成的可能性:
   証明は構成的であり、量子ウォーク演算子のスペクトルから接続集合を直接復元する手順を含みます。

4. 量子計算への応用:
   $U_G$ は $O(n)$ 個の量子ゲートで実装可能であるため、このスペクトル識別問題は近未来の量子ハードウェアでも実行可能です。古典的な多項式時間アルゴリズムに対して、量子優位性が達成できるかどうかが今後の課題として提起されています。

5. 今後の課題

• 合成次数への拡張: 現在の証明は $\mathbb{Z}_p$ の直交性と素数次数における一意分解性に依存しているため、次数が合成数（$n=pq$や$n=p^2$）の場合への拡張には新たなアイデアが必要です。
• 頂点推移的でないグラフ: 本研究は Cayley グラフ構造（頂点推移性）に本質的に依存しています。頂点推移的でない強正則グラフに対しても量子ウォーク特性多項式が完全な同型不変量となるかは未解決です（$n \le 10$ の実験では反例は見つかりませんでした）。

結論

本論文は、量子ウォークの特性多項式が、素数次数の強正則グラフの同型判定を完全に解決する強力な不変量であることを数学的に証明しました。この結果は、代数組合せ論と量子計算の交差点において、構造的な洞察に基づいた効率的なアルゴリズムの可能性を示唆する重要な貢献です。