Imagesはじめまして、テラスカイの須郷です。量子コンピューター、量子アニーリングのビジネス応用に向けて取り組んでいます。今回からQAOAという量子コンピューターのゲートモデルのアルゴリズムについて、3回に分けてご紹介したいと思います。この記事の内容は先日行った以下の勉強会で私が発表した内容を、ブログ用に再度まとめ直したものとなります。connpass2019年2月13日に弊社テラスカイで行った量子コンピューター勉強会の第2回目です。この回では量子ゲートモデルの最新状況ということで、NISQに関連した3つの講演を社外の方も招いて分担して発表を行いました。今後の記事の流れ組み合わせ最適化問題と聞くと量子アニーリング等のアニーリング系を思い浮かべる人も多いと思いますが、ゲートモデルにもQAOAという組み合わせ最適化を扱うアルゴリズムがあります。今回から3回に分けてMaxcut問題をQAOAで解いてみたいと思います。今回以降、Maxcut問題の紹介QAOAの簡単な解説qiskitを用いたデモという流れで説明をします。第1回の今回はMaxcut問題の紹介です。今回はまだ量子コンピューターに関係のない部分ですが、組み合わせ最適化問題の理解はアニーリングを行う時にも活きてくるため、詳しく紹介したいと思います。Maxcut問題の紹介Maxcut問題はクラスタリングなどに応用される組み合わせ最適化問題で、QAOAで解く問題としてはかなり定番になっています。問題設定としては、グラフの頂点を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つの頂点を同数ずつにカットしましたが、必ずしもその必要はありません。最適なカットをした際に、値が最小値を取るようなコスト関数を考え、その関数の最小化問題としてMaxcut問題を定式化します。\sum_{i,j}C_{ij}(1-x_ix_j)\]がコスト関数となります。\(C_{ij}\)は隣接行列のi,j成分です。-\frac{1}{2}C_{ij}(1-x_ix_j)\)がどのような値になるかもう少し詳しく見ていきしょう。頂点iとjが同じグループの場合、\(x_i\)と\(x_j\)は両方1または両方-1となります。\)と\(x_j\)は片方が1、もう片方が-1となります。-C_{ij}\)となります。よって、iとjが異なるグループにいる頂点ペアの時だけ\(-C_{ij}\)が加算されていき、最終的にこのコスト関数の値は(-1)*(辺の重みの合計)となります。最後に今回はMaxcut問題について説明しました。次回はQAOAというアルゴリズムがどういったものであるか、可能な範囲で説明していこうと思っています。(第2回)「量子コンピューター」カテゴリー開設にあたって関連するキーワード組合せ最適化Maxcut問題QAOA量子ゲートモデル量子コンピューターTerraSkyBaseについてTerraSkyBaseはクラウドサービスを手掛ける株式会社テラスカイのコンテンツプラットフォームです。