Bidirectional Path Integral Monte Carlo Simulation of Quantum Circuits

技術要約：量子回路の双方向パス積分モンテカルロ・シミュレーション

問題提起
量子回路の古典的シミュレーションは、アルゴリズムの検証や近未来のデバイスのベンチマークに不可欠であるが、時間と空間の両面において指数関数的なスケーリングの課題に直面している。シュレディンガー法（状態ベクトル・シミュレーション）は厳密な結果を提供するが、そのメモリ要件は $O(2^n)$ で増加するため、およそ30〜50量子ビット程度のシミュレーションに制限される。一方、ファインマンのパス積分法は、全状態ベクトルを保存する代わりに経路を総和することで、空間計算量を $O(nL)$ （$n$ は量子ビット数、$L$ は回路の深さ）に抑えることができる。しかし、パス空間は指数関数的に巨大（$|P| = 2^{n(L-1)}$）であり、かつ極めて疎（sparse）であることが多く、非ゼロの振幅を持つパスの数は全パスに対して無視できるほど小さい。

標準的なモンテカルロ（MC）法は、確率的にパスをサンプリングすることで遷移振幅 $\langle\Psi_f| \hat{U}|\Psi_0\rangle$ を推定しようと試みる。この領域における主要な課題は、「次元の呪い」とパス空間の疎さに起因する。一方向の前方サンプリング（forward sampling）では、初期状態 $|\Psi_0\rangle$ から最終状態 $|\Psi_f\rangle$ へとつながる非ゼロ振幅のパスを見つけることが困難である。そのようなパスが見つかったとしても、それらはしばしば極めて低いサンプリング確率を持つため、重み（$f(\bar{z})/p(\bar{z})$）が非常に大きくなり、推定値の分散が高くなってしまう。さらに、「数値的な符号問題（numerical sign problem）」（パス間の破壊的干渉）も性能を低下させる可能性があるが、本論文は主にサンプリング効率に関する疎さの問題に焦点を当てている。

手法
著者らは、以下の3つのコア概念を統合した**双方向パス積分モンテカルロ（BS）**アルゴリズムを提案している。

1. 双方向サンプリング（Bidirectional Sampling）: コンピュータグラフィックスにおける双方向パス・トレーシング（BDPT）に着想を得たこのアルゴリズムは、初期状態 $|\Psi_0\rangle$ からのパスセグメント（前方）と、最終状態 $|\Psi_f\rangle$ からのパスセグメント（後方）を生成する。
   • 前方セグメント $\bar{z}_F$ は、前方重要度サンプリングを用いて $|\Psi_0\rangle$ から中間状態 $s_{L-1}$ までサンプリングされる。
   • 後方セグメント $\bar{z}_B$ は、随伴ユニタリ演算子 $\hat{U}^\dagger$ を用いて $|\Psi_f\rangle$ から中間状態 $t_{L-1}$ までサンプリングされる。
   • 完全なパスは、特定のレイヤー $l$ において、前方セグメントのステートと後方セグメントのステートを決定論的に接続することによって構築される。このプロセスは、$L$ 個のすべての可能な接続レイヤーに対して繰り返され、1回のサンプリング反復あたり $L$ 個の候補パスが生成される。
2. 多重重要度サンプリング（Multiple Importance Sampling: MIS）: 低確率のパスによって引き起こされる分散に対処するため、著者らはMISを採用している。あるパスは、前方および後方のセグメントを任意の $L$ 個のレイヤーで接続することによって生成され得るため、アルゴリズムは与えられたパスに対して $L$ 個のすべての可能なサンプリング戦略を考慮する。
   • 推定値は「バランス・ヒューリスティック（balance heuristic）」を用いて各パスの寄与を重み付けする。単一の、潜在的に極小なサンプリング確率 $p(\bar{z})$ で割る代わりに、分母は、そのパスが生成され得た $L$ 通りの方法の確率の総和（$\sum p_d(\bar{z})$）を用いる。
   • これにより、あるパスが低確率の戦略によってサンプリングされた場合でも、分母の和が堅牢に保たれるため、推定値が爆発することを防ぐことができる。
3. 空間計算量: アルゴリズムは回路の記述と現在のパスの状態のみを保持し、状態ベクトル法に対する $O(nL)$ の空間計算量の利点を維持する。

主な貢献
本論文はBS推定値を導入し、経験的データを通じて以下の3つの具体的な仮説を検証している。

• H1（収束率）: 双方向アプローチは、前方サンプリング（FS）と比較して、有意に速い収束率（一定のサンプル数または実行時間に対してより低い分散）を達成する。
• H2（スケーラビリティ）: $O(nL)$ のメモリ使用量と効率的なパス発見能力により、本アルゴリズムは標準的なシュレディンガー型シミュレータでは不可能なスケールである最大4096量子ビットの回路をシミュレートできる。
• H3（疎さ vs 符号問題）: BSがFSに対して示す性能向上は、数値的な符号問題（破壊的干渉）の緩和ではなく、主に疎なパス空間のより効率的なサンプリング（非ゼロのパスの発見）に起因する。

実験結果
著者らは、IQP（Instantaneous Quantum Polynomial）回路とランダム（RND）回路の2種類の回路群を用いて、収束分析には5〜25量子ビット、スケーラビリティ分析には最大4096量子ビットの隠れシフト回路（HSC）を用いてアルゴリズムをテストした。

• 収束性: 大規模な回路（例：25量子ビットのIQP、12量子ビットのRND）において、BS推定値は、同じサンプル数に対してFSと比較して2〜5桁の分散減少を示した。実行時間に対して測定した場合、BSはFSを1〜6桁上回った。
• パスの発見: 極めて疎なパス空間において、BSはFSと同じサンプル数で、最大6桁多い非ゼロ振幅のパスを発見した。
• 大規模シミュレーション: アルゴリズムは、256、1024、4096量子ビットのHSCにおける遷移振幅の推定に成功した。状態ベクトル・シミュレータは $O(2^{4096})$ のメモリを必要とする（実行不可能）が、BSアプローチはわずか数メガバイトのRAM（4096量子ビットで RSS ~2.8 MiB）を必要とし、16ノードを使用して30分以内に完了した。
• 疎さ vs 符号問題: 500個のランダム回路の分析により、FSとBSの分散比はパス空間の疎さには非常に敏感であるが、数値的な符号問題の指標である逆二乗平均位相（$\chi$）にはほとんど依存しないことが示された。これは、改善が破壊的干渉の処理によるものではなく、疎な空間のサンプリングの改善から来ていることを裏付けている。

意義と主張
本論文は、提案された双方向サンプリングと多重重要度サンプリングが、量子回路の遷移振幅を推定するための堅牢で偏りのない手法を提供すると主張している。その主な意義は、パス積分の $O(nL)$ の空間計算量を活用し、双方向探索を通じて疎さのボトルネックを克服することで、古典的シミュレーションが数千量子ビット（具体的には4096量子ビット）までスケールできることを示した点にある。

著者らは、本手法は疎さには効果的に対処するものの、数値的な符号問題は依然としてパス積分モンテカルロ法の根本的な課題であることを明示している。破壊的干渉が増大する（$\chi$ が高い）につれて、サンプリング要件は依然として指数関数的に増大する。本論文は、将来の研究において、ノイズを含むシステムへの対応や、代替のパス表現（例：スタビライザー状態）が符号問題をさらに軽減できるかどうかの調査が必要であると述べ、控えめに結論づけている。本研究は、一般的な量子シミュレーションの困難さを解決すると主張するものではなく、大規模で疎なパス空間における振幅推定のための、特定の効率的なツールを提供するものである。