common.title
Cloud support

Nobisuke

Dekisugi

RAG

autoQAOA
RAG for dev
Fortune telling app
Annealing
DEEPSCORE
Translation
Overview
Service overview
Terms of service

Privacy policy

Contact
Research
Sign in
Sign up
common.title

QAOAで整数計画問題

Yuichiro Minato

2021/07/17 10:41

#qaoa

1

整数計画問題 / Binary Integer Linear Programming

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

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

例題

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

[321523][x1x2x3]=[35]\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}

を満たす時、

[121][x1x2x3]\begin{bmatrix} 1&2&1 \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}

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

第1項を計算する

第1項目はSx=bSx=bという条件を満たす組み合わせを指定します。 指定の式をb2−2∗b∗A+A2b^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]となりました。以上です。

© 2024, blueqat Inc. All rights reserved