Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

技術要約：組合せ最適化のための生成的量子探索

問題提起
本研究は、浅い量子サンプラーが、古典的な「リカバリ・ベイシン（回復領域）」内に高い確率質量を配置することで、組合せ最適化において古典的なサンプラーを凌駕できるかどうかを調査するものである。本研究では、量子化学分野で開発されたGQE+QSCI（Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction）アーキテクチャを、グラフ最適化（具体的には最大重み独立集合：MWIS）の領域に適応させている。中核となる仮説は、量子サンプラーが、古典的な修復および拡張アルゴリズムによって精緻化された際に、より高い成功率をもたらすような候補解の分布を生成できるという点にある。

手法
著者は、以下の4段階のパイプラインに従うGQO+QSS (Generative Quantum Optimization + Quantum-Selected Search) フレームワークを提案している。

1. 生成的ポリシー (Generative Policy): 機械学習モデル（グラフ条件付きポリシー）が、量子回路プログラム（例：QAOAパラメータ）を生成する。
2. 量子サンプリング (Quantum Sampling): 回路をシミュレータまたはQPU（Piast-Q）上で実行し、ビット列（候補解）を生成する。
3. 古典的リカバリ (Classical Recovery): 問題固有の修復関数を用いて実行不可能な解を修正し、続いて局所的な拡張（例：$r$-flip近傍）を行い、制限された探索部分空間を作成する。
4. 制限付きソルバー (Restricted Solver): この制限された部分空間内で、厳密な古典的ソルバーが最適解を見つけ出す。

主要な理論的定式化
本論文は、「リカバリ・ベイシンの質量」($p_r$) を用いて「量子的な利点」に関する問いを定式化している。
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
ここで、$A_r(G)$ は、修復および$r$-flip拡張を行った後にグローバル最適解を含む状態の集合である。ショット数 $B$ における成功確率は $P_{success} = 1 - (1 - p_r)^B$ となる。本研究は、重要な指標はサンプリングされた部分空間の全空間に対するサイズ ($|S_Q|/2^n$) ではなく、サンプラーがリカバリ・ベイシンに配置する確率質量 $p_r$ であると断じている。

実験プロトコル

• データセット: 真の解がCBCおよび総当たり検証によって保証された150個のMWISインスタンス。
• ベースライン: 9種類のサンプラーを比較。これには、一様ランダム、貪欲法、焼きなまし法（SA）、タブー探索、マルチスタート局所探索、メトロポリス法、ウォームスタートQAOA、オラクルQAOA（最高の設定を50個選択）、および一致させた学習済み古典的ポリシーが含まれる。
• 制約: 事前登録され、固定されたプロトコルに基づき、各サンプラーの予算を200ショットに固定。
• ハードウェア: 実験には、シミュレーションおよび20量子ビットのトラップイオン・プロセッサ（Piast-Q）での実行が含まれる。

主要な結果

1. 古典的優位性: タブー探索と焼きなまし法（SA）は、テストされたすべての問題サイズ（$n=16$ から $n=28$）において、すべての量子および学習済み古典サンプラーを大幅に上回った。タブー探索は、$n=16$ で0.822、$n=18$ で0.944、$n=20$ で0.878、$n=24$ で0.943、$n=28$ で0.901というリカバリ・ベイシン質量（$p_r$）を達成した。SAは、これらのサイズを通じて0.088から0.428の範囲であった。
2. 量子性能の低迷: すべての量子サンプラー（ウォームスタートQAOA、オラクルQAOA、および生成的ポリシー）は、公正かつ事前登録されたプロトコルの下で、すべての問題サイズにおいてSAおよびタブー探索に敗北した。
3. 「オラクル」によるアーティファクト: QAOAがSAを上回るという過去のポジティブな結果は、インスタンスごとに構成を選択するという「オラクル」による上限設定によるアーティファクトであることが特定された。展開可能な手法としてランダムな構成を用いた場合、オラクルQAOAの $p_r$ は $n=28$ において0.014となり、SAの0.088を大きく下回った。
4. 学習済み古典の同等性: 学習済み古典的ポリシー（140Kパラメータ）は、オラクルQAOAと同等の性能（$p_r = 0.005–0.101$ 対 $0.014–0.113$）を達成した。これは、この設定において量子回路が一致させた古典モデルに対して構造的な優位性を持たないことを示している。
5. ハードウェアの堅牢性: Piast-Q上での実験は、QPUとシミュレータのサンプル間で93.4%のリカバリ一貫性を示し、ハードウェアの堅牢性を確認したが、最適化の質における量子優位性は認められなかった。
6. リカバリの遷移: 本研究は、2-flip拡張において、$n \le 16$ では古典的リカバリが十分であるが、$n \ge 20$ では失敗し始めるという「リカバリ遷移」をマッピングした。しかし、この遷移領域においても、強力な古典的ベースライン（SA、タブー探索）は優れた性能を維持した。

意義と主張
本論文は、反証研究として提示されている。その主な主張は、厳格かつ事前登録された評価、および一致させた学習済みベースラインの下では、浅いQAOA由来の提案分布は、MWISにおける古典的リカバリ・ベイシンを捉えるための一致させた古典的提案モデルを凌駕することはない、という点である。

• 量子優位性の欠如: 著者は、テストされた領域において、GQO+QSSアーキテクチャに量子優位性がないことを明示的に主張している。
• 過去の主張の論破: 以前のポジティブな結果は、展開不可能な手法である「インスタンスごとの構成選択（オラクル効果）」に起因すると指摘している。
• 指標の修正: 「部分空間の割合」($|S_Q|/2^n$) は、固定されたショット予算の下ではトートロジー的な指標であり、リカバリ・ベイシン質量 ($p_r$) こそが、リカバリ・ベイシンを測定するための科学的に正確な量であると論じている。
• 今後の方向性: 著者は、量子サンプリングが価値を提供するためには、古典的リカバリが失敗する領域（$n \ge 55$）において、強力な古典的ベースライン（SAなど）よりも一貫して多くの質量をリカバリ・ベイシンに配置する必要があると示唆している。これは、現在の浅い回路が直面している課題である。

結論として、GQO+QSSアーキテクチャはハイブリッド最適化のための有効なフレームワークではあるものの、現在の浅い量子サンプラーは、MWISのリカバリ・ベイシン捕捉という特定のタスクにおいて、強力な古典的確率探索手法に対する構造的な優位性を提供していない。