【量子コンピューター】QAOAでMaxcut問題を解こう! (第2回)

こんにちは、テラスカイの須郷です。
今回は、前回の続きでQAOAというアルゴリズムについて、簡単にご紹介したいと思います。
※この記事の内容は、先日行った以下の勉強会で私が発表した内容をブログ用に再度まとめ直したものです。

前回紹介したMaxcut問題のコスト関数\(E = -\frac{1}{2} \sum_{i,j}C_{ij}(1-x_ix_j)\)は、1 or -1を取るバイナリー変数で表記されていましたが、これをゲートモデルで扱う式に変換する必要があります。結論としては\(x_i\)をそのままZゲート\(Z_i\)に置き換えるだけで大丈夫です。この置き換えた式をコストハミルトニアン\(H_{cost}\)と書くことにします。
このハミルトニアンという言葉はエネルギーの演算子に対して使う言葉ですが、演算子というものに馴染みのない方はエネルギーを求めるためのもの、なんとなくエネルギーの話なのね、という程度の理解で問題ありません。

QAOAは量子断熱定理という概念に基づいています。適当な初期ハミルトニアンを用いて以下のような時間によって形を変えるハミルトニアン\(H(t)\)を考えます。
\[H(t) = (1-\frac{t}{T})H_{initial} + \frac{t}{T}H_{cost} ~~ (0 \le t \le T)\]
このハミルトニアンは\(t = 0\)のときに\(H_{initial}\)、\(t = T\)の時に\(H_{cost}\)となります。
量子断熱定理とは、このようなハミルトニアンがあった時、十分にゆっくり時間発展させれば各時刻において常に基底状態(エネルギーの最も低い状態)をとり続けるというもので、自明な基底状態を持つハミルトニアン\(H_{initial}\)からスタートし、そのような時間発展をさせることができれば、最終的に非自明な基底状態(=求めたい最適値)を得ることができます。
この量子断熱定理は量子アニーリングの基礎にもなっているため、量子アニーリングについてご存知の方は同様の式を見たことがあるかもしれません。

上述の時間発展ハミルトニアンは、理想的には連続的に時間tを動かす必要がありますが、現実的には(プログラム上でも)そうはいきません、離散的にハミルトニアンを動かすときに、時間を以下のようにp個に分割して時間発展させます。この際、トロッター展開という技術を用いると各時間ステップごとに\(\beta_i\gamma_i\)という二個の古典パラメーター(p分割しているので全部で2p個)が出現します。

ゲート操作は数学的にはユニタリー行列に対応しているため、これらの離散的な時間発展も2p個のユニタリー行列の演算になります。これらの時間発展を行った後の最後の量子状態を下図のように\(\beta\)と\(\gamma\)を用いて書くことが多いです。

上述の時間発展後の量子状態は、pを無限に大きくとった理想的な状態では最適解になりますが、現実的には有限のpの値を選択します。
この場合、時間発展後の量子状態が最適な状態になっているかどうかは古典パラメーターの\(\beta\)と\(\gamma\)に依存するため、下図のように古典・量子のハイブリッドな最適化を行います。
古典計算側では、各種オプティマイザーを使って2p個のパラメーターを決定します。量子計算側では、その2p個のパラメーターを用いて(固定して)実機、またはシミュレーターを用いて下図の右側に示した式(エネルギーの式)を計算します。古典計算側ではそのエネルギーを元にさらに2p個のパラメーターを決定し、さらに量子計算側へ渡す、といったように繰り返し計算を行うことで、最適なパラメーターを決定し、最適解を求めることができます。