A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

技術要約：量子交互作用演算子アンザッツのためのパラメータ設定ヒューリスティック

問題提起
量子交互作用演算子アンザッツ（QAOA）は、組合せ最適化問題を解くための著名なパラメータ化量子アルゴリズムである。しかし、高品質なパラメータ（$\vec{\gamma}, \vec{\beta}$）を効率的に見つけることは、依然として重大な実用的課題である。典型的なパラメータ設定プロセスは、量子ハードウェアまたは高コストな古典シミュレーション上でコスト関数の期待値を評価し、それに基づいて古典オプティマイザがパラメータを更新するという、変分量子・古典ループを伴う。このプロセスは、バレン・プラトー（barren plateaus）、多数の局所最適解、および量子ビット数（$n$）や回路の深さ（$p$）が増加するにつれて指数関数的に増大するリソースの計算量といった問題に直面する。さらに、現在のノイズ中間規模量子（NISQ）デバイスは、ノイズや有限のサンプリング誤差を通じて、これらの課題を悪化させている。

手法
著者らは、コスト関数の期待値の計算という高コストな量子または古典的評価を、効率的な古典モデルによって置き換えるために設計された古典的戦略である「均質性を用いたヒューリスティック（Homogeneous Heuristic for Parameter Setting）」を提案している。このアプローチの中核は、**完全な均質性（Perfect Homogeneity）**という概念に基づいている。

1. 完全な均質性： これは、同じコスト値 $c(x)$ を共有するすべてのビット列 $x$ が同一の量子振幅を持つという状態の特性として定義される。この特性は、特定の対称な問題や、パラメータが小さい極限においてのみ厳密に成立するが、経験的な観察によれば、様々な設定においてQAOAの状態と完全な均質性を持つ状態との間には高いオーバーラップが存在することが示唆されている。
2. 古典的均質プロキシ（Classical Homogeneous Proxy）： 著者らは、完全な均質性を仮定することで、完全な均質性を強制する「古典的均質プロキシ」と呼ばれる古典モデルを構築した。このプロキシにおいて、状態は $2^n$ 個の振幅ではなく、各一意のコスト値 $c$ に対応する一組の振幅 $Q(c)$ によって記述される。
   • 進化は「パスの総和（sum-of-paths）」の観点からモデル化される。著者らは、特定のハミング距離におけるビット列の正確なカウント $n(x; d, c)$ を、コストクラスのみに依存する解析的に導出された分布 $N(c'; d, c)$ で置き換えている。
   • これにより、式(5)を用いて各レイヤー $\ell$ における振幅 $Q_\ell(c)$ を再帰的に計算することが可能となる。これは、コスト値の数 $|C|$ が $n$ に対して多項式的に成長する場合、問題サイズ $n$ および層の数 $p$ に対して多項式時間でスケールする。
3. ヒューリスティック・ループ： パラメータ設定手順（アルゴリズム3）は、このプロキシを内部的なサブルーチンとして利用する。古典オプティマイザは、プロキシから導出された「均質パラメータ目的関数」（コスト期待値の推定値）を最小化するパラメータ $(\vec{\gamma}, \vec{\beta})$ を探索する。プロキシに対して最適なパラメータが見つかったら、それらを実際のQAOA回路に直接適用する。

本論文は、ランダムに抽出された節（clause）を含む、ランダム $k$-SAT、Erdős-Rényiグラフ上のMaxCut、およびMax-$k$-XORといった特定の制約充足問題（CSP）のクラスに対して、必要な分布（$N(c'; d, c)$ およびコスト確率 $P(c')$）を計算できることを示している。

主な貢献

• 完全な均質性とプロキシの定義： 著者らは、完全な均質性の条件を定式化し、効率的な状態記述と期待値算出を実現する「古典的均質プロキシ」を定義した。
• 多項式時間スケーリング： 提案手法は、指数関数的なリソース増大を伴う厳密な状態ベクトルシミュレーションを回避し、変数 $n$ および深さ $p$ の両方に対して多項式時間でスケールするプロキシパラメータの古典計算を可能にする。
• CSPクラスへの汎用化： 著者らは、4つのランダムCSPクラスに対するプロキシ分布の明示的な導出を提供しており、プロキシが単一のインスタンスではなく、問題のクラス全体を記述できることを示している。
• ヒューリスティック・フレームワーク： 著者らは、このプロキシを標準的なパラメータ更新スキームの選択における柔軟性を維持しつつ、標準的なパラメータ最適化ループに統合する完全なワークフロー（アルゴリズム3）を導入した。

結果
著者らは、重みなしErdős-Rényiランダムグラフ（$G(n, p_e)$）上のMaxCut問題に対して、このヒューリスティックを数値的に評価した。

• 低深度（$p \leq 3$）： $n=20$ のグラフにおいて、このヒューリスティックは、「パラメータ転送（parameter transfer）」戦略（より小さなインスタンスからグローバルに最適化されたパラメータを転送する手法）と同等の近似比を得るパラメータを見出した。性能の差は統計的に有意ではなく、いくつかのケースではヒューリスティックの方がわずかに高い平均性能を示した。
• 高深度（$p \leq 20$）： 深さ $p=20$ までの範囲において、ヒューリスティックは、深さが増すにつれて近似比が単調に増加するパラメータを特定することに成功した。対照的に、同一の古典的リソースを用いたパラメータ転送戦略は収束に失敗した。
• プロキシの精度： 数値解析により、特に線形ランプ（linear ramp）のパラメータスケジュールや $\gamma$ が小さい領域において、プロキシがフル状態ベクトルシミュレーションと大きなオーバーラップを維持していることが示された。プロキシで使用される解析的分布は、ランダムグラフインスタンスの経験的な平均と高い相関があることが判明した。

意義と主張
本論文は、均質ヒューリスティックが、ノイズのためにNISQデバイスにとって困難であり、また指数関数的なスケーリングのために古典的手法にとって困難な領域において、パラメータ設定への実用的な経路を提供すると主張している。高コストな期待値評価を多項式時間の古典的プロキシに置き換えることで、本手法は、従来の戦略が収束に失敗する深いQAOA回路（例：$p=20$）の探索を可能にする。

著者らは、このヒューリスティックがすべての特定のインスタンスに対して最適なパラメータを保証するものではないものの、低深度においては確立された手法と同等の性能を発揮し、高深度においてはそれらを凌駕する、堅牢なクラス全体にわたる戦略を提供することを強調している。本研究は、「完全な均質性」という仮定が、必ずしも厳密に正確ではないものの、多くの組合せ最適化の設定（特にランダムな制約を伴うもの）において、パラメータ最適化を導くための十分に正確な近似として機能することを示唆している。最後に、著者らは、プロキシにインスタンス固有の情報を取り入れることや、変分量子固有値ソルバー（VQE）のような他の変分量子アルゴリズムへ拡張することなど、今後の展望を述べている。