Fair sampling with temperature-targeted QAOA based on quantum-classical correspondence theory

技術要約：温度標的型QAOAによる公平なサンプリング

問題提起
縮退した基底状態を特徴とする組合せ最適化問題において、偏りなくすべての縮退解に対して一様な分布を得る「公平なサンプリング（fair sampling）」を行う能力は極めて重要である。量子アニーリング（QA）および量子近似最適化アルゴリズム（QAOA）はこれらの問題に対して有望なメタヒューリスティクスであるが、横磁場ミキサーを利用する標準的な実装では、公平なサンプリングを実現できないことが多い。理論的および実験的な証拠は、回路の深さが増すにつれて、標準的なQAOAが縮退した状態間にバイアスを誘発し、近似比が1に収束する場合であっても特定の解を優先することを示唆している。既存の解決策（特殊なミキサーやハイブリッド・ポストプロセッシングなど）は、多くの場合、回路の複雑性を増大させるか、追加の古典的計算ステップを必要とする。

手法
著者らは、ミキサーを修正するのではなく、量子・古典対応理論に基づいてターゲット（コスト）ハミルトニアンを再設計することにより、サンプリングバイアスに対処するQAOAの変種であるSBO-QAOAを提案する。

• 理論的枠組み: 古典的なイジング・ハミルトニアン $\hat{H}_0$ の基底状態をターゲットにする代わりに、SBO-QAOAはSommaらによって導出された有効ハミルトニアン $\hat{H}_S(T)$ の基底状態をターゲットとする。このハミルトニアンは、その唯一の基底状態が、特定の温度 $T$ における古典系のボルツマン因子の平方根を確率振幅として持つ量子状態 $|\psi_{Gibbs}(T)\rangle$ に対応するように構成されている。
• ハミルトニアンの構成: SBOハミルトニアンは次のように定義される：
  $$\hat{H}_S(T) = -e^{-\alpha/T} \sum_{i=1}^N \left( \hat{\sigma}_i^x - e^{\hat{H}_i/T} \right)$$
  ここで、$\hat{H}_i$ はスピン $i$ に依存する $\hat{H}_0$ の局所項を表し、$\alpha$ は $T \to 0$ の際に発散を防ぐためのスケーリング因子である。SBO-QAOAでは、$\hat{H}_C$ を $\hat{H}_S(T)$ に設定し、標準的な横磁場ミキサー $\hat{H}_X$ を保持する。
• パラメータ化スキーム: 本研究では、変分角 $\{\gamma_k, \beta_k\}$ に関する2つのパラメータ化戦略を評価する：
  1. フルパラメータ: 回路の深さ $p$ に対して $2p$ 個の独立変数を持つ。
  2. 線形化: 深さのインデックスの関数として角度を減少させるスキームであり、深さに依存せず、最適化変数を4つ（$\gamma_{slope}, \gamma_{intcp}, \beta_{slope}, \beta_{intcp}$）に削減する。
• 実験設定: 数値シミュレーションは、6重の基底状態縮退を持つ5スピンのフラストレイテッド・イジング・トイモデルを用いて行われた。標準的なQAOAとSBO-QAOAを、様々な回路の深さ（$p=1$ から $100$）および温度にわたって比較するために、系を厳密に（フル行列発展を用いて）シミュレートした。

主な結果

• 標準的なQAOAのバイアス: 標準的なQAOA（$\hat{H}_0$ をターゲットとする場合）では、回路の深さ $p$ が増すにつれて、全基底状態確率（$P_{GS}$）は1へと向かう。しかし、縮退部分空間内の分布は依然として偏っており、フルパラメータまたは線形化パラメータのいずれを使用した場合でも、特定の状態ペアが支配的になり、他の状態は抑制される。
• SBO-QAOAの公平性: $\hat{H}_S(T)$ をターゲットとする場合、SBO-QAOAは根本的に異なる挙動を示す：
  • 温度標的化: 全基底状態確率 $P_{GS}$ は1には近づかず、指定された温度 $T$ におけるギブス分布の確率と一致する値（例：$T=1$ のとき $\approx 0.83$）で飽和する。
  • 一様サンプリング: $p$ が増加するにつれて、縮退した基底状態間の確率分布は一様になる。異なる状態ペアの確率は同一の値に収束し、公平なサンプリングが行われていることを確認できる。
  • 全変動距離（TVD）: 出力分布とターゲットとなるギブス分布との間のTVDは、$p$ の増加とともに減少し、ゼロ付近に収束する。これにより、アルゴリズムが単なる基底状態だけでなく、完全な有限温度分布を再現していることが確認される。
• パラメータ削減に対する堅牢性: SBO-QAOAの公平なサンプリングおよび温度標的化の特性は、変分パラメータの数が $2p$ からわずか4つに減少する線形化スキームの下でも維持される。

意義と主張
本論文は、ミキサーの複雑性を増大させたり、追加の古典的ポストプロセッシング工程を加えたりすることなく、QAOAにおける公平なサンプリングが達成できると主張している。ターゲットとなるハミルトニアンをSBOハミルトニアンに置き換えることで、アルゴリズムはギブス分布をその基底状態として本質的に符号化する。著者らは、このアプローチによって以下が可能であることを示している：

1. 公平なサンプリング: 縮退した基底状態に対する一様な分布の実現。
2. 温度標的化: パラメータ $T$ を通じたサンプリング分布の制御。
3. 効率性: これらの特性を最小限の変分パラメータ（4つ）で維持し、最適化の複雑さの観点からスケーラブルである可能性を示す。

著者らは、現在の研究が厳密対角化を用いて小規模な系でこれらの特性を検証したものであることを指摘しており、今後の課題としてスケーラビリティへの対処が必要であるとしている。具体的には、$\hat{H}_S(T)$ をゲートベースのデバイス上に実装するには、ハミルトニアンが一般に多体相互作用を誘起するため、効率的なパウリ文字列展開と回路分解が必要となる。