Quantum Alternative Operator Ansatz for graph coloring
この記事では、Quantum Alternating Operator Ansatzと呼ばれるアルゴリズムとそれをgraph coloring problemに適用した場合について説明します。より詳細な議論やその他の適用例については、元論文[1]を見てください。
このQuantum Alternating Operator Ansatzは、Quantum Approximate Optimization Algorithmと同じQAOAと略されややこしいので、Quantum Approximate Optimization Algorithmをoriginal QAOAと呼び、Quantum Alternating Operator AnsatzをQAOAと呼ぶことにします。
Quantum Approximate Optimization Algorithm
QAOAは、original QAOAを拡張したアルゴリズムと考えることができます。まずは、元々のQAOAを復習しておきます。
通常のQAOAは、以下の二つのハミルトニアンで構成されます。
phase Hamiltonian
古典的な目的関数をエンコードしたハミルトニアン
mixing Hamiltonian
各qubitに対するフリップ操作で構成されるハミルトニアン
この二つのハミルトニアンはQuantum Annealingのハミルトニアンの構成要素と一致しています。
ここで初期状態を とすると、上記の二つのハミルトニアンを次のように作用させて、終状態
を作ることができます。ここで はパラメータで、 という演算を 回繰り返しているので、合計で 個のパラメータが存在します。また、式(3)はQuantum Annealingにおける状態の時間発展をTrotter分解して、時間をパラメータ化したものと捉えることもできます。
この交互に演算をかけていく振る舞いは、直感的には、Simulated Annealingのスピンフリップと目的関数のチェックに似ています。
さて、式(3)の終状態を用いて、 の期待値
を量子計算機上で計算します。そして、この を最小化するようにパラメータを古典計算機で最適化します。この量子計算機上での期待値計算と古典計算機上でのパラメータの最適化を繰り返していくことにより、最適値 とそれに対応する終状態を得ます。
Quantum Alternating Operator Ansatz
original QAOAは式(1)と(2)のハミルトニアンから構成できました。QAOAでは、original QAOAにおける という部分をパラメータをもつユニタリー演算 に置き換えます。これを明示的に書けばは
と書くことができます。 はそれぞれphase operator、mixing operatorと呼ばれる演算子ユニタリー演算子です。
phase operator
目的関数に依存して決まる、目的関数をエンコードしたユニタリー演算子。基本的には、original QAOAにおける式(1)と同じで良い。
mixing operator
は以下の2点の性質を持つユニタリー演算子です。
- 最適化問題の実行可能空間のみを探索する操作に対応する演算。
- によって遷移可能な空間全体は実行可能空間全体になる
これは、 をかけることで実行可能解の中のみを十分に探索できることを意味しています。
もちろん、この条件を緩めて、実行可能解でない状態にまで遷移することが可能であるとすることもできます。しかし、その場合には、遷移可能な空間が実行可能空間よりも大幅に大きくなると広い空間を遷移する必要が生じ、そのために必要なパラメータ数やdepthが増大する可能性があります。また、それによって古典側の最適化も難しくなりうる。
このQAOAの操作は直感的には、original QAOAがただ実行可能空間とは関係なくスピンフリップをただ行うだけだったのに対して、QAOAでは制約条件を満たす状態間の遷移だけを操作として選ぶようなことと対応しています。
注意としては、常に実行可能空間にいるためには、初期状態として実行可能解を取る必要がある点。問題に依存して を定義する必要がある点が挙げられます。
Graph Coloring Problem
QAOAの原理については説明したので、次に、具体的にグラフ彩色問題を例に考えてみます。
問題として、無向グラフ が与えられ、そのグラフを 色で塗る問題を考えます。ここで、 とします。
グラフ彩色問題の数理モデルは
と書くことができます。 はノード を色 で塗る時1となる変数です。
の構成
まずは、 について考えてみましょう。これはoriginal QAOAと同じように目的関数に関するハミルトニアンを作れば良いのでPauli演算子を用いて、目的関数を書き直すと、
となります。
ここで、 の項について考えると、onehot制約が満たされている場合には、各ノードは一色だけで塗られるはずなので、 が常に成立します。つまり、 の項も定数となります。これは、この項がglobal phaseにしか寄与しないことを意味しており、期待値の計算には影響しないので、無視しても問題がありません。よって、 は簡単に
とし、この を用いて、 を
と定義します。
の構成
この問題の制約条件はonehot制約なので、onehot制約を満たすような操作 を構成すれば良いことがわかります。
まずは具体的に、 の場合にノード 1に関連する変数 という数字列について考えてみます。
たとえば、色1が採用されている場合には、
となります。この から始まって、onehot制約を満たす操作というのは、
の二つです。これは1と0を入れ替える演算なので、ビット と に対して、 という演算が実行できれば十分です。これを実行する演算は
と書くことができます。
この演算子を肩に乗せた
というユニタリー演算子を考えます。
今、を定義したので、これを複数回組み合わせることで、実行可能領域を回ることができるようにする必要があります。
例えば、最も単純なやり方だと、単純に といった隣のビットに情報を移す演算を順々に考え、これを最初のビットから最後のビットまで繋ぐことを考えることができます。
これを回路として書くと、次のようになります。
この回路をみてわかるように、このように回路を構成するとdepthが深くなってしまいます。実際この場合には、色の総数 を使って のdepthになります。depthが深いのはNISQの場合には避けたいので、この並べ方はあまり好ましくありません。
そこで、演算子 をかける順序を が奇数が先の場合をかけ、次に偶数の場合をかけるようにする。すると、次の図のようにdepthを2まで下げることができる。
この回路のdepthは色の総数にほぼ依存せずdepthは2です。(正確には色の総数の偶奇によって2か3かは変化しますが、簡単のために色が偶数の場合だけを考えます。)
ここで、注意が必要なのは、上の回路図と下の回路図は がそれぞれ可換ではないので一致しない点です。しかし、 の構成の仕方には任意性があるので、つまり、の並べ方には任意性があるので、ここではdepthを下げるために下の回路図の並べ方を採用します。
よって、あるノードに対する操作 は
と書くことができます。
すべてのノードに対して、上記の操作を実行しても 全体の演算は、
と書くことができます。 は一つのノードに対する演算であり、色の切り替え演算は、各ノードごと独立に実行できるので、 全体のdepthは のdepthになっています。
ここでは、すべての のパラメータの値を にしているが、各演算のパラメータをすべて異なるように設定することもできます。
以上で、 と が構成できたので、これを用いて式(1)に従って終状態を計算することで、グラフ彩色問題に対するQAOAを構成することができます。
QAOAのQiskitでの実装
では、実際にQAOAをQiskitで実装してみます。
必要なライブラリーをimportしておきます。
の実装
の実装
次に、mixing operator を実装します。 の形をしていますが、これを量子ゲートで実装できる形にしていきます。と は可換なので、
という形に変形できます。これは、 ゲートと ゲートなのでこちらを用いて実装していきます。
初期状態の実装
次に、初期状態を実装します。ここでは、単純に各ノードの色のうち一つだけが1であればいいので、1としたいビットに ゲートを作用させておきます。
QAOAの実装
さて、準備ができたので、実際に問題を解いてみたいと思います。
ここでは簡単な問題として、
というグラフで2色に塗り分ける問題を解いていきたいと思います。
回路としては以下のようになります。
実際に、QAOAを計算して結果を見てみましょう。
確かに、実行可能解しか出ていないことがヒストグラムからわかります。
また、確率が最も高くなっているのは10011001という状態です。この結果でグラフに色付けしたのが以下の図です。
確かに、2色でグラフを色塗り分けできていることがわかります。
optimizerのイテレーション数やshots数、QAOAの繰り返し数などを変化させることで、これより大きい問題も解くことができるので、ぜひ試してみてください。また、ここでは簡単のために自明な実行可能解の一つを初期状態としましたが、簡単に構成できる実行可能解の重ね合わせ状態を用いても良いです。例えば、onehot制約を満たさねければいけない部分は W stateにし、それらの積状態を構成することで初期状態を作ることもできます。
[1] S. Hadfield et al. "From the quantum approximate optimization algorithm to a quantum alternating operator ansatz." Algorithms
12.2 (2019): 34.