21-26. 量子アニーリング（QUBO）でシフト最適化

量子コンピュータ

2023/05/29

やること
おさらい
シフト最適化問題の解き方
コードと結果
さいごに

やること

アニーリングを勉強しているとシフト最適化問題は避けて通れないです。今回は手短にQUBOでシフト最適化を試します。例題は下の方で出します。

おさらい

先日まとめ記事に追加した応用D1（解が0と1だけの方程式）を使います。

例えば、重さ1, 2, 3のボールのどれを取れば合計3の重さになりますか？の条件式は次のように設定しました。

H = (1*q0 + 2*q1 + 3*q2 - 3)**2

解は [q0, q1, q2] = [0, 0, 1] or [1, 1, 0] となり、1, 2のボール、または3のボールを取れば良いという結果になります。

その他のQUBOで設定できる条件式についてはまとめ記事をご参照ください↓

シフト最適化問題の解き方

例題と解き方

文化祭でお店を出すとして、お店に必要なパワーがこちら。2人体制です。

＊＊＊＊＊＊	13時	14時	15時	16時	17時
必要なパワー	2	2	2	2	2

8人の生徒のシフト希望がこちら。経験者はパワー2を持っているとします。

＊＊＊＊＊＊	13時	14時	15時	16時	17時
q0	1				1
q1	1			1
q2		1			1
q3			1	1
q4				1	1
q5（経験者）	2
q6（経験者）		2
q7（経験者）			2

生徒は、採用であればきっちりシフト希望通り入ることとします。q0君が採用された場合、一部だけ入るようなことはできず必ず13時・17時の両方に入るという意味です。

すでに表中にq0と書いているように、まずは生徒に量子ビットを割り当てて、１になったら勤務、０になったらお休みとします。

条件式の設定は意外とシンプルで、13時の列に着目すると「q0, q1, q5 の合計が2になる」必要があります。q5は経験者なので重み2であることに注意すると、

H = (q0 + q1 + 2*q5 - 2)**2

となり、これを他の時間帯でも同様に設定するだけです。

参考

今回は用いませんが、問題によっては他の制約条件も足せます。

例えば、「全部で3人採用する」であれば「8つの量子ビットから3つを1にする」

H = (q0 + q1 + q2 + q3 + q4 + q5 + q6 + q7 - 3)**2

例えば、「q0君とq1君は仲が悪いので同時には採用しない」は「2つの量子ビットが同時に1になったらペナルティ」

H = (q0 *q1)

などです。条件の強さに応じて重みをかけるなど調整する必要もあるかもしれません。

コードと結果

これだけです。

from pyqubo import Binary
from dwave_qbsolv import QBSolv

#量子ビットを用意する
q0 = Binary('q0')
q1 = Binary('q1')
q2 = Binary('q2')
q3 = Binary('q3')
q4 = Binary('q4')
q5 = Binary('q5')
q6 = Binary('q6')
q7 = Binary('q7')

#各時間帯とも、パワー合計が2になる
H = 0
H += (q0 + q1 + 2*q5 - 2)**2
H += (q2 + 2*q6 - 2)**2
H += (q3 + 2*q7 - 2)**2
H += (q1 + q3 + q4 - 2)**2
H += (q0 + q2 + q4 - 2)**2


#コンパイル
model = H.compile()
qubo, offset = model.to_qubo()
print(f'offset\n{offset}')

#分割サンプリング
response = QBSolv().sample_qubo(qubo, num_repeats=500)

#レスポンスの確認
print('response')
for (sample, energy, occurrence) in response.data():
    print(f'Sample:{list(sample.values())} Energy:{energy} Occurrence:{occurrence}')

offset
20.0
response
Sample:[1, 1, 0, 0, 1, 0, 1, 1] Energy:-20.0 Occurrence:377
Sample:[1, 1, 1, 1, 0, 0, 1, 1] Energy:-18.0 Occurrence:6
Sample:[0, 0, 1, 1, 1, 1, 0, 1] Energy:-18.0 Occurrence:3
Sample:[1, 1, 0, 1, 1, 0, 1, 0] Energy:-18.0 Occurrence:6

解のエネルギーがマイナスoffsetと同じ値であることは、すべての条件を満たしたシフトであることを意味します。以下の通りぴったりになりました。