QAOA+maxcut

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

はじめに

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

手順

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

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

イジングモデルとは？

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

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

QAOAとは？

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

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

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

VQEとは？

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

例題

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

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

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

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

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

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

$
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

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

Tweet

Recommended