Grover Mixers for QAOA

Grover Mixer QAOA

Grover Mixer QAOA (GM-QAOA)は、組み合わせ最適化問題を解く量子アルゴリズムであるQAOAを、
制約付き最適化問題に拡張したアルゴリズムです。

GM-QAOAの論文
https://arxiv.org/abs/2006.00354

なお、QAOAについては、
https://dojo.qulacs.org/ja/latest/notebooks/5.3_quantum_approximate_optimazation_algorithm.html

QAOAで制約付き組み合わせ最適化問題を解く場合、コストハミルトニアン$H_{C}$に、制約違反に対するペナルティーを課す項$H_{penalty}$
を追加した $H_{C} + K*H_{penalty}$を新たなコストハミルトニアンとして設定して最適化することが普通です。
係数$K$が小さすぎると制約違反の解が出力されてしまいますし、大きすぎると制約遵守ばかりを気にして肝心の$H_{C}$が低くない解を出力してしまいます。
$K$は経験的に設定するしかないことが多く、なかなか難しいです。

GM-QAOAでは、解の探索空間を、制約を満たす範囲に限定することが出来ます。
コストハミルトニアンは$H_{C}$をそのまま使えます。

GM-QAOAの原理

通常のQAOAでは、自明な基底状態を持つハミルトニアン(Mixerハミルトニアン)$H_{mixer}$の元での時間発展$e^{-i\beta H_{mixer}}$と、
コストハミルトニアン$H_{C}$のもとでの時間発展$e^{-i\gamma H_{C}}$を交互に行います。
Mixerハミルトニアンには、問題に関する情報は一切教えられていないため、制約違反となる解も探索してしまうことがあります。

GM-QAOAでは、$H_{mixer}$に制約を教えます。
今、探索空間全体が$n$量子ビットで表現できたとします : $S = [0,1]^{\otimes n}$
このうち、制約を満たすもの全体の空間を$F$とします。 : $F \subseteq S$
$F$の元$|x \rangle$のうち、最もコスト$H_{C}(|x \rangle)$が低いものがこの問題の解です。

$F$の全ての元$|x \rangle$に対する均等重ね合わせ状態を$|F \rangle$とします。
$|F \rangle = \sum_{x \in F} |x \rangle$
(規格化係数は省略します）
このとき、GM-QAOAは以下のようなアルゴリズムです。

・初期状態としては、$|F \rangle$を用いる。これはゲート$U_{S}$で準備できるとする：$|F \rangle = U_{S}|0...0 \rangle$
・時間発展は、$H_{mixer} = |F \rangle \langle F|$のもとでの時間発展$U_{M} = e^{-i\beta |F \rangle \langle F|}$を用いる。
コストハミルトニアンの元での時間発展はQAOA同様に$U_{P} = e^{-i\gamma H_{C}}$とする。
両者を交互に繰り返す
・コストハミルトニアンの期待値を測定し、最小となるように、変分パラメータ$\beta, \gamma$を古典ソルバーでアップデート。

初期状態は制約を満たすものだけで構成されており、$|F \rangle \langle F|$は制約を満たすもの全体の空間への射影演算子¹なので、
この時間発展で制約の"外へ出る"ことはありません。²
よって、探索空間は制約の範囲内に限定されます。

上記のような、「解空間への射影」という技はGroverのアルゴリズムにも見られるため、Grover mixer QAOA という名前がついているようです。

GM-QAOAの注意点

弱点としては、$|F \rangle$を用意するのに必要な計算量が大きい場合は実用上使えません。
論文では多項式時間が求められるとありますが、多項式時間といっても様々なので、実際はケース・バイ・ケースかと思います。
Groverのアルゴリズムでも、Grover演算子が重くて実機で使えないということはよくあります。
オリジナルのQAOAはNISQでも動くように出来るだけゲートを浅くしたアルゴリズムですが、GM-QAOAはGroverの系譜が入っているのでゲートが深くなる場合があり、NISQとlong-termの悪いところ取りになる可能性もあります。

まとめ

GM-QAOAについて論文を読んでみた。制約付き最適化に有効である。

---

1. 作用するのは$U_{M} = e^{-i\beta |F \rangle \langle F|}$であって、$|F \rangle \langle F|$じゃないよね？と思うかもしれません。そのとおりです。が、行列指数関数$e^{A}$はたかだか$A$の累乗の和であることと、射影演算子$P$の累乗は再び$P$であることを考えると、$U_{M} = e^{-i\beta |F \rangle \langle F|}$は$|F \rangle \langle F|$とそっくりに振る舞います。 ↩

2. コストハミルトニアンのもとでの時間発展で制約の外へ出ることがありえる気がしますが・・・。それでも、次のミキサーハミルトニアンの作用で再び制約を満たす空間へ射影される＝”引き戻してくれる”のでしょうか。 ↩