ポスト
量子コンピューター、量子アニーリングのビジネス応用に向けて取り組んでいます。
今回からQAOAという量子コンピューターのゲートモデルのアルゴリズムについて、3回に分けてご紹介したいと思います。
この記事の内容は先日行った以下の勉強会で私が発表した内容を、ブログ用に再度まとめ直したものとなります。
第2回 量子ゲートの最新状況を学ぶ - connpass
今後の記事の流れ
組み合わせ最適化問題と聞くと量子アニーリング等のアニーリング系を思い浮かべる人も多いと思いますが、ゲートモデルにもQAOAという組み合わせ最適化を扱うアルゴリズムがあります。
今回から3回に分けてMaxcut問題をQAOAで解いてみたいと思います。
今回以降、
- Maxcut問題の紹介
- QAOAの簡単な解説
- qiskitを用いたデモ
という流れで説明をします。 第1回の今回はMaxcut問題の紹介です。今回はまだ量子コンピューターに関係のない部分ですが、組み合わせ最適化問題の理解はアニーリングを行う時にも活きてくるため、詳しく紹介したいと思います。
Maxcut問題の紹介
問題設定としては、グラフの頂点を2つのグループに分けるときに、グループ間の辺の本数(または辺の重みの合計)が最大になるようにするにはどのように分ければ良いか？というものになります。
この問題をもう少し深く理解するために以下で順を追って説明していこうと思います。
グラフと隣接行列
最初にMaxcut問題で扱うグラフについて見てみます。
上図左のようなグラフ(頂点とその間の辺の集合)を考えたとき、このグラフの形が問題設定そのものなので、このグラフをプログラムで扱うデータにする必要があります。
グラフをデータとして表現する方法のひとつに上図右のような隣接行列を用いて表す方法があります。
この行列は、頂点間が繋がっているかどうかを0,1で表しており、例えばA,B間は繋がっているので1、B,D間は繋がっていないので0、という風になります。
また、AB間の繋がりをAC間の繋がりの2倍にしたい、というような場合は0,1だけでなく具体的な繋がりの強さを表す数値を入れることもできます。
カットしてみる
グラフのA,B,C,D4つの頂点を2つのグループに分けます。
例えば上図真ん中のように緑の線でAとD、BとCを同じグループに分けるとします。
この際、2つのグループの間を通る辺の数は赤線で示したように3本となります。
同様に、上図右のようにAとC、BとDを同じグループに分けると4本となります。
このようにグラフの頂点を2つのグループに分けた際、その間の辺の本数(または辺の重みの合計)が最大になるような分け方を見つけるのがMaxcut問題です。(このグラフの場合、4が最大です)
今回は4つの頂点を同数ずつにカットしましたが、必ずしもその必要はありません。
定式化
グラフをカットし2グループに分けたとき、頂点iがどちらのグループに属しているかを\(x_i = 1, -1\)で表すと、(少々天下り的ですが)
\[E = -\frac{1}{2} \sum_{i,j}C_{ij}(1-x_ix_j)\]
がコスト関数となります。\(C_{ij}\)は隣接行列のi,j成分です。
この式を理解するために、特定のiとjについて和の各項\( -\frac{1}{2}C_{ij}(1-x_ix_j)\)がどのような値になるかもう少し詳しく見ていきしょう。
頂点iとjが同じグループの場合、\(x_i\)と\(x_j\)は両方1または両方-1となります。
この場合それらの積\(x_ix_j\)は1となり、\( -\frac{1}{2}C_{ij}(1-1) = 0\)となります。
次にiとjが異なるグループの場合、\(x_i \)と\(x_j\)は片方が1、もう片方が-1となります。
この場合それらの積\(x_ix_j\)は-1となり、\( -\frac{1}{2}C_{ij}(1-(-1)) = -C_{ij}\)となります。
よって、iとjが異なるグループにいる頂点ペアの時だけ\(-C_{ij}\)が加算されていき、最終的にこのコスト関数の値は(-1)*(辺の重みの合計)となります。
最後に
今回はMaxcut問題について説明しました。
次回はQAOAというアルゴリズムがどういったものであるか、可能な範囲で説明していこうと思っています。