21-24. 量子アニーリング（QUBO）で論理クイズ「犯人は誰だ？」を解く

量子コンピュータ

2023/05/19

やること
紙とペンで解く
QUBO式のおさらい
どうやってアニーリング（QUBO）で解くか？
コードと結果
さいごに

やること

もうQUBOは完全に飽きましたが、今回は論理クイズ「犯人は誰だ？」を解いてみます。

【問題】A, B, C, Dの中に犯人が１人います。犯人は嘘をつき、他の人は本当のことを証言します。犯人は誰でしょうか？

A「Dが犯人だ」
B「僕は犯人ではない」
C「Aは犯人ではない」
D「Bが犯人だ」

紙とペンで解く

この手のクイズは犯人が２人いたり一般人は本当のことを言うか嘘を言うか気まぐれだったりしていくらでも複雑になるのですが、シンプルに嘘つきが１人の場合の簡単な解き方を紹介します。

まず、「～が犯人だ」を「～は犯人ではない」に言い換えます。次のように表を用意して、犯人ではないと証言された部分にNoを書き、Noの数を縦に集計します。Noが０個の人が犯人です。

ただ、通常はNoが０個の人はいません。そこで対角成分を無効にして集計します。これは犯人による「自分は犯人ではない」という証言を無効にするためです。これで答えが得られると思います。

QUBO式のおさらい

今回は基本の「ｎ個の量子ビットからｍ個を１にする」の他に

応用A3「２個の量子ビットが同時に１になったら報酬を与える」

応用A4「２個の量子ビットが同時に０になったら報酬を与える」

このあたりを使用します。

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

どうやってアニーリング（QUBO）で解くか？

さっきの問題はシンプルすぎたので、「犯人はA～Cの誰か」「A～Cは犯人ではない」のように複数人指定がある問題でやってみます。

問題（答えはここに置いておきます）

A「僕とCは犯人ではない」
B「犯人はA, C, Dの誰か」
C「Eは犯人ではない」
D「A, C, Eは犯人ではない」
E「犯人はA, Bのどちらか」

まず、各人に５個の量子ビット（A～E）を割り当てて、１になったら犯人とします。

強い条件として、５人の中に犯人が１人いるので「５個の量子ビットから１つだけ１になる」を設定します。

次に、各人の証言を「もし～なら～が成り立つ」というif文を使って言い換えます。「もし自分が正直者なら、自分の証言が成り立つ」という感じです。

「もしAが0なら、A, Cは0」
「もしBが0なら、A, C, Dのどれかが1」
「もしCが0なら、Eは0」
「もしDが0なら、A, C, Eは0」
「もしEが0なら、A, Bのどれかが1」

さらにこれを「◯◯かつ✕✕なら報酬を与える」に言い換えます。

A=0かつA=0なら報酬、A=0かつC=0なら報酬
B=0かつA=1なら報酬、B=0かつC=1なら報酬、B=0かつD=1なら報酬
C=0かつE=0なら報酬
D=0かつA=0なら報酬、D=0かつC=0なら報酬、D=0かつE=0なら報酬
E=0かつA=1なら報酬、E=0かつB=1なら報酬

例えば、「B=0かつC=1なら報酬」の部分は次のように設定できます。

H = -0.1 * ((1 - B) * C)

証言の重みを1にしてしまうと報酬欲しさに犯人を２人にしてしまうかもしれません。したがってここは弱い条件として重み0.1にします。

コードと結果

量子ビット名がA～Eである点は分かりやすいです。

from pyqubo import Binary
from dwave_qbsolv import QBSolv

#量子ビットを用意する
A = Binary('qA')
B = Binary('qB')
C = Binary('qC')
D = Binary('qD')
E = Binary('qE')

#5人の中に犯人が1人いる（強い条件）
H = 0
H += (A + B + C + D + E - 1)**2

#各人の証言（成り立てば弱い報酬）
H += -0.1 * ((1 - A) * (1 - A))
H += -0.1 * ((1 - A) * (1 - C))

H += -0.1 * ((1 - B) * A)
H += -0.1 * ((1 - B) * C)
H += -0.1 * ((1 - B) * D)

H += -0.1 * ((1 - C) * (1 - E))

H += -0.1 * ((1 - D) * (1 - A))
H += -0.1 * ((1 - D) * (1 - C))
H += -0.1 * ((1 - D) * (1 - E))

H += -0.1 * ((1 - E) * A)
H += -0.1 * ((1 - E) * B)


#コンパイル
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:[0, 1, 0, 0, 0] Energy:-1.1 Occurrence:501

Bが犯人だと分かりました。解のエネルギーは叶った報酬の数によりますがこれは問題からは予想が難しいと思われます（頑張れば分からなくはないですが）。

さいごに

もっと複雑なif文を表現できるようになりたいですね。「A=0かつB=1なら、C=1またはD=1」のような。中継ビットを使うとできるとかできないとか・・・