@yuichirominato 2018.11.12更新 36views

Blueqatで汎用型量子コンピュータでmaxcutのハンズオン

Blueqat QAOA QUBO 組合せ最適化 量子ゲート

はじめに

組合せ最適化問題におけるmaxcut問題はイジングモデルと呼ばれる物理モデルで特にはとても初歩的な問題です。今回はこちらの問題をBlueqatをつかって実践してみたいと思います。

手順

具体的な手順はシンプルです。

1、問題の設定
2、問題をイジングモデルと呼ばれるモデルにマッピングする
3、イジングモデルを量子ゲートモデルのアルゴリズム「QAOA」にかける
4、精度のパラメータを設定し、あとは問題を回路にかけて計算する
5、出てきた答えを確認する。シミュレータの場合には状態ベクトルというものを確認する。

イジングモデルとは?

イジングモデルは物理モデルです。こちらに適合するように問題を設定することで量子コンピュータで解けるようになります。

「量子アニーリング、イジングモデルとフレームワーク」
http://blog.mdrft.com/post/6

QAOAとは?

量子ゲートモデルでの量子シミュレーション手法の1つで、量子断熱計算を利用して組合せ最適化問題を解きます。
参考は下記です。

「量子ゲートで組合せ最適化問題を解くQAOAの実装」
http://blog.mdrft.com/post/229

今回はこのQAOAを利用します。

VQEとは?

今回さらにこのQAOAを解く際に利用するのがVQEで、変分原理を利用して、波動関数のパラメータを求めるテクニックで、量子古典ハイブリッド計算の古典最適化を組み合わせて計算します。

例題

早速例題です。以前の記事で、D-Waveやアニーリングのイジングでmaxcut問題を解いたものがありました。これと同じ例題を取り上げてみたいと思います。記事は参考になりますので、下記から参照ください。

「D-WaveとWildqatで巡回セールスマン問題とmaxcut問題を解いてみた」
http://blog.mdrft.com/post/160

5ノードのネットワーク問題でmaxcutを解いてみたいと思います。頂点を2つのグループに分けるような辺の切り方のうち、一番最大数のものを探します。イジング問題で解くときには、隣り合う頂点同士がなるべく異なる符号に落ちるようにエネルギー関数の最小値を探していきます。

maxcutのコスト関数一般式は、頂点の量子ビットが{-1,1}をとりうるとして、

$
H = -\sum_{i,j} \frac{1}{2}(1-q_iq_j)
$

ノードが等しいとコストが高くなるようになっています。今回は5ノードあるので、

$
H = -\frac{1}{2}\bigl[(1-q_0q_1)+(1-q_0q_3)+(1-q_1q_2)+(1-q_2q_3)+(1-q_3q_4)+(1-q_2q_4) \bigr]\\
=\frac{1}{2}(q_0q_1+q_0q_3+q_1q_2+q_2q_3+q_3q_4+q_2q_4)-3
$

こちらをプログラミングします。

Blueqatにプログラミング

インストールは簡単です。

pip install blueqat

もしくはこちらから手に入ります。
https://github.com/mdrft/Blueqat

コードは下記の通りです。blueqatからvqeとblueqat.pauliを呼び出します。
次に上記のハミルトニアンをZオペレーターで記述します。そして、精度を決めるステップを決めます。
最後にvqe/qaoaアルゴリズムをかけることで解を得ます。

from blueqat import vqe
from blueqat.pauli import *

hamiltonian = 0.5*Z[0]*Z[1]+0.5*Z[0]*Z[3]+0.5*Z[1]*Z[2]+0.5*Z[2]*Z[3]+0.5*Z[3]*Z[4]+0.5*Z[2]*Z[4]
step = 2

result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step)).run()
print(result.most_common(12))


(((1, 0, 1, 0, 1), 0.0875936132919655), ((1, 0, 1, 0, 0), 0.0875936132919655), ((0, 1, 0, 1, 1), 0.0875936132919655), ((0, 1, 0, 1, 0), 0.0875936132919655), ((1, 0, 1, 1, 0), 0.07344565024381726), ((0, 1, 0, 0, 1), 0.07344565024381726), ((1, 0, 0, 0, 1), 0.07344565024381723), ((0, 1, 1, 1, 0), 0.07344565024381723), ((0, 0, 1, 1, 0), 0.06382328839510434), ((1, 1, 0, 0, 1), 0.06382328839510434), ((1, 0, 0, 1, 0), 0.026885288693200914), ((0, 1, 1, 0, 1), 0.026885288693200914))

上記は無事状態ベクトルと呼ばれる形で解を得ることができました。上位4つは組み合わせが最小コストになっているのがわかります。シミュレータでは、状態ベクトルで出現確率を一緒に求めることができます。

以上でmaxcutが解けました。

1,0,1,0,1
1,0,1,0,0
0,1,0,1,1
0,1,0,1,0

の4つが答えになります。

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップに戻る

Recent Posts