量子コンピュータ
量子アニーリング

整数計画問題を量子コンピュータQAOAとアニーリングで


はじめに

整数計画問題と呼ばれる問題をQAOAを使って組合せ最適化問題で解いてみます。


コスト関数

コスト関数は下記の通りです。Sx=bという条件を満たす制約条件が1項目で、問題となる方程式を満たすのが2項目です。

H = \sum_{j=1}^m[b_j-\sum_{i=1}^N S_{ji}x_i]^2 - B\sum_{i=1}^N c_ix_i


例題

早速下記のような例題を解いてみましょう。

004_1.png


Blueqatで解いてみます。

まずは式を準備して解いてみます。インストールしてない方はpipで

pip install blueqat

次に早速問題を解きます。opt.optmは数式からハミルトニアンを自動分解してQUBOをつくってくれます。上記式でBのハイパーパラメータを2にしてみました。

from blueqat.opt import Opt

result = Opt().add('(3*q0+2*q1+q2-3)^2+(5*q0+2*q1+3*q2-5)^2-2*(q0+2*q1+q2)').qaoa()
print(result.most_common(5))

#=>
(((0, 1, 1), 0.8571008889203714), ((1, 1, 0), 0.08134053938905932), ((0, 1, 0), 0.031757569458734695), ((1, 0, 0), 0.011712997948251888), ((1, 0, 1), 0.010846834513550044))

こたえは011がでてきました。こちらが答えです。

x1=0,x2=1,x3=1となりました。以上で整数計画問題が解けました。


アニーリングで

答え合わせしてみます。

Opt().add('(3*q0+2*q1+q2-3)^2+(5*q0+2*q1+3*q2-5)^2-2*(q0+2*q1+q2)').run()

[0, 1, 1]

こちらも大丈夫そうです。