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/02/11 14:49

#量子アニーリング #量子ゲート

はじめに

整数計画問題と呼ばれる問題をQAOAを使って組合せ最適化問題で解いてみます。

コスト関数

コスト関数は下記の通りです。Sx=bという条件を満たす制約条件が1項目で、問題となる方程式を満たすのが2項目です。

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

例題

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

(321523)(x1x2x3)=(35)\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}

を満たすとき、

(121)(x1x2x3)\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]

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

© 2024, blueqat Inc. All rights reserved