Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models

技術要約：イジングモデルにおけるレベル1 QAOAの近最適パラメータチューニング

問題提起
量子近似最適化アルゴリズム（QAOA）は、解をハミルトニアンの基底状態にエンコードすることで、組合せ最適化問題（QUBOなどの二次非制約バイナリ最適化）を解くために設計されたハイブリッド量子・古典アルゴリズムである。回路の深さ（$p$）を増やすことは、理論的には解の質を向上させるが、実用的な実装においては、ゲートノイズ、結合性の制限、および状態準備のエラーにより、浅い深さ（$p=1$、またはQAOA1）に制約される。

QAOA1における決定的なボトルネックは、2つの変分パラメータである $\gamma$ と $\beta$ の最適化である。次元数は低いものの、コスト関数（コストランドスケープ）は非常に振動性が高く、その振動率は問題のサイズ、密度、および重みの変動性とともに増加する。従来の定石では、粗いグリッドサーチとその後の局所最適化で十分であるとされている。しかし、本研究は、そのようなアプローチがランドスケープの歪みやエイリアシング（折り返し雑音）によって真のグローバル最適値を見逃し、劣ったパラメータ推定値をもたらす可能性があることを示している。さらに、既存のパラメータ初期化のためのヒューリスティック手法は、性能保証を欠いているか、あるいは特定のグラフ構造（例：非重みの正則グラフ）に依存しており、複雑で重みを持つ実世界のインスタンスには汎用性がない。

手法
著者らは、イジングモデル（QUBOの量子版）に対するQAOA1パラメータを多項式時間で最適化するための、厳密かつ問題に依存しない戦略を提案している。この手法は、以下の4つの理論的およびアルゴリズム的ステップを通じて進行する。

1. フーリエ解析とサンプリング要件：
   論文では、QAOA1の期待値を部分フーリエ級数としてモデル化している。期待値に関する閉形式の式を導出することで（定理1および系1）、著者らはコストランドスケープの $\gamma$ 次元における最大周波数（$\omega_{\max}$）を解析的に決定した。この周波数は、特定の問題インスタンスの結合強度（$J_{uv}$）および外部磁場（$h_i$）に依存する。ナイキスト・シャノンのサンプリング定理を適用することで、彼らは、歪みなくコストランドスケープを正確に再構成するために必要な最小サンプリング解像度（$\Delta\gamma$）を確立した。これにより、粗いグリッドサーチにおけるアンダーサンプリングの問題が解決される。

2. 次元削減：
   主要な理論的貢献は、$(\gamma, \beta)$ に関する二次元の最適化問題を、$\gamma$ に関する一次元探索へと削減することである。

• 外部磁場を持たないイジングモデルの場合、最適な $\beta^*$ は $\gamma$ の関数として解析的に導出される（定理5）。
• 外部磁場を持つモデルの場合、最適な $\beta^*$ は、一次の最適条件から導かれる四次多項式を解くことによって求められる（定理6）。
  この変換により、アルゴリズムは各点において最適な $\beta^*$ を計算しながら、$\gamma$ に関するラインサーチを実行することが可能となり、計算複雑性を大幅に削減できる。

3. 最適化アルゴリズム：
   得られた一変数関数のグローバル最適値を見つけるために、著者らは区間解析（グリーン・アルゴリズム）に基づく細分アルゴリズム（アルゴリズム1）を採用している。この手法は、三角多項式の最大絶対値を効率的に推定し、高解像度のグリッドサーチを行うことなく、近最適解である $\gamma^*$ の特定を保証する。

4. 最適値の集中：
   論文では、大規模で高密度な正則グラフにおいて、グローバルな最適値 $\gamma^* \in \mathbb{R}^+$ がゼロの極めて近くに集中し、最初の局所最適値と一致することを厳密に証明している（定理7）。有限サイズのグラフを用いた実証分析により、「敵対的」なインスタンス（最初の局所最適値がグローバル最適値と異なるもの）は稀であり、主に小さく疎なグラフにおいて発生することが確認された。この知見により、さらなる簡略化が可能となる。すなわち、最大周波数に基づいたサンプリング境界をステップサイズとして尊重する限り、$\gamma \approx 0$ 付近で初期化された勾配降下法を使用できる。

主な結果
提案された戦略は、QAOA1をサブルーチンとして用いて問題サイズを再帰的に縮小する手法である、再帰的QAOA（RQAOA）を用いて検証された。著者らは、エッジ確率や重みの分布が異なる、大規模で高密度かつ重み付きのエルデシュ・レニ・グラフ（128および256頂点）を用いてベンチマークを行った。

• 外部磁場がない場合： 提案手法（近最適パラメータを用いたRQAOA1）は、すべてのテストされたインスタンスにおいて、粗く最適化されたRQAOA1および古典的な半正定値計画法（SDP）を一貫して上回った。対照的に、粗く最適化されたRQAOA1は、一般にSDPを超えることができなかった。
• 外部磁場がある場合： 著者らは、標準的なRQAOA1が磁場を持つモデルにおいて一貫性のないパフォーマンスを示すことを観察した。これに対処するため、簡略化された反復丸め手順を用いるバリアントである「Iter-QAOA」を導入した。Iter-QAOAは、提案されたパラメータチューニング戦略と組み合わせることで、異なるグラフ密度においてもSDPおよび標準的なRQAлоR1のバリアントを一貫して上回り、堅牢性を示した。
• 敵対的インスタンス： 実証的なテストにより、敵対的なグラフ（最初の局所最適値がグローバル最適値ではないグラフ）に遭遇する確率は、$n > 14$ ノードのグラフにおいて約1%で安定することが示され、ほとんどの実際的なケースにおいてゼロ付近での勾配降下法を使用するという戦略が妥当であることが検証された。

意義および主張
本論文は、任意のQUBO問題に対して、QAOA1のグローバルに近最適なパラメータを効率的に見つけるという課題を解決すると主張している。本研究の意義は以下の点にある：

• 厳密な保証： 従来のヒューリスティックなアプローチとは異なり、本手法は、システムサイズに対して指数関数的にスケールしない可換な重みを持つ場合において、多項式時間のアルゴリズムと、近似的な最適性の証明を提供している。
• 問題への非依存性： この戦略は、グラフの対称性、構造、または重みの分布に関する仮定に依存しないため、一般的な重み付きイジングモデルに適用可能である。
• 実用的な効率性： 探索空間を削減し、$\beta^*$ の解析解を利用することで、高解像度の2Dグリッドサーチの計算不可能性を回避しつつ、粗いサンプリングの罠を回避している。
• 性能の向上： 適切なパラメータチューニングを行うことで、浅い深さの量子アルゴリズム（QAOA1）が、高密度で重み付きのインスタンスにおいて最先端の古典的ヒューリスティック（SDP）を凌駕できることを示しており、変分量子アルゴリズムにおけるパラメータ最適化の決定的な役割を浮き彫りにしている。

著者らは、自身のアプローチがQAOA1のパラメータチューニングのボトルネックを効果的に解決し、現在のおよび近未来の量子ハードウェアにおいて、より信頼性が高く高品質な近似を実現できると結論付けている。