Generate Image

QAOAで整数計画問題

Yuichiro Minato

2021/07/17 10:41

#qaoa

整数計画問題 / Binary Integer Linear Programming

バイナリ値からなるベクトルxについてSx=bという制約条件を満たす中で、c⋅xが最大となるxを求める。ハミルトニアンは上記の制約条件と最大にするコスト関数を繋げて、

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

例題

下記のような例題を用意します。

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

を満たす時、

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

を最大にするようなベクトル $x$ を求めます。

第1項を計算する

第1項目は $Sx=b$ という条件を満たす組み合わせを指定します。指定の式を $b^2 - 2*b*A + A^2$ の形にします。定数は無視します。


import numpy as np
import blueqat.wq as wq
from blueqat import vqe

A = [[3,2,1],[5,2,3]]
b = [3,5]

qubo = np.zeros((3,3))

for i in range(len(b)):
  qubo += -2*b[i]*np.diag(A[i]) + wq.sqr(A[i])

print(qubo)

[[-34.  32.  36.]

 [  0. -24.  16.]

 [  0.   0. -26.]]

ここで一旦確認をしてみます。上記の条件を満たすのは、


result = vqe.Vqe(vqe.QaoaAnsatz(wq.pauli(qubo), step=2)).run()
answer = result.most_common(12)
print(answer)

(((1, 0, 0), 0.4740483041946056), ((0, 1, 1), 0.4740483041946056), ((0, 1, 0), 0.013873620237192762), ((1, 0, 1), 0.013873620237192762), ((1, 1, 0), 0.0075247127169019755), ((0, 0, 1), 0.0075247127169019755), ((0, 0, 0), 0.004553362851299381), ((1, 1, 1), 0.004553362851299381))

上記のように[1,0,0]や[0,1,1]がでてきました。

次に第2項を計算する

その次にもう１つのコスト関数を計算します。こちらは下記のようになります。


matrix2 = np.diag([1,2,1])
print(matrix2)

[[1 0 0]

 [0 2 0]

 [0 0 1]]

QUBOをつなげて計算する

これらをつなげて計算してみます。


B = 1
qubo += - B * matrix2

result = vqe.Vqe(vqe.QaoaAnsatz(wq.pauli(qubo), step=4)).run()
answer = result.most_common(12)
print(answer)

(((0, 1, 1), 0.6881917820176535), ((1, 0, 0), 0.19239554109430343), ((1, 0, 1), 0.05175245548622831), ((1, 1, 1), 0.033712227096117826), ((0, 1, 0), 0.014905610166535091), ((0, 0, 1), 0.0105463169840855), ((0, 0, 0), 0.007355716679034651), ((1, 1, 0), 0.0011403504760410786))

答えは、[0,1,1]となりました。以上です。