Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice

以下は、提示された論文「Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice（実用における組合せ最適化問題に対する変分量子アルゴリズムのベンチマーク）」の技術的サマリーです。

1. 研究の背景と問題設定

• 背景: 組合せ最適化（CO）問題は、サプライチェーン、物流、チップ設計、物理実験における粒子軌道の再構成など、多くの実用的な応用を持つ。これらの問題は一般的に NP 困難であり、古典的なヒューリスティック手法で近似解が求められている。
• 課題: 現在のノイズあり中規模量子（NISQ）デバイス向けに提案されている変分量子アルゴリズム（VQA）、特に変分量子固有値ソルバー（VQE）や量子近似最適化アルゴリズム（QAOA）は、浅い回路（shallow circuits）を使用することで実用化が期待されている。しかし、理論的には訓練に必要なリソース（サンプリング数など）が問題サイズに対して超多項式的にスケールする（コスト集中や局所最適解の問題）ことが知られている。
• 本研究の目的: 理論的なスケーリング結果が、実際の問題（特に Max-Cut 問題）を解く際にどのような意味を持つかを数値的に検証する。具体的には、限られたリソース（固定された評価回数）の中で、VQA が古典的なランダムサンプリングや貪欲法（Greedy Algorithm）に対して実際に優位性を持てるのか、またその閾値はどこにあるかを明らかにすること。

2. 手法と実験設定

• ベンチマーク問題: 3-正則グラフ上の Max-Cut 問題。
  • 問題サイズ $N$（変数の数）: 11, 21, 31, 41, 51, 61 の 6 段階。
  • 各サイズで 25 件のインスタンスを生成（重みは (0, 1] から一様分布）。
  • 最適解は商用ソルバー（Gurobi）を用いて事前に計算。
• 比較対象アルゴリズム:
  1. VQE (Variational Quantum Eigensolver):
     • 回路構造: $N$ 量子ビット、RY 回転ゲートと CNOT ゲートのレンガ状パターン（Brick pattern）による浅い回路。
     • コスト関数: 条件付き平均リスク（CVaR, $\gamma=0.1$）を使用。
     • 最適化アルゴリズム: COBYLA（勾配なし）。
     • 評価回数: 最大 $10^6$ 回（$N_{iter}=1000, N_{shots}=1000$）。
  2. 置換付きランダムサンプリング (Sampling with Replacement):
     • 問題構造を一切利用せず、計算基底状態をランダムに生成する。VQA が単なる「推測」に過ぎないかを検証するためのベースライン。
  3. 貪欲法 (Greedy Algorithm):
     • 局所的に目的関数を最大化するようにビット反転を繰り返す。
     • 重要な工夫: VQE と貪欲法を「同じ初期点」から開始する。VQE の初期パラメータで量子回路を 1 回実行して得られた計算基底状態を、貪欲法の初期状態として使用し、公平な比較を行う。
• 評価指標:
  • 近似率（Approximation Ratio）: 得られた解の目的関数値と最適解（または GW アルゴリズムによる基準値）の比率。
  • 成功確率: 最適解を一度でも見つけた試行の割合。
  • 統計的有意性: ウィルソンのスコア法を用いた 95% 信頼区間。
  • インスタンスごとの相関分析: 特定のインスタンスにおいて、あるアルゴリズムが難しい場合、他のアルゴリズムも難しいかどうかをバinned 統計（区間統計）で分析。

3. 主要な結果

• 小規模問題（$N \le 21$）における結果:
  • VQE はサンプリングに劣る: 問題サイズが 11 や 21 の場合、VQE の平均近似率はランダムサンプリングよりも低い、あるいは同等である。特に $N=11$ では、VQE がサンプリングより劣る領域が広範囲にわたる。
  • 貪欲法もサンプリングに劣る: 解空間が小さいため、ランダムサンプリング自体が非常に強力であり、貪欲法もそれ以上のパフォーマンスを発揮できない。
  • 結論: このサイズでは、VQA が古典的な単純な手法に対して優位性を持つことは確認できなかった。
• 中・大規模問題（$N \ge 31$）における結果:
  • サンプリングとの比較: 問題サイズが 30 を超えると、解空間が指数的に増大するためランダムサンプリングの性能が急激に低下する。これに対し、VQE は $N \ge 31$ でサンプリングを明確に上回る（$N=31$ で約 95% のインスタンスで優位）。
  • 貪欲法との比較:
    • 貪欲法は初期段階で局所最適解に収束し、VQE の初期の反復よりも良い近似率を示す。
    • しかし、VQE は反復を重ねることで貪欲法が到達できないより良い局所最適解（あるいは大域的最適解に近い解）へ収束する。
    • 性能差の傾向: VQE が貪欲法を上回るまでの反復数は問題サイズが大きくなるほど増加する（$N=31$ で約 100 回、$N=61$ で約 600 回）。一方、VQE が貪欲法を上回る「最大性能差（近似率の差）」は問題サイズが大きくなるほど減少する（$N=31$ で約 0.025、$N=61$ で約 0.005）。
• インスタンスごとの相関:
  • VQE とサンプリング: 問題サイズに依存する弱い相関がある。サンプリングが得意なインスタンスは VQE も得意とする傾向があるが、相関はサイズが大きくなるほど弱まる。
  • VQE と貪欲法: 相関は存在しない。 貪欲法が難しいインスタンスでも VQE はうまくいく場合があり、その逆も真である。これは両者が根本的に異なるメカニズム（確率的探索 vs 局所探索）に基づいていることを示唆している。

4. 主要な貢献

1. リソースを考慮した現実的なベンチマーク: 従来の「証明実験（Proof-of-Principle）」的なベンチマークを超え、固定された計算リソース（評価回数）の下でのアルゴリズムの平均性能を定量的に評価した。
2. 優位性の閾値の特定: 特定の浅い VQE 構成において、ランダムサンプリングに対して優位性を持つためには問題サイズが約 30 以上必要であることを数値的に示した。
3. 初期点の重要性と相関の解明: VQE と貪欲法を「同じ初期点」から比較することで、VQE の良い初期点が貪欲法にとって良い初期点とは限らないことを示し、両アルゴリズムの探索メカニズムの非相関性を明らかにした。
4. 性能差の収束傾向: 問題サイズが大きくなると、VQA が古典的アルゴリズム（貪欲法）に対して得られる性能の絶対的な差は小さくなるが、それでもサンプリングよりは優位であるという傾向を明らかにした。

5. 意義と今後の展望

• 実用性の評価: 現在の NISQ デバイスやそのシミュレーションにおいて、VQA が実用的な優位性を持つためには、単に「量子である」だけでなく、問題サイズが一定の閾値（本研究では約 30 変数以上）を超え、かつ古典的なヒューリスティック（貪欲法など）よりも良い解空間を探索できる必要があることを示唆している。
• ベンチマーク手法の提案: 「ランダムサンプリング」と「同じ初期点からの貪欲法」を対照実験として用いることで、量子アルゴリズムの真の能力を評価する枠組みを提供した。
• 物理問題への拡張: 本研究は組合せ最適化（離散変数）に焦点を当てたが、物理系の期待値計算（連続変数や状態の近似）への応用においても、MCMC 法などの古典的手法との比較を通じて、VQA の有効性を議論する基礎となる。
• 結論: 小規模な問題では VQA は古典的なランダムサンプリングにも劣る可能性があるため、実用的な優位性を主張するには、より大規模な問題や、より高度な回路・最適化手法を用いた検証が必要である。