Proof of hiding conjecture in Gaussian boson sampling

技術要約：ガウス型ボソンサンプリングにおける隠蔽仮説の証明

1. 問題設定

ガウス型ボソンサンプリング（GBS）は、量子計算優位性を示すための有力な候補である。GBSの古典的シミュレーションの困難性の議論は、主に2つの要素、すなわち、行列のハフニアン（hafnian）を近似することの平均的な場合の困難性に関する推測と、**隠蔽仮説（hiding conjecture）**に基づいている。

隠蔽仮説は、複素ガウス行列（具体的には独立な成分を持つもの）が、ハール乱数ユニタリ行列の対称積の中に「隠される」ことができると主張している。これは、2つの分布が全変動（TV）距離において区別不能であるという性質である。この性質は、特定の計算困難な行列 $Z$ をGBSの出力分布の中に埋め込むことを可能にし、それによって、敵対者（または古典的シミュレータ）が確率推定を歪めるために $Z$ の位置を特定することを防ぐ。

標準的な（フォック）ボソンサンプリングにおける隠蔽特性は疎な領域（sparse regimes）では確立されていたが、近年の大規模なGBS実験に関連する領域――すべての $M$ 個の入力モードがスクイーズされている場合（$K=M$）――では未証明であった。この領域において、関連する部分行列はハールユニタリの $N \times M$ の長方形ブロックであるが、これは行の正規化制約により、TV距離においてガウス行列には見えないことが知られている。未解決の問いは、この非ガウス的な部分行列の対称積（$U_{N,M}U_{N,M}^T$）が、TV距離において複素対称ガウス行列に収束するかどうかであった。

2. 手法

著者らは、$K=M$（すべての入力モードがスクイーズされている）の場合について厳密な証明を提供している。手法の核心は以下の通りである：

• ランダム行列論の定式化： この問題は、$M \times M$ の巡回直交アンサンブル（COE）ランダム行列（$U$ がハール乱数であるとき $UU^T$ として分布するもの）の左上 $N \times N$ 部分行列 $A$ が、$\sqrt{M}$ でスケールされた際に複素対称ガウス行列 $G \sim \mathcal{G}^{\text{sym}}_N$ に収束することを示す問題へとマッピングされる。
• KLダイバージェンスによる全変動距離： 直接的な結合（coupling）を用いる代わりに、著者らは、2つの分布間のカルバック・ライブラー（KL）ダイバージェンスを用いてTV距離を抑え込む**ピンサーの不等式（Pinsker's inequality）**を利用する。
• 密度解析：
  • COE部分行列の確率密度関数（PDF）は、既存の文献（Hua, 1963; Kieburg et al., 2013）を用いて導出される。これには、行列式項 $\det(I - Z^\dagger Z/M)^{(M-2N-1)/2}$ が含まれる。
  • ターゲットとなるガウス行列のPDFは、標準的な複素対称ガウスである。
• 正規化定数の処理： 技術的な革新として、COE密度の複雑な正規化定数の明示的な計算を回避している。代わりに、著者らはスケーリング因子 $\zeta$ を導入し、行列の特異値の境界を用いることで $\zeta \to 1$ ($M \to \infty$ のとき) であることを証明している。これにより、収束証明の妥当性を維持したまま、正規化定数の困難な漸近展開を回避できる。
• モーメント境界： 証明では、Weingarten計算を用いて特異値（$A^\dagger A$ の固有値）のモーメントを計算し、集中不等式（サブガウス集中）を用いて大きな固有値が発生する確率を抑え込み、対数密度のテイラー展開が有効であることを保証している。

3. 主な貢献と結果

定理 1.1 / 定理 1.2 (主要な結果):
著者らは、$K=M$ の場合のGBSにおける隠蔽仮説を証明している。具体的には、$N = o(\sqrt{M})$ のとき、スケールされたCOE部分行列 $\sqrt{M}A$ と複素対称ガウス行列 $G$ の間の全変動距離は、$M \to \infty$ において消失することを示す：
$$d_{\text{TV}}(\sqrt{M}A, G) \leq O\left(\frac{N}{\sqrt{M}}\right)$$
これにより、対称積 $U_{N,M}U_{N,M}^T$ が、実験的に関連のある領域において複素対称ガウス行列によって良好に近似されることが確立された。

系 1.1:
著者らは、複素対称ガウス行列 $G$（独立な成分を持つ）と、長方形ガウス行列の対称積 $GG^T$ が、成分ごとの最大ノルムにおいて（したがって、十分に小さい $N$ に対してはTV距離においても）近いことを示している。これは、$\text{Haf}(G)$ を近似することの困難性が、関連する領域において $\text{Haf}(GG^T)$ を近似することの困難性と本質的に等価であることを意味する。

定理 1.3 (乗法的推定):
本論文は、密度関数に対する乗法的境界 $f(Z) \leq (1 + O(N^3/M))g(Z)$ を提供している。この結果は、「インスタンス生成」法を用いる困難性の証明に必要であり、特定のガウス行列を隠された部分行列として含むランダムなユニタリ行列の生成を可能にする。

定理 1.5 & 1.6 (疎な領域への拡張):
本論文は、隠蔽特性を疎な領域（$NK = o(M)$）へと拡張し、この領域において $K < M$ でも隠蔽仮説が成立することを確認し、フォック・ボソンサンプリングの既知の境界を最大サイズ $N = o(\sqrt{M})$ まで改善した。

4. 意義と主張

本論文は、最大スクイーズ入力モード（$K=M$）を用いたガウス型ボソンサンプリングにおける隠蔽特性の初の厳密な証明を提供したと主張している。

• 困難性の議論： 隠蔽仮説を証明することで、著者らは、最大スクイーズ入力モードを用いたGBSの古典的シミュレーションの困難性の議論を、従来のフォック・ボソンサンプリングの困難性の議論（Aaronson and Arkhipov, 2013）と同等のレベルに引き上げた。
• 実験的関連性： この結果は、完全にスクイーズされた入力状態を利用する最近の大規模なGBS実験（例：Madsen et al., Nature 2022）に対する、計算理論的な正当性を直接的に支持するものである。
• 理論的ニュアンス： 著者らは、証明が部分行列そのものではなく、その対称積の分布に基づいていることを強調している。部分行列 $U_{N,M}$ はTV距離においてガウス分布からは程遠いが、その対称積 $U_{N,M}U_{N,M}^T$ はガウス行列に収束する。この区別は極めて重要である。なぜなら、フォック・ボソンサンプリングの隠蔽特性からGBSの困難性を導こうとした過去の試みは、この高密度な領域においては失敗してきたからである。

結論として、本論文は $K=M$ のケースが解決された一方で、$K=cM$ ($c<1$) の中間的なケースにおける隠蔽仮説は、本研究の範囲内では未解決であるとしている（ただし、後続の追補研究 [47] で解決された旨を注記している）。本研究は、衝突のない領域（$N \ll M$）に厳密に従っており、ハフニアン近似の平均的な場合の困難性に関する標準的な計算理論的推測に基づいている。