量子アニーリング（QUBO）でライツアウト（lights out）を解く

AI要約
やること
例題
おさらい
定式化
おわりに

AI要約

パズル「ライツアウト」を量子アニーリング（QUBO）で攻略します。各マスの「反転回数の偶奇」に着目してQUBO形式に落とし込み、TYTANを用いてサンプリングします。補助量子ビットの数を削減する工夫にも注目です。

やること

ライツアウトはすでに「遺伝的アルゴリズム」でも「理論」でも解いたのですが、

QUBOの練習にもピッタリなので、ちゃっかり量子アニーリングでも解いてみましょう。

例題

以前も使用したこちらの例題。

赤丸のマスをクリックするとすべてのライトが消えます。解は４種類ありますがこれが最小手数の解です。

おさらい

こちらの３パターンの条件設定を使います。久しぶりの降順制約ですね。忘れたときにやってくる。

基本「ｎ個の量子ビットからｍ個を１にする」
C1「2個の量子ビットを降順にする」
D2　解が0と1だけの方程式（右辺が複数）

定式化

各マスに量子ビットを割り当て、クリックするかどうかを０／１で表すこととします。（25個）

ここで制約条件を考えます。消灯マスが消灯のままでいるためには「偶数回」反転する必要があります。つまり、自身を中心とする十字のマス（場所によって３～５マス）の合計が [0 or 2 or 4] と等しくなればOKです。逆に、点灯マスが消灯するためには、十字マスの合計が [1 or 3 or 5] と等しくなる必要があります。

この方程式制約をシンプルに作るなら、各マスに３個の補助量子ビットを割り当てて [1 or 3 or 5] を表現することになるでしょう。

#補助量子ビットをワンホット
H += (s0 + s1 + s2 - 1)**2

#十字マス（5マス）の合計が [1 or 3 or 5] と等しくなる
H += ((q0 + q1 + q2 + q3 + q4) - (1*s0 + 3*s1 + 5*s2))**2

しかし、もっと量子ビットを節約する~~空前絶後の~~アイデアがあります。各マスの補助量子ビットを２個にすると、そのパターンは [0, 0]／[0, 1]／[1, 0]／[1, 1] の４通りで合計を取ると [0 or 1 or 2] となり、２倍して１を足せば [1 or 3 or 5] を表現できるのです。

ただしこのままでは一つの解に対して補助量子ビットの[0, 1]／[1, 0]のバリエーションが無数に出てしまって探索に無駄が発生するので、[0, 1]のパターンをブロックするために降順制約を与えます。つまり、補助量子ビットが [0, 0]／[1, 0]／[1, 1] の３パターンしか出ないように制限します。

#補助量子ビットを降順
H += (1 - s0) * s1

#十字マス（5マス）の合計が [1 or 3 or 5] と等しくなる
H += ((q0 + q1 + q2 + q3 + q4) - (1 + 2*(s0 + s1)))**2

その他に、最小手数の解を出すために全体に対して０になりやすい圧力もかけます。

import numpy as np
from copy import deepcopy
from tytan import *

#パズルの記述
lights = ['---#-',
          '---##',
          '--##-',
          '#-###',
          '##-##']


#パズルをプレイする関数
def play(lights, ans):
    #盤面をコピー
    lights_copy = deepcopy(lights)
    
    #盤面に対して答えを十字型に足し込む
    lights_copy[:, :] += ans[:, :]
    lights_copy[1:, :] += ans[:-1, :]
    lights_copy[:-1, :] += ans[1:, :]
    lights_copy[:, 1:] += ans[:, :-1]
    lights_copy[:, :-1] += ans[:, 1:]
    
    #偶数回返されたマスは０、奇数回は１とする
    lights_copy = lights_copy % 2
    
    return lights_copy

#変換
lights_tmp = []
for line in lights:
    line = line.replace('-', '0')
    line = line.replace('#', '1')
    lights_tmp.append(list(line))
lights = np.array(lights_tmp, dtype=int)
print(f'lights = \n{lights}')

#サイズ
h, w = lights.shape
print(f'(h, w) = ({h}, {w})')

#量子ビット
q = symbols_list([h, w], 'q{}_{}')

#補助量子ビット
s = symbols_list([h, w, 2], 's{}_{}_{}')

#補助量子ビットを降順
Hconst1 = 0
for i in range(h):
    for j in range(w):
        Hconst1 += (1 - s[i, j, 0]) * s[i, j, 1]

#全マスを消灯させる
Hconst2 = 0
for i in range(h):
    for j in range(w):
        #ここを中心とする十字マスの量子ビットを集める
        jujimasu = q[i, j]
        if i-1 >= 0:
            jujimasu += q[i-1, j]
        if i+1 < h:
            jujimasu += q[i+1, j]
        if j-1 >= 0:
            jujimasu += q[i, j-1]
        if j+1 < w:
            jujimasu += q[i, j+1]
        
        #ここが消灯マスなら十字マスの合計が [0 or 2 or 4]個
        if lights[i, j] == 0:
            Hconst2 += (np.sum(jujimasu) - (0 + 2*np.sum(s[i, j])))**2
        else:
            #ここが点灯マスなら十字マスの合計が [1 or 3 or 5]個
            Hconst2 += (np.sum(jujimasu) - (1 + 2*np.sum(s[i, j])))**2

#最小手数にする
Hcost = 0
for i in range(h):
    for j in range(w):
        Hcost += (q[i, j] - 0)**2

#合体
H = Hconst1 + Hconst2 + 0.01*Hcost

#コンパイル
qubo, offset = Compile(H).get_qubo()
print(f'offset = {offset}')

#サンプラー選択
solver = sampler.ArminSampler()

#サンプリング
result = solver.run(qubo, shots=5000, T_num=20000)

#上位3件
for r in result[:3]:
    print(f'Energy {r[1]}, Occurrence {r[2]}')
    
    #配列
    ans, _ = Auto_array(r[0]).get_ndarray('q{}_{}')
    print(f'ans = \n{ans}')
    
    #プレイ結果
    result = play(lights, ans)
    print(f'result = \n{result}')

lights = 
[[0 0 0 1 0]
 [0 0 0 1 1]
 [0 0 1 1 0]
 [1 0 1 1 1]
 [1 1 0 1 1]]
(h, w) = (5, 5)
offset = 13.0
MODE: GPU
DEVICE: cuda:0
Energy -12.920001983642578, Occurrence 3
ans = 
[[1 0 0 0 0]
 [1 1 0 1 0]
 [1 0 0 0 0]
 [0 0 1 0 0]
 [0 1 0 0 1]]
result = 
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]]
Energy -12.879999160766602, Occurrence 1
ans = 
[[0 1 0 1 1]
 [1 1 0 1 0]
 [0 1 0 1 1]
 [0 0 1 0 0]
 [1 0 0 1 0]]
result = 
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]]
Energy -12.879997253417969, Occurrence 1
ans = 
[[0 0 1 0 1]
 [0 1 1 1 1]
 [1 0 0 0 0]
 [1 0 0 0 1]
 [1 1 1 0 0]]
result = 
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]]

結果、第１位の解が模範解答と一致しています。

ans = 
[[1 0 0 0 0]
 [1 1 0 1 0]
 [1 0 0 0 0]
 [0 0 1 0 0]
 [0 1 0 0 1]]

それに続く解は最小手数ではない別解たちです。（理論記事の方と見比べると一致しています）

プレイ結果もきちんとオール消灯になっていますね。完全勝利 (✌ ･ω･ ✌)

おわりに

こいついつもパズル解いてるな ( ˘ω˘ ; )