Simulating Gaussian boson sampling on graphs in polynomial time

技術要約：グラフ上におけるガウス型ボソンサンプリングの多項式時間でのシミュレーション

問題提起
本論文は、ボソンサンプリング（BS）およびガウス型ボソンサンプリング（GBS）に関連する分布からのサンプリングの計算複雑性を取り上げている。AaronsonとArkhipov [1] は、パーマネントの反集中（anti-concentration）およびパーマネントのガウス予想を仮定することで、BSを量子優位性を実証するためのモデルとして提案した。この場合、正確な出力分布からの古典的なサンプリングは、多項式階層を崩壊させるほど困難であると考えられている。同様に、特定の光子源コストを回避するためにスクイーズド状態を利用する変種であるGBSは、完全マッチングの計数、最大密度部分グラフの探索、グラフ同型判定などの困難なグラフ問題の解決のために提案されてきた。

対処されている中心的な未解決問題は、グラフ上のGBS分布、すなわち $\mu_{GBS,G} \propto c^{2|S|} \text{PM}(S)^2$ （ここで $\text{PM}(S)$ は誘導部分グラフ $G[S]$ における完全マッチングの数）からのサンプリングに対して、効率的な古典アルゴリズムが存在するかどうかである。先行研究のZhangら [12] は、非常に密なグラフに対してのみ高速なアルゴリズムを提供しており、またOhら [13] は、$\text{PM}(S)$ ではなく $\text{PM}(S)^2$ に比例する分布とはわずかに異なる分布に対して古典アルゴリズムを提案しているが、非負のGBSケースは未解決のままであった。

手法
著者らは、ターゲットとなるサンプリング分布を、グラフにおける重み付き完全マッチングの問題へと写像する還元戦略を採用している。彼らは、特定の条件下で完全マッチングの近似サンプリングを可能にするJerrum、Sinclair、およびVigoda [14, 17] によって開発されたマルコフ連鎖モンテカルロ（MCMC）アルゴリズムを活用している。

1. 非負ボソンサンプリング（定理1.3）に対して：
   著者らは、与えられた非負実行列 $A$ から二部グラフ $G$ を構築する。この構築では、頂点集合 $L_1, L_2$ および $R_1, R_2$ を作成し、エッジを $A$ の成分によって重み付けする。特定の辺の重みを持つこの構築されたグラフから完全マッチングをサンプリングすることで、$R_1$ におけるマッチされた頂点の周辺分布がボソンサンプリング分布 $\mu_{BS}$ を近似する。近似誤差は、頂数のコピー数であるパラメータ $k$ によって制御され、これは十分に大きい値（$O(n^2/\varepsilon)$）として選択される。

2. グラフ上のガウス型ボソンサンプリング（定理1.1）に対して：
   著者らは、GBS分布 $\mu_{GBS,G}(S) \propto c^{2|S|} \text{PM}(S)^2$ を定義する。これをサンプリングするために、入力グラフ $G$ とエッジの直積である $G \square K_2$ を構築する。

   • 構築： $G \square K_2$ は、2つの $G$ のコピー（$G$ と $G'$）と、対応する頂点を結ぶエッジで構成される。
   • 重み付け： $G$ および $G'$ 内のエッジ（集合 $E$ および $E'$）には重み $c^2$ が割り当てられ、コピー間を結ぶエッジ（集合 $E_0$）には重み $1$ が割り当てられる。
   • 還元： $G \square K_2$ における完全マッチングは、元のグラフの頂点の部分集合 $S \subseteq V$ を誘導する（$S$ は自身のコピー内でマッチされた頂点）。特定の集合 $S$ が誘導される確率は、$c^{2|S|} \text{Haf}(A_S)^2$ に比例することが示される。これは、誘導部分グラフに対する $c^{2|S|} \text{PM}(S)^2$ に等しい。
   • 効率性の条件： Jerrum-Sinclairアルゴリズムは、準完全マッチング（near-perfect matchings）と完全マッチングの比が多項式で抑えられることを必要とする。これを保証するために、著者らは新しい重み関数 $\lambda'$ （$4n^2$ でスケールされたもの）を定義し、この新しい重みの下で、準完全マッチングの総重み（$Z'_{n-1}$）と完全マッチングの総重み（$Z'_n$）の比が定数（具体的には $Z'_{n-1} \le Z'_n/2$）に抑えられることを証明した。これは、元の重みにおける $Z_{n-1} < 2n^2 Z_n$ という関係を確立する補題4.2と、マッチング多項式の対数凹性（HeilmannおよびLieb [20]）およびAM-GM不等論から導かれる。これにより、マルコフ連鎖が多項式時間で混合することが保証される。

主な貢献と結果
本論文は、2つの主要な定理により、多項式時間の古典アルゴリズムを提示している：

• 定理1.1（グラフ上のGBS）： グラフ $G$ と実パラメータ $c > 0$ が与えられたとき、全変動距離において $\mu_{GBS,G}$ に $\varepsilon$-近い分布からサンプリングするアルゴリズムが存在する。実行時間は $O(\bar{c}mn^4 \log^2(nc/\varepsilon))$ である。ここで $m=|E|$、$n=|V|$、$\bar{c} = \max\{1, c\}$ である。この結果は、密なグラフに限らず、すべてのグラフに対して成立する。
• 定理1.3（非負ボソンサンプリング）： 非負実行列 $A$（$A$ は必ずしも切断されたユニタリ行列である必要はない）が与えられたとき、ボソンサンプリング分布 $\mu_{BS}$ に $\varepsilon$-近い分布からサンプリングするアルゴリズムが存在する。実行時間は $O(m^7 n^{14} \varepsilon^{-7} \log^4(mn/\varepsilon))$ である。

意義と主張
著者らは、これらの結果が、$\mu_{GBS,G}$ の分布からのサンプリングに基づくアプリケーションにおいて、量子アルゴリズムは指数関数的な高速化を提供しないことを示していると主張している。多くの提案されたGBSのアプリケーション（例：グラフ同型判定、完全マッチングの計数）は、この特定の分布からのサンプリングに依存しているため、多項式時間の古典的サンプラーの存在は、これらの特定のタスクが標準的なGBSモデルの下で量子優位性を持たないことを意味する。

本論文は、Jerrum-Sinclair-Vigodaアルゴリズムは一般的なボソンサンプリング（入力行列が複素成分を持つ切断されたユニタリ行列である場合）には直接適用できないことを指摘している。その理由は、彼らの構成がサンプリング問題を複素重み付き行列のパーマネント近似へと還元するためである。パーマネントの近似は一般にNP困難であるため、一般的なボソンサンプリングの古典的シミュレーションは依然として困難である。しかし、非負行列およびグラフベースのGBSの特定の場合において、著者らは効率的な古典的シミュレーションが可能であることを示した。

本研究は、Zhangら [12] のような従来のアプローチとは異なり、密なグラフだけでなくすべてのグラフに適用可能であり、かつ直積構成を用いたより単純で高速なアルゴリズムを利用している点で差別化されている。