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

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

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

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

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

Yuichiro Minato
blueqat CEO/CTO 2015年総務省異能vation最終採択 2017年内閣府ImPACTプロジェクトPM補佐 2019年文科省さきがけ量子情報処理領域アドバイザー
Comments
Yuichiro Minato
blueqat CEO/CTO 2015年総務省異能vation最終採択 2017年内閣府ImPACTプロジェクトPM補佐 2019年文科省さきがけ量子情報処理領域アドバイザー
Related posts

blueqat Inc.

Shibuya Scramble Square 39F 2-24-12, Shibuya, Shibuya-ku, Tokyo
Contact: info@blueqat.com