やること
もうしばらくQUBOは見たくないのですが、今回は入試の数学でも出題されるような「複数の数字を均等に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です。
数字に６個の量子ビット（q0～q5）を割り当て、１になったらグループA、０になったらグループBとします。
グループAの量子ビットは１であることを利用し、重みとして数字をかけた合計が130になるような式を設定します。「量子ビットが１になったときにその数字の重みが有効」になります。
#グループA（＝１になった量子ビット）は合計130
H = (15*q0 + 25*q1 + 33*q2 + 41*q3 + 64*q4 + 82*q5 - 130)**2反対に、グループBの量子ビットは０であることから、こちらも重みをかけたものの合計が130になるように設定します。ここで大切なのは、q0 を (1 – q0) と置き換えることで０，１の条件をひっくり返し「０になったときに重みが有効」を表現できることです。
#グループB（＝０になった量子ビット）は合計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（＝１になった量子ビット）は合計130
H = 0
H += (15*q0 + 25*q1 + 33*q2 + 41*q3 + 64*q4 + 82*q5 - 130)**2
#グループB（＝０になった量子ビット）は合計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解は２通り出ましたがグループ名を入れ替えたものなので同じです。[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同じ結果が得られました。
さいごに
あまり数字が多いと解空間の離散性が高すぎてサンプリングのヒット率が絶望的になる気がしますが、いやいや、離散性が高いのどうのと考えている時点で疑似アニーリング脳なのでしょう。理想の量子アニーリングマシンなら解空間がどうであれ１回のサンプリングできっちり求まるはずです。未来のアニーリングマシンに期待していますよ！
