整数計画問題を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

例題

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

\begin{pmatrix} 3&2&1\\5&2&3 \end{pmatrix} \begin{pmatrix} x_1\\x_2\\x_3 \end{pmatrix} = \begin{pmatrix} 3\\5 \end{pmatrix}

を満たすとき、

\begin{pmatrix} 1&2&1 \end{pmatrix} \begin{pmatrix} x_1\\x_2\\x_3 \end{pmatrix}

を最大にするようなベクトルｘをもとめる。

blueqatで解いてみます。

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

from blueqat.wq import *

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))

(((0, 1, 1), 0.5857063424383061), ((1, 1, 0), 0.23649832912124985), ((1, 0, 1), 0.10538525347336665), ((0, 1, 0), 0.037863564579929794), ((1, 0, 0), 0.017425335432638765))

こたえは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]

[0, 1, 1]

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

整数計画問題をQAOAとアニーリングで

Yuichiro Minato

はじめに

コスト関数

例題

blueqatで解いてみます。

アニーリングで