Automorphism-Assisted QAOA: A Classical-Estimator Speedup for QAOA Simulation on Graphs with Non-Trivial Symmetry

技術要約：自己同型写像支援型QAOA (AA-QAOA)

問題提起
量子近似最適化アルゴリズム（QAOA）は、非重み付きMaxCut問題のようなNP困難な組合せ最適化問題を解くための、主要なハイブリッド量子・古典的アプローチである。QAOA研究における大きなボトルネック、特に量子プロセッシングユニット（QPU）へのアクセスが限られているために古典的な状態ベクトルシミュレータに依存しているグループにとって、古典的な最適化ループの計算コストが課題となっている。具体的には、古典的な最適化器の各イテレーションにおいて、問題のハミルトニアン $H_C$ の期待値を計算する必要がある。$|E|$ 個のエッジを持つグラフの場合、標準的な状態ベクトル推定器は、$\langle Z_i Z_j \rangle$ という形式の $|E|$ 個の項を集計する。各項は状態ベクトルの振幅に対して $O(2^n)$ 回のパス（$n$ は量子ビット数）を必要とするため、期待値の集計コストは $O(|E| \cdot 2^n)$ となる。この集計コストは、回路の深さ（$p$）が低い場合であっても、エッジ数が多いグラフでは総シミュレーション時間を支配することが多い。

手法：自己同型写像支援型QAOA (AA-QAOA)
本論文は、グラフの対称性を活用することで、QAOAの古典的な状態ベクトルシミュレーションを加速させる手法としてAA-QAOAを提案している。その核心となる洞察は、グラフの非自明な自己同型群 $\text{Aut}(G)$ に対して、QAOAのアンザッツは $\text{Aut}(G)$ の作用に対して不変な状態 $|\psi(\vec{\beta}, \vec{\gamma})\rangle$ を準備するという点にある。

手法の詳細は以下の通りである：

1. エッジ軌道の特定： アルゴリズムは Nauty パッケージを使用して、グラフの自己同型群の生成元を計算する。これらの生成元を用いて、エッジ集合 $E$ を等価類（軌道）に分割する。これらを $\tilde{S}_m$ と表記する。同じ軌道内にあるエッジは、グラフの対称性に基づき構造的に同一である。
2. 観測量の置換： フルコスト・ハミルトニアン $H_C = \frac{1}{2} \sum_{(i,j) \in E} (1 - Z_i Z_j)$ の代わりに、簡約された観測量 $H_{\text{red}}$ を用いる。この簡約ハミルトニアンは、エッジ軌道ごとに、その軌道のサイズで重み付けされた代表的なZZ項を一つだけ保持する：
   $$H_{\text{red}} = \frac{1}{2} \sum_{m=1}^{|O_E|} |\tilde{S}_m| (1 - Z_{i_m} Z_{j_m})$$
   ここで $|O_E|$ はエッジ軌道の数である。
3. 厳密な等価性： 著者らは、標準的なQAOAアンザッツによって準備された $\text{Aut}(G)$ 不変の状態に対して、期待値が $\langle H_{\text{red}} \rangle = \langle H_C \rangle$ となることを証明している。したがって、最適化のランドスケープ、最適な変分パラメータ $(\vec{\beta}^*, \vec{\gamma}^*)$、および最終的な近似比は変化しない。
4. パイプラインの実装： QAOAアンザッツ回路は、フルハミルトニアン $H_C$ を用いて構築される（これにより、状態準備は標準的なQAOAと同一となる）。しかし、古典的な最適化ループの間、推定器は $|O_E|$ 個の項からなる $H_{\text{red}}$ を用いて期待値を計算する。

主な貢献

