整数計画問題 / 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]となりました。以上です。

QAOAで整数計画問題

Yuichiro Minato

整数計画問題 / Binary Integer Linear Programming

例題

第1項を計算する

次に第2項を計算する

QUBOをつなげて計算する