Improving the efficiency of QAOA using efficient parameter transfer initialization and targeted-single-layer regularized optimization with minimal performance degradation

技術要約：パラメータ転送と標的化された正則化最適化によるQAOAの効率向上

問題提起
量子近似最適化アルゴリズム（QAOA）は、近未来の量子デバイス上で組合せ最適化問題（COP）、特に最大カット（MaxCut）問題を解くための有力な候補です。しかし、QAOAは問題サイズ（$n$）および回路深さ（$p$）が増大するにつれて、重大な課題に直面します。最適化のランドスケープは高度に非凸となり、指数関数的に増大する解空間（$2^n$）と線形に増加するパラメータ数（$2p$）によって特徴付けられます。この複雑さは、古典的なオプティマイザを劣悪な局所解に陥らせることが多く、特に重み付きグラフのファミリーにおいては、近似比（$r$）の低下を招きます。さらに、$2p$個の全パラメータを最適化することは計算コストが非常に高く、多大な時間とリソースを必要とするため、量子優位性の実用的な実証を妨げています。

手法
著者らは、性能の低下を最小限に抑えつつQAOAの効率を高めるために、パラメータ転送初期化、標的化された単一層最適化、およびL2正則化を組み合わせたハイブリッド戦略を提案しています。

1. パラメータ転送初期化:

   • このアプローチは、類似した問題インスタンスの最適化パラメータが互いにクラスター化する傾向があるという観察に基づいています。
   • 「ドナー」グラフ（$G_1$、ノード数 $n_d = 8$）を完全に最適化します。このドナーの初期化には、Trotter化量子アニーリング（TQA、パラメータ $t=0.75$）を用い、その後、Adagradオプティマイザを用いてフル最適化を行います。
   • これらの最適化されたパラメータ $\{\gamma^*_i, \beta^*_i\}$ を、同じグラフファミリー内のより大きな「アクセプター」グラフ（$G_2$、ノード数 $n_a \ge n_d$）へと転送します。

2. 標的化された単一層最適化:

   • アクセプターグラフに対して全$2p$個のパラメータを再最適化する代わりに、個別に最適化した際に最も優れた近似比をもたらす特定の「標的」層（$p_k$）を特定します。
   • 固定された深さ $p=15$ において、各層 $p_k \in [1, 15]$ を系統的にテストし、異なるグラフファミリー（3-Regular、Erdős–Rényi、Barabási–Albert）に対して最も確率の高い最適層を決定します。
   • この単一の層のパラメータのみをCOBYLA（Constrained Optimization By Linear Approximation）オプティマイザを用いて最適化し、他のすべての層は転送された値に固定します。

3. 正則化（L2/Ridge）:

   • フル最適化の過程でオプティマイザが局所解に捕らわれることにより、標的化された単一層最適化（$r_s$）がフル最適化（$r_f$）を時として上回ってしまうという不一致に対処するため、著者らはL2（Ridge）正則化を導入しています。
   • コスト関数にペナルティ項 $\lambda \sum (\gamma_k^2 + \beta_k^2)$ を追加します。これにより、解のランドスケープが滑らかになり、オプティマイザが局所解から脱出するのを助け、フル最適化（$r_f$）の信頼性を向上させます。

主な貢献と結果
本研究は、3つの無重みグラフファミリー（3-Regular、Erdős–Rényi、Barabási–Albert）および3つの重み付きグラフファミリーを用いて、ノード数が8から24の範囲のグラフに対して実施されました。

• 無重みグラフにおける性能:

  • 無重みの3-Regular（u3R）グラフにおいて、パラメータ転送アプローチを用いた標的化された単一層最適化（$r_s$）は、平均近似比0.9443を達成しました（フル最適化 $r_f$ は0.9551）。これは最適性能の**98.88%**に相当します。
  • 極めて重要なことに、このアプローチはフル最適化と比較して8.06倍の計算スピードアップを実現しました。
  • 同様の傾向が無重みのErdős–Rényi（uER）およびBarabási–Albert（uBA）グラフでも観察され、そこでは $r_s$ は $r_f$ に極めて近い値を維持しながら、最適化時間（$\tau$）を大幅に削減しました。

• 重み付きグラフにおける性能:

  • 重み付き3-Regular (w3R): 初期化のみ（$r_n$）の段階でGoemans-Williamsonの古典的閾値（$r_{GW} \ge 0.878$）を超えることが多く、標的最適化によってこれらの結果はさらに向上しました。
  • 重み付きErdős–Rényi (wER): ノード数が増大（$n_a \ge 14$）すると、このアプローチは苦戦し、$r_s$ は $r_{GW}$ 閾値を下回りました。これらの複雑な重み付きファミリーについては、高品質な解を得るためにフル最適化が必要であり続けました。
  • 重み付きBarabási–Albert (wBA): このファミリーはハイブリッドな挙動を示しました。フル最適化の方がわずかに効率的であったものの、標的最適化も実行可能な代替案として残りました。

• 正則化の影響:

  • 正則化なしでは、標的化された単一層最適化がフル最適化を上回るケースが**8.92%**存在しました（これはフル最適化が局所解に捕らえられていたことを示唆しています）。
  • L2正則化の適用により、この不一致は**3.81%**に減少し、フル最適化の堅牢性が大幅に向上しました。

• オプティマイザと初期化の比較:

  • 様々なオプティマイザ（COBYLA, POWELL, GSLS, NELDER-MEAD, SPSA）の中で、COBYLAが最も適していると特定されました。これは、同等の精度を提供しつつ、最適化時間が最も短いという特徴があります。
  • パラメータ転送初期化は、近似比および必要な最適化ステップ数の両方において、TQAおよびランダム初期化を一貫して上回りました。

意義と主張
本論文は、効率的なパラメータ初期化と標的化された単一層最適化を組み合わせることで、性能の低下を最小限に抑えつつ、QAOAの効率を大幅に向上させられることを示しています。

著者らは、この戦略が精度と計算コストのトレードオフを効果的にバランスさせていると主張しています。小さな、完全に最適化されたインスタンスからパラメータを転送することで、より大きな複雑なインスタンスに対して「準最適」な開始点を提供し、探索空間を縮小します。その後の戦略的に選ばれた単一層の最適化は、全件の再最適化に伴う指数関数的なコストをかけることなく、解をさらに洗練させます。

本研究は、このアプローチが無重みおよび特定の重み付きトポロジー（w3Rなど）には非常に有効である一方で、フル最適化が依然として必要となる複雑な重み付きトポロジー（特にwER）に対しては、あらゆるケースに適用できる普遍的な解決策ではないことを明らかにしています。L2正則化の導入は、フル最適化が選択的な手法よりも劣後しないようにするための、決定的な緩和戦略として提示されています。最終的に、本研究は、パラメータチューニングに関連する古典的な計算オーバーヘッドを削減することにより、より大規模な組合せ問題に対してQAOAをより実用的なものにするための道筋を示唆しています。