• 古典的集計の高速化： 主要な貢献は、状態ベクトル推定器における古典的な後処理コストの削減である。集計コストは、イテレーションあたりの $O(|E| \cdot 2^n)$ から $O(|O_E| \cdot 2^n)$ へと減少する。高速化係数は、軌道比 $|E|/|O_E|$ によって決定される。
• 逆因果錐（RCC）からのデカップリング： 本論文は、回路の深さや量子ビットのスパンを削減するために逆因果錐（Reverse Causal Cone, RCC）を利用する先行研究と、自身のメカニズムを明確に区別している。著者らは、AA-QAOAによる高速化が、代表的なRCCの量子ビットスパンに依存しないことを示している。たとえ単一の代表的なエッジのRCCがすべての量子ビットに及ぶ場合（完全グラフの場合など）でも、高速化は維持される。なぜなら、節約が行われるのは量子回路の実行や状態の進化ではなく、項の古典的な加算においてだからである。
• 厳密性： この手法は近似ではなく、厳密な置換を提供する。$H_{\text{red}}$ に対する最適化は、$H_C$ に対する最適化と全く同じ解に収束する。

結果
著者らは、$p=1$ および $p=2$ のレイヤーを用いて、様々なグラフファミリーに対してAA-QAOAのベンチマークを行った：

• ツリー構造グラフ： 34頂点までのバイナリツリーおよびバランスツリーにおいて、本手法は大幅なウォールタイムの削減を実現した。34頂点のバイナリツリーでは、最適化時間がフルハミルトニアンの $>3600$ 秒から、簡約版の $360.56$ 秒へと減少した（90%以上の削減）。また、ピークメモリ使用量も大幅に減少した。
• 診断コントロール： メカニズムを分離するため、著者らは以下のテストを行った：
  • 完全グラフ ($K_n$): 単一のエッジ軌道（$|O_E|=1$）を持ち、代表的なRCCがすべての量子ビットに及ぶにもかかわらず、$K_{16}$ は約8倍の高速化を示した。これは、高速化がRCCの量子ビットスパンの削減に依存するという仮説を否定するものである。
  • スターグラフ： オーバーヘッドが最小限になった場合、軌道比と一致する高速化を示した。
  • ランダム3-正則グラフ： 自己同型群が自明な（$|O_E| \approx |E|$ である）グラフでは、高速化は見られなかった。これは、恩恵が対称性に厳密に結びついていることを裏付けている。
• アーキテクチャ非依存性： CPUおよびGPUバックエンドの両方でのテストにより、高速化は古典的な集計ステップに固有のものであり、特定のハードウェアアクセラレータによるアーティファクトではないことが確認された。
• 近似比： テストされたすべてのインスタンスにおいて、$R_{\text{red}}$ と $R_{\text{full}}$ の近似比は最適化の分散内で同一であり、厳密な等価性の理論的主張を検証した。

意義と範囲
本論文は、AA-QAOAを、古典的な状態ベクトルシミュレーション・パイプラインのための特化したアクセラレータとして位置づけている。これは、QPUへのアクセスを持たない研究グループにとって主要なツールである。

• 制限事項： 著者らは、AA-QAOAは量子プロセッサ（QPU）上では高速化を提供しないことを明記している。ハードウェア上では、測定される観測量に関わらずフル回路が実行され、対角成分のZZ項の集計は、状態ベクトルシミュレーションで見られる $O(|E| \cdot 2^n)$ のコストを伴わない、古典的なビット列に対する単純な後処理作業であるためである。
• 適用可能性： 本手法は、高い対称性を持つ構造化グラフ（例：ツリー、サイクル、完全グラフ、ハイパーキューブ）のように、軌道比 $|E|/|O_E|$ が大きい場合に最も効果的である。非対称な一般的なグラフ（例：ランダム3-正則グラフ）では効果が低い。
• オーバーヘッド： 自己同型（Nautyを使用）の事前計算にはコストがかかるが、これは報告されたイテレーションごとの時間には含まれていない。しかし、多くの最適化イテレーションやパラメータのスイープを伴う典型的なQAOA研究においては、この事前計算コストは蓄積されるシミュレーションの節約分と比較して無視できる程度である。

要約すると、AA-QAOAは、グラフの対称性を利用してコスト期待値の集計における項の数を減らすことで、量子回路や解の質を変えることなく、古典的なQAOAシミュレーションの計算上のボトルネックを削減する、厳密かつ直接的な手法を提供する。