Complex-Valued-Matrix Permanents: SPA-based Approximations and Double-Cover Analysis

技術要約：複素行列のパーマネント：SPAに基づく近似と二重被覆解析

問題設定
複素値行列のパーマネントは、ボソンサンプリング（量子超越性の実証に向けた候補）や確率的推論などの分野における基本的な量である。非負の実値行列のパーマネントは、すでに大規模な次元において計算量的に困難であることが知られているが、複素値の場合は、パーマネントの総和における実部と虚部の項間の「強め合いと打ち消し合い（干渉）」により、さらなる課題が生じる。和積アルゴリズム（SPA）およびベテ近似（Bethe approximation）は、正規因子グラフ（NFG）を介して非負の実値行列に対して成功裏に適用されてきたが、これらの手法を複素値行列へ拡張することは未解決の問題である。具体的には、SPAの固定点が、実数値のアンサンブルから複素数のアンサンブルへと移行する際にどのように振る舞うのか、また、グラフ被覆に関連する確立された解析的な関係が複素領域においても保持されるのかについては不明である。

手法
著者らは、以下の手法を用いて、因子グラフに基づく近似技術を複素値行列へと拡張している。

1. 二重エッジ正規因子グラフ（DE-NFG）： 複素パーマネントに対する標準的なNFGに直接SPAを適用する代わりに、著者らはDE-NFGを利用する。著者らは、その分配関数が $|\text{perm}(\theta)|^2$ に等しくなるように設計された特定のDE-NFG、$N_{DE}(\theta)$ を構築する。この定式化では、バイナリ変数の代わりに $\{0, 1\}^2$ の値を取る変数を用いることで、パーマネントの絶対値の二乗を表現することを可能にしている。
2. 和積アルゴリズム（SPA）の解析： 著者らは、$N_{DE}(\theta)$ 上でのSPAの挙動を調査する。収束を確実にするため、中間値ダンピングを用いたフローディング・スケジュールを採用する。研究は、分布のサポート・セクターを定義する角度 $\alpha \in [0, \pi]$ によってパラメータ化された、成分が独立同一分布（i.i.d.）に従う複素ランダム行列のアンサンブルに焦点を当てている。
3. グラフ被覆解析： ベテ近似を解析的に理解するために、著者らはグラフ被覆の理論を用いる。具体的には、DE-NFGの次数2の被覆（二重被覆）を分析する。これには、DE-NFGの二重被覆を、標準的なNFGの被覆の互いに素な和集合へと分解すること、および対称群のサイクル指数を用いた組合せ論的な計数技術が含まれる。
4. 漸近的および組合せ論的導出： 論文では、全一行列（all-one matrix）および平均ゼロの複素ランダム行列の2つの特定ケースについて、真の分配関数と次数2のベテ近似の比（$Z/Z_{B,2}$）の厳密な式と漸近的挙動を導出している。

主要な貢献と結果

• アルゴリズムの挙動と退化： 数値実験により、パラメータ $\alpha$ に基づくSPAの挙動における2つの明確なレジーム（領域）が明らかになった。
  • 低 $\alpha$（実数値に近い場合）： $\alpha$ が特定の閾値を下回る場合、SPAの固定点メッセージはランク1の行列へと退化する。このレジムでは、近似比は非負の実値行列で観察される比の二乗と同様の挙動を示す。
  • 高 $\alpha$（複素ガウス分布）： $\alpha$ が $\pi$ に近づく（標準的な複素ガウス分布に対応）とき、SPAの固定点メッセージと信念（beliefs）は対角行列へと退化する。このレジムでは、ベテ近似は $|\text{perm}(\theta)|^2$ ではなく $\text{perm}(|\theta|^2)$ を効果的に近似してしまう。近似比の分布は著しく拡散しており、これは性能の低下を示している。
• 二重被覆による解析的結果：
  • 著者らは、DE-NFGの次数2のベテ分配関数 $Z_{B,2}(N_{DE}(\theta))$ が、標準的なNFG被覆の分配関数の絶対値の二乗の期待値 $\mathbb{E}[|Z(\tilde{N}(\theta))|^2]$ として表せることを証明している。
  • 全一行列については、$Z_{B,2}$ の厳密な式を導出し、$Z/Z_{B,2}$ が漸近的に $\sqrt{\pi n / e}$ のスケールで変化することを示す。
  • 平均ゼロの複素行列（特定のモーメント条件を満たすもの）については、真の分配関数と次数2のベテ近似の両方の二次モーメントの厳密な式を導出している。漸近的な比は、$\sqrt{(n + 1 + C)/e}$ （ここで $C$ は分布のモーメントに依存する）のスケールとなることが示されている。
• 「二乗則」仮説の検証： 論文では、$Z(N)/Z_B(N) \approx (Z(N)/Z_{B,2}(N))^2$ という関係性を調査している。結果は、行列成分の引数が一定の閾値内に限定されている場合（実数値に近いケース）には、この関係が保持されることを示している。しかし、分布が標準的な複素ガウス分布に近づく場合、この関係は成立しなくなり、SPAベースの近似は複素パーマネントの干渉効果を捉える能力を失う。

意義
本論文は、複素値行列のパーマネントを近似するための、アルゴリズム的および解析的な両面からの視点を提供している。DE-NFGとグラフ被覆解析を用いることで、著者らは複素設定におけるベテ近似の構造的な限界を明らかにしている。本研究は、SPAベースの手法が実数値に近い行列に対しては堅牢である一方で、高度に複素的な（例えばガウス的な）アンサンブルに対しては、近似の対象がパーマネントの絶対値の二乗から、絶対値の二乗のパーマネントへと実質的にシフトするという、性質の変化が生じることを示している。この知見は、ボソンサンプリングや複素振幅を含む確率的推論といった問題において、いつこのような近似が意味を持ち続けるのかという境界を定義する上で役立つ。