論理演算
充足可能性問題
パズルを論理演算で解く
放課後、いつものようにアリスとボブが量子コンピュータクラブの教室に直行すると、ドアに不穏な張り紙を見つけました。
暗唱番号? アリスとボブは急いで教室のパソコンに向かうと、見たことのないロック画面が表示されています。
「なにこれイブがやったの!? はらたつのり!」アリスはいらつきましたが、すぐに冷静さを取り戻しました。 「ようは 3 つの数字を当てればいいってことね。それにしても、ヒントの ○ や △ ってどういう意味だろう?」。 ボブ「これ Wordle に似てない? つまり、数字と場所が合ってれば ○ で、数字は合ってるけど場所が違うときは △ なんだよきっと」。 アリス「なるほど。そうと分かれば、あてずっぽうに試して失敗するより、ちゃんとシステマチックに解いたほうが良さそうね」。 アリスの言うシステマチックとは、パズルを定式化して何らかのアリゴリズムに沿って機械的に解く、という意味です。
パズルを定式化する
実際このパズルは、次のように定式化できます。 数字が入る 3 つの箱をそれぞれ左から A, B, C と名付けます。 そして、たとえば A に数 8 が入る場合には変数 A8 = true となることにします。 この書き方を使うと、5 つのヒントはそれぞれ変数 A0, A1, ..., C9 を組合わせた論理式として書けます。これらの論理式のすべてを満たす変数 A0, A1, ..., C9 の値 true, false の組がみつかれば、それが最終的な答となります。
このように、ある論理式が与えられたときにそれを満たす変数の値 true, false の組をみつける問題を「充足可能性問題 (SAT)」と呼びます。 充足可能性問題は NP 完全問題として有名です。 NP 完全とはざっくり言えば「計算には時間がかかるが、答合わせは簡単にできる」という種類の問題です。 つまり論理式を満たす変数の値 true, false の組をみつける計算は大変ですが、代入して論理式が true になるかを確認するのは簡単です。
充足可能性問題は NP 完全問題の基本型であることでも有名です。 他の NP 完全問題には、巡回サラリーマン問題や整数計画問題、ゲームでは数独やテトリスなど様々な問題があります。 これらはすべて充足可能性問題の形に変換できます。 このため、充足可能性問題を (たとえば量子コンピュータを使って) 効率的に解くことが非常に重要なのです。
充足可能性問題を量子コンピュータで解くには、与えられた論理式を量子論理演算と位相論理演算を使って量子回路に変換します。 これにすべての true, false の重ね合わせを入力すれば、論理式を満たす true, false の組を並列に探索できます。
ヒント 1
ヒント 1 の「6, 8, 2 = ○」は、「A は 6」または「B は 8」または「C は 2」と書き直すことができます。
A が 6 である場合、A6 は true となります。 この場合 A には 8 や 2 は入らないので、A8 と A2 は
false となります。 さらにこの場合、B と C には 6 はもちろん, 8, 2 のいずれも入りません。
これをまとめて論理式で表すと
A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ ¬B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ ¬C2 と書けます以降では簡潔さのため、AND を ∧, OR を ∨, NOT を ¬ の記号で書きます。 同様に B が 8 である場合は ¬A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ ¬C2、C
が 2 である場合は ¬A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ ¬B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ C2 と書けます。
この 3 つを OR でつなげると、ヒント 1 は次の一つの論理式になります。
Hint1 = ( A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ ¬B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ ¬C2) ∨ // A には 6 が入る。または、 (¬A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ ¬C2) ∨ // B には 8 が入る。または、 (¬A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ ¬B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ C2) // C には 2 が入るこのようにして、すべてのヒントを論理式に変換していきます。
ヒント 2
6, 1, 4 = △ ということは、6 は B または C に入っているか、またはどれにも入っていないことが考えられます。 同様に 1 は A または C, もしくはどれにも入っていない可能性があります。 このようにすべての場合をまとめていくと、ヒント 2 は次のいずれか (OR) であることが分かります。
- A には 1 が入る
- A には 4 が入る
- B には 6 が入る
- B には 4 が入る
- C には 6 が入る
- C には 1 が入る
A に 1 が入っている場合、A には 6 と 4 は入りませんし、B と C には 6, 1, 4 のいずれも入りません。 このようにしてすべての場合を論理式にまとめて OR でつなげると、最終的にヒント 2 は次の論理式として書けます。
Hint2 = (¬A6 ∧ A1 ∧ ¬A4 ∧ ¬B6 ∧ ¬B1 ∧ ¬B4 ∧ ¬C6 ∧ ¬C1 ∧ ¬C4) ∨ // A には 1 が入る。または、 (¬A6 ∧ ¬A1 ∧ A4 ∧ ¬B6 ∧ ¬B1 ∧ ¬B4 ∧ ¬C6 ∧ ¬C1 ∧ ¬C4) ∨ // A には 4 が入る。または、 (¬A6 ∧ ¬A1 ∧ ¬A4 ∧ B6 ∧ ¬B1 ∧ ¬B4 ∧ ¬C6 ∧ ¬C1 ∧ ¬C4) ∨ // B には 6 が入る。または、 (¬A6 ∧ ¬A1 ∧ ¬A4 ∧ ¬B6 ∧ ¬B1 ∧ B4 ∧ ¬C6 ∧ ¬C1 ∧ ¬C4) ∨ // B には 4 が入る。または、 (¬A6 ∧ ¬A1 ∧ ¬A4 ∧ ¬B6 ∧ ¬B1 ∧ ¬B4 ∧ C6 ∧ ¬C1 ∧ ¬C4) ∨ // C には 6 が入る。または、 (¬A6 ∧ ¬A1 ∧ ¬A4 ∧ ¬B6 ∧ ¬B1 ∧ ¬B4 ∧ ¬C6 ∧ C1 ∧ ¬C4) // C には 1 が入る
ヒント 3
2,0,6 = △△ ということは、2 つの数だけ合っていてそれぞれの位置が異なるのですから、3 つの数の並びの組合わせは全部で次の 9 通りになります。
- 0, 2, ?
- 6, 2, ?
- 0, 6, ?
- 0, ?, 2
- 6, ?, 2
- 6, ?, 0
- ?, 2, 0
- ?, 6, 2
- ?, 6, 0
Hint3 = (¬A2 ∧ A0 ∧ ¬A6 ∧ B2 ∧ ¬B0 ∧ ¬B6 ∧ ¬C2 ∧ ¬C0 ∧ ¬C6) ∨ // 0, 2, ? または、 (¬A2 ∧ ¬A0 ∧ A6 ∧ B2 ∧ ¬B0 ∧ ¬B6 ∧ ¬C2 ∧ ¬C0 ∧ ¬C6) ∨ // 6, 2, ? または、 (¬A2 ∧ A0 ∧ ¬A6 ∧ ¬B2 ∧ ¬B0 ∧ B6 ∧ ¬C2 ∧ ¬C0 ∧ ¬C6) ∨ // 0, 6, ? または、 (¬A2 ∧ A0 ∧ ¬A6 ∧ ¬B2 ∧ ¬B0 ∧ ¬B6 ∧ C2 ∧ ¬C0 ∧ ¬C6) ∨ // 0, ?, 2 または、 (¬A2 ∧ ¬A0 ∧ A6 ∧ ¬B2 ∧ ¬B0 ∧ ¬B6 ∧ C2 ∧ ¬C0 ∧ ¬C6) ∨ // 6, ?, 2 または、 (¬A2 ∧ ¬A0 ∧ A6 ∧ ¬B2 ∧ ¬B0 ∧ ¬B6 ∧ ¬C2 ∧ C0 ∧ ¬C6) ∨ // 6, ?, 0 または、 (¬A2 ∧ ¬A0 ∧ ¬A6 ∧ B2 ∧ ¬B0 ∧ ¬B6 ∧ ¬C2 ∧ C0 ∧ ¬C6) ∨ // ?, 2, 0 または、 (¬A2 ∧ ¬A0 ∧ ¬A6 ∧ ¬B2 ∧ ¬B0 ∧ B6 ∧ C2 ∧ ¬C0 ∧ ¬C6) ∨ // ?, 6, 2 または、 (¬A2 ∧ ¬A0 ∧ ¬A6 ∧ ¬B2 ∧ ¬B0 ∧ B6 ∧ ¬C2 ∧ C0 ∧ ¬C6) // ?, 6, 0
ヒント 4
このヒントが言っていることは次の 3 つです。
- A は 7 ではない (¬A7)
- B は 3 ではない (¬B3)
- C は 8 ではない (¬C8)
これによって 3 つの変数 A7, B3, C8 の値は false に確定します。 これらの値を他の論理式に代入すれば変数を消すことができるので、論理式をより短いものに変換できます。
ヒント 5
ヒント 2 と同様に次の論理式を導けます。
Hint5 = (¬A8 ∧ A7 ∧ ¬A0 ∧ ¬B8 ∧ ¬B7 ∧ ¬B0 ∧ ¬C8 ∧ ¬C7 ∧ ¬C0) ∨ // A には 7 が入る。または、 (¬A8 ∧ ¬A7 ∧ A0 ∧ ¬B8 ∧ ¬B7 ∧ ¬B0 ∧ ¬C8 ∧ ¬C7 ∧ ¬C0) ∨ // A には 0 が入る。または、 (¬A8 ∧ ¬A7 ∧ ¬A0 ∧ B8 ∧ ¬B7 ∧ ¬B0 ∧ ¬C8 ∧ ¬C7 ∧ ¬C0) ∨ // B には 8 が入る。または、 (¬A8 ∧ ¬A7 ∧ ¬A0 ∧ ¬B8 ∧ ¬B7 ∧ B0 ∧ ¬C8 ∧ ¬C7 ∧ ¬C0) ∨ // B には 0 が入る。または、 (¬A8 ∧ ¬A7 ∧ ¬A0 ∧ ¬B8 ∧ ¬B7 ∧ ¬B0 ∧ C8 ∧ ¬C7 ∧ ¬C0) ∨ // C には 8 が入る。または、 (¬A8 ∧ ¬A7 ∧ ¬A0 ∧ ¬B8 ∧ ¬B7 ∧ ¬B0 ∧ ¬C8 ∧ C7 ∧ ¬C0) // C には 7 が入る
追加条件 1
それぞれの箱には少なくとも 1 つの数が入らなければなりません。 たとえば A には必ず 0 から 9 のうち一つの数が入るので、A0, A1, ... A9 のいずれかは true となります。 B, C についても同様に考えると、「それぞれの箱には少なくとも 1 つの数が入る」という論理式は次のようになります。
Cond1 = (A0 ∨ A1 ∨ A2 ∨ A3 ∨ A4 ∨ A5 ∨ A6 ∨ A7 ∨ A8 ∨ A9) ∧ // A には数が少なくとも 1 つ入る。かつ、 (B0 ∨ B1 ∨ B2 ∨ B3 ∨ B4 ∨ B5 ∨ B6 ∨ B7 ∨ B8 ∨ B9) ∧ // B には数が少なくとも 1 つ入る。かつ、 (C0 ∨ C1 ∨ C2 ∨ C3 ∨ C4 ∨ C5 ∨ C6 ∨ C7 ∨ C8 ∨ C9) // C には数が少なくとも 1 つ入る
追加条件 2
それぞれの箱には高々 1 つの数が入ります。 たとえば A に 0 が入っている場合、A0 は true ですが A1, A2, ..., A9 は false となります。 もしこれを指定しないと、A に複数の数が入る答が得られてしいまいます。 ほかの数 1, ..., 9 とすべての箱 B, C について同様に考えると、論理式は次のようになります。
Cond2 = ( A0 ∧ ¬A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5 ∧ ¬A6 ∧ ¬A7 ∧ ¬A8 ∧ ¬A9) ∨ (¬A0 ∧ A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5 ∧ ¬A6 ∧ ¬A7 ∧ ¬A8 ∧ ¬A9) ∨ (¬A0 ∧ ¬A1 ∧ A2 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5 ∧ ¬A6 ∧ ¬A7 ∧ ¬A8 ∧ ¬A9) ∨ (¬A0 ∧ ¬A1 ∧ ¬A2 ∧ A3 ∧ ¬A4 ∧ ¬A5 ∧ ¬A6 ∧ ¬A7 ∧ ¬A8 ∧ ¬A9) ∨ (¬A0 ∧ ¬A1 ∧ ¬A2 ∧ ¬A3 ∧ A4 ∧ ¬A5 ∧ ¬A6 ∧ ¬A7 ∧ ¬A8 ∧ ¬A9) ∨ (¬A0 ∧ ¬A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A4 ∧ A5 ∧ ¬A6 ∧ ¬A7 ∧ ¬A8 ∧ ¬A9) ∨ (¬A0 ∧ ¬A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5 ∧ A6 ∧ ¬A7 ∧ ¬A8 ∧ ¬A9) ∨ (¬A0 ∧ ¬A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5 ∧ ¬A6 ∧ A7 ∧ ¬A8 ∧ ¬A9) ∨ (¬A0 ∧ ¬A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5 ∧ ¬A6 ∧ ¬A7 ∧ A8 ∧ ¬A9) ∨ (¬A0 ∧ ¬A1 ∧ ¬A2 ∧ ¬A3 ∧ ¬A4 ∧ ¬A5 ∧ ¬A6 ∧ ¬A7 ∧ ¬A8 ∧ A9) ∨ ( B0 ∧ ¬B1 ∧ ¬B2 ∧ ¬B3 ∧ ¬B4 ∧ ¬B5 ∧ ¬B6 ∧ ¬B7 ∧ ¬B8 ∧ ¬B9) ∨ (¬B0 ∧ B1 ∧ ¬B2 ∧ ¬B3 ∧ ¬B4 ∧ ¬B5 ∧ ¬B6 ∧ ¬B7 ∧ ¬B8 ∧ ¬B9) ∨ (¬B0 ∧ ¬B1 ∧ B2 ∧ ¬B3 ∧ ¬B4 ∧ ¬B5 ∧ ¬B6 ∧ ¬B7 ∧ ¬B8 ∧ ¬B9) ∨ (¬B0 ∧ ¬B1 ∧ ¬B2 ∧ B3 ∧ ¬B4 ∧ ¬B5 ∧ ¬B6 ∧ ¬B7 ∧ ¬B8 ∧ ¬B9) ∨ (¬B0 ∧ ¬B1 ∧ ¬B2 ∧ ¬B3 ∧ B4 ∧ ¬B5 ∧ ¬B6 ∧ ¬B7 ∧ ¬B8 ∧ ¬B9) ∨ (¬B0 ∧ ¬B1 ∧ ¬B2 ∧ ¬B3 ∧ ¬B4 ∧ B5 ∧ ¬B6 ∧ ¬B7 ∧ ¬B8 ∧ ¬B9) ∨ (¬B0 ∧ ¬B1 ∧ ¬B2 ∧ ¬B3 ∧ ¬B4 ∧ ¬B5 ∧ B6 ∧ ¬B7 ∧ ¬B8 ∧ ¬B9) ∨ (¬B0 ∧ ¬B1 ∧ ¬B2 ∧ ¬B3 ∧ ¬B4 ∧ ¬B5 ∧ ¬B6 ∧ B7 ∧ ¬B8 ∧ ¬B9) ∨ (¬B0 ∧ ¬B1 ∧ ¬B2 ∧ ¬B3 ∧ ¬B4 ∧ ¬B5 ∧ ¬B6 ∧ ¬B7 ∧ B8 ∧ ¬B9) ∨ (¬B0 ∧ ¬B1 ∧ ¬B2 ∧ ¬B3 ∧ ¬B4 ∧ ¬B5 ∧ ¬B6 ∧ ¬B7 ∧ ¬B8 ∧ B9) ∨ ( C0 ∧ ¬C1 ∧ ¬C2 ∧ ¬C3 ∧ ¬C4 ∧ ¬C5 ∧ ¬C6 ∧ ¬C7 ∧ ¬C8 ∧ ¬C9) ∨ (¬C0 ∧ C1 ∧ ¬C2 ∧ ¬C3 ∧ ¬C4 ∧ ¬C5 ∧ ¬C6 ∧ ¬C7 ∧ ¬C8 ∧ ¬C9) ∨ (¬C0 ∧ ¬C1 ∧ C2 ∧ ¬C3 ∧ ¬C4 ∧ ¬C5 ∧ ¬C6 ∧ ¬C7 ∧ ¬C8 ∧ ¬C9) ∨ (¬C0 ∧ ¬C1 ∧ ¬C2 ∧ C3 ∧ ¬C4 ∧ ¬C5 ∧ ¬C6 ∧ ¬C7 ∧ ¬C8 ∧ ¬C9) ∨ (¬C0 ∧ ¬C1 ∧ ¬C2 ∧ ¬C3 ∧ C4 ∧ ¬C5 ∧ ¬C6 ∧ ¬C7 ∧ ¬C8 ∧ ¬C9) ∨ (¬C0 ∧ ¬C1 ∧ ¬C2 ∧ ¬C3 ∧ ¬C4 ∧ C5 ∧ ¬C6 ∧ ¬C7 ∧ ¬C8 ∧ ¬C9) ∨ (¬C0 ∧ ¬C1 ∧ ¬C2 ∧ ¬C3 ∧ ¬C4 ∧ ¬C5 ∧ C6 ∧ ¬C7 ∧ ¬C8 ∧ ¬C9) ∨ (¬C0 ∧ ¬C1 ∧ ¬C2 ∧ ¬C3 ∧ ¬C4 ∧ ¬C5 ∧ ¬C6 ∧ C7 ∧ ¬C8 ∧ ¬C9) ∨ (¬C0 ∧ ¬C1 ∧ ¬C2 ∧ ¬C3 ∧ ¬C4 ∧ ¬C5 ∧ ¬C6 ∧ ¬C7 ∧ C8 ∧ ¬C9) ∨ (¬C0 ∧ ¬C1 ∧ ¬C2 ∧ ¬C3 ∧ ¬C4 ∧ ¬C5 ∧ ¬C6 ∧ ¬C7 ∧ ¬C8 ∧ C9)
論理式の最適化
すべてのヒントと必要な追加条件を論理式にしたので、これらを AND でつなげば 1 つの論理式が求まります。
NumberPuzzle = Hint1 ∧ Hint2 ∧ Hint3 ∧ Hint4 ∧ Hint5 ∧ Cond1 ∧ Cond2
この論理式は巨大になります! これをそのまま量子回路に変換するにはとてもビット数が足りないので、論理式を整理 (最適化) してより短い論理式にしてみましょう。 論理式の最適化はたとえば Logic Calculator というサイトで簡単にできます。 たとえばヒント 1 の論理式は次のように短い論理式に変換できます。
Hint1 = ( A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ ¬B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ ¬C2) ∨ // A には 6 が入る (¬A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ ¬C2) ∨ // B には 8 が入る (¬A6 ∧ ¬A8 ∧ ¬A2 ∧ ¬B6 ∧ ¬B8 ∧ ¬B2 ∧ ¬C6 ∧ ¬C8 ∧ C2) // C には 2 が入る → (A6 ∧ ¬A2 ∧ ¬B6 ∧ ¬B2 ∧ ¬C6 ∧ ¬C2) ∨ (¬A6 ∧ ¬A2 ∧ ¬B6 ∧ ¬B2 ∧ ¬C6 ∧ C2) // 最適化後
このように最適化した各ヒントと追加条件を AND でつなぎあわせれば、最初のバージョンより短い論理式を生成できます。 これにさらに最適化をかけると、ヒント 4 のような答を絞りこむ追加条件によって変数が消えるため、最終的にとても短い論理式が生成されます。
A0 ∧ ¬A1 ∧ ¬A2 ∧ ¬A4 ∧ ¬A6 ∧ ¬B0 ∧ ¬B1 ∧ ¬B2 ∧ ¬B6 ∧ ¬C0 ∧ ¬C1 ∧ C2 ∧ ¬C6 ∧ (B4 ∨ A4 ∨ A1) ∧ (¬A1 ∨ ¬A4) ∧ (¬A4 ∨ B1) ∧ (¬A4 ∨ ¬B4) ∧ (¬A1 ∨ B1) ∧ (B4 ∨ A4 ∨ B1) ∧ (B4 ∨ B1) ∧ (¬A1 ∨ ¬B4)
これをよく見ると A0 と C2 には NOT 記号 ¬ がついていませんからそれぞれ true で、つまりこの時点で A には 0, C には 2 が入ることが決定しています。 よってこれらの変数を除けば、論理式はさらに短くできます。
¬A1 ∧ ¬A4 ∧ ¬B1 ∧ (B4 ∨ A4 ∨ A1) ∧ (¬A1 ∨ ¬A4) ∧ (¬A4 ∨ B1) ∧ (¬A4 ∨ ¬B4) ∧ (¬A1 ∨ B1) ∧ (B4 ∨ A4 ∨ B1) ∧ (B4 ∨ B1) ∧ (¬A1 ∨ ¬B4)
不明な変数は A1, A4, B1, B4 の 4 つです。この 4 つを求める量子回路は次のようになります。
回路の上から 4 つの量子ビットはそれぞれ A1, A4, B1, B4
の値に割り当て、それ以外は計算の一時ビットに使います。 回路では論理式中の
(B4 ∨ A4 ∨ A1)
といったひとつひとつの項を論理演算で計算し、一時ビットに結果を出力します。
そして最後にそれぞれの項の AND を位相論理演算で (つまり pAND で) 計算します。 最後に pAND
以外をアンコンピュートすることで、振幅は変化せず位相に書き込まれた結果のみが残ります。
実行結果を見ると、B4 の位相が反転しているので真ん中の箱 B の数は 4 で確定です。 すでに A は 0, C は 2 と確定していたので、答は 0, 4, 2 となります。
まとめ
充足可能性問題 (SAT) を量子コンピュータで解く方法を見てきました。 問題の論理式を量子回路として表し、最後の AND を pAND にすることで結果を位相に書き込むようにします。 そして論理式の各変数に true と false (1 と 0) の重ね合わせを入力することで、論理式を満たす答だけ振幅を反転させます。 ここから実際に答を取り出すのに必要な振幅増幅は、いよいよ次回に紹介します。