はじめに
4カード問題を出されたときに，「それ量子アニーリングで解けるよ」と言って，実際に解いてあげたい．そんな人向けの記事です．
4カード問題とは
次のような，とても有名な論理パズルです．ウェイソン選択課題とも言います．
4枚のカードがあります．左のカードから順に1, 4, F, Aと書かれています．
| 1 | 4 | F | A |
|---|
なお，カードの片面にはアルファベット1文字，もう一方の面には数字が書かれているとします．
このとき，次の命題が成立しているかどうかを確かめるために裏返すべきカードはどれでしょう？
「あるカードのアルファベットが母音の場合，もう一方の面の数字は偶数である」
答え
先に答えを書いておきます．もちろん「1」と「A」のカードです．
「1」のカードのアルファベットが母音だったら，命題が成り立ちませんし，「A」のカードの数字が奇数だったらやっぱり命題が成り立ちません．それらを確かめないといけません．
「4」のアルファベットは子音であっても構いませんし，「F」のカードの数字が奇数であっても偶数であっても，命題とは関係ありません．
ですが，これでは面白くない．ということで量子アニーリングです．
問題をQUBOで表現する
量子アニーリングを利用するために，問題をQUBOで表現しましょう．
カードに書かれたアルファベットが母音なら1となる変数 $x_i\in\{0,1\}$ を4個,カードに書かれた数字が偶数なら1となる変数 $y_i\in\{0,1\}$ を4個，用意します．
| 1 | 4 | F | A | |
|---|---|---|---|---|
| $x_i$ | 0 | 1 | ||
| $y_i$ | 0 | 1 | ||
| $i$ | 1 | 2 | 3 | 4 |
添字 $i$ は左のカードから順に1, 2, 3, 4と付けます．
こうすると，命題「あるカード $i$ のアルファベットが母音の場合，もう一方の面の数字は偶数である」が偽であること $\Leftrightarrow x_i(1-y_i)=1$ となります．
これを最小化したいペナルティと考えて問題を次のようにします．
\text{minimize} \quad \Sigma_i x_i(1-y_i)
さらに，解をカードの見えている部分と一致させるためのペナルティも置きます．
\text{minimize} \quad \Sigma_i x_i(1-y_i) + P \\
P=x_3^2 + (1-x_4)^2 + y_1^2 + (1-y_2)^2
展開すると，
（定数2が出てくるが，最小化に関係ないので削除）
\text{minimize} \quad x_1-x_1y_1 + x_2-x_2y_2 + 2x_3-x_3y_3 - x_4y_4 + y_1 - y_2 \\
\because x_i^2=x_i, y_i^2=y_i
となり，
\text{minimize} \quad x^\text{T}Qx\\
x = [x_1, \cdots, x_4, y_1, \cdots, y_4]^\text{T}
の形で表現すると， 上三角行列 $Q$ の$j$行$k$列目の要素 $q_{j,k}$ のうち非ゼロのものは，
q_{11}=1, q_{15}=-1, q_{22}=1, q_{26}=-1, \\
q_{33}=2, q_{37}=-1, q_{48}=-1, q_{55}=1, q_{66}=-1\\
となります．これでQUBOの形で問題が表現できました．
解いてみる
このQUBOをDWave社のqbsolvを使って解いてみます． （自分の環境ではDWaveマシンは呼び出せないので，qbsolv内のタブーサーチソルバで解を求めています．）
from dwave_qbsolv import QBSolv
Q = {(0, 0): 1,
(0, 4): -1,
(1, 1): 1,
(1, 5): -1,
(2, 2): 2,
(2, 6): -1,
(3, 7): -1,
(4, 4): 1,
(5, 5): -1}
response = QBSolv().sample_qubo(Q)
list(response.samples())
すると，解は次のように３通りでてきました．
[{0: 0, 1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 1, 7: 1},
{0: 0, 1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 1, 7: 1},
{0: 0, 1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1}]
また，最小化しようとしたペナルティの値は，
list(response.data_vectors['energy'])
[-2.0, -2.0, -2.0]
となっています．削除した定数2を考えると，全ての解においてペナルティはゼロで，命題が成り立っています．
解を見てみると，2番目と7番目の要素（$x_2$と$y_3$）については，1と0どちらも取る可能性があることがわかります．つまり，$x_2$と$y_3$の中身はどっちでも良いということなので，2枚目と3枚目のカードは裏返して確かめなくて良いということになります．
必然的に，裏返すべきは1枚目と4枚目，つまり「1」と「A」のカードで，「1」のアルファベットは子音($x_1=0$)，「A」の数字は偶数($y_4=1$)でないといけない，ということがわかります．
環境
Python 3.6.3
dwave-qbsolv 0.2.7
おわりに
4カード問題を出されて本当にこんな返しをしたら，どうなるかは知りません．そんな人いないとは思いますが……