12/9(月) 応用科学学会シンポジウムで自動運転に関する講演を担当します☆彡

21-25. 量子アニーリング(QUBO)で複数の数字を均等に2組に分ける

やること

もうしばらくQUBOは見たくないのですが、今回は入試の数学でも出題されるような「複数の数字を均等に2グループに分けてください」を解いてみましょう。

【問題】
次の6つの自然数を、総和が等しくなるように2グループに分けなさい。
15, 25, 33, 41, 64, 82

おさらい

カクラスを解いた記事を予習してください。

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

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

解は [q0, q1, q2, q3] = [0, 0, 1, 1] or [1, 1, 0, 1] となり、3, 4のボール、または1, 2, 4のボールを取ればいいことが分かります。

こういった方程式的な設定はこちらの記事でも扱いました↓

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

どうやって数字分け問題を解くか?

まず、すべての合計値が260なので各グループは合計130です。

数字に6個の量子ビット(q0~q5)を割り当て、1になったらグループA、0になったらグループBとします。

グループAの量子ビットは1であることを利用し、重みとして数字をかけた合計が130になるような式を設定します。「量子ビットが1になったときにその数字の重みが有効」になります。

#グループA(=1になった量子ビット)は合計130
H = (15*q0 + 25*q1 + 33*q2 + 41*q3 + 64*q4 + 82*q5 - 130)**2

反対に、グループBの量子ビットは0であることから、こちらも重みをかけたものの合計が130になるように設定します。ここで大切なのは、q0 を (1 – q0) と置き換えることで0,1の条件をひっくり返し「0になったときに重みが有効」を表現できることです。

#グループB(=0になった量子ビット)は合計130
H = (15*(1-q0) + 25*(1-q1) + 33*(1-q2) + 41*(1-q3) + 64*(1-q4) + 82*(1-q5) - 130)**2

コードと結果

これだけです。

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

#グループA(=1になった量子ビット)は合計130
H = 0
H += (15*q0 + 25*q1 + 33*q2 + 41*q3 + 64*q4 + 82*q5 - 130)**2

#グループB(=0になった量子ビット)は合計130
H += (15*(1-q0) + 25*(1-q1) + 33*(1-q2) + 41*(1-q3) + 64*(1-q4) + 82*(1-q5) - 130)**2


#コンパイル
model = H.compile()
qubo, offset = model.to_qubo()

#分割サンプリング
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}')
response
Sample:[1, 0, 1, 0, 0, 1] Energy:-33800.0 Occurrence:146
Sample:[0, 1, 0, 1, 1, 0] Energy:-33800.0 Occurrence:355

解は2通り出ましたがグループ名を入れ替えたものなので同じです。[15, 25, 33, 41, 64, 82] => [1, 0, 1, 0, 0, 1] ということで、グループAに [15, 33, 82]、グループBに [25, 41, 64] と分かりました。

さて、お気づきかもしれませんが実はグループBの設定式は無くても大丈夫です。グループAの条件を満たしていれば必然的にグループBの条件も満たすからです。

グループBの条件式をなくして実行しても

response
Sample:[1, 0, 1, 0, 0, 1] Energy:-16900.0 Occurrence:144
Sample:[0, 1, 0, 1, 1, 0] Energy:-16900.0 Occurrence:357

同じ結果が得られました。

さいごに

あまり数字が多いと解空間の離散性が高すぎてサンプリングのヒット率が絶望的になる気がしますが、いやいや、離散性が高いのどうのと考えている時点で疑似アニーリング脳なのでしょう。理想の量子アニーリングマシンなら解空間がどうであれ1回のサンプリングできっちり求まるはずです。未来のアニーリングマシンに期待していますよ!

タイトルとURLをコピーしました