Python
量子コンピュータ
量子アニーリング
qubo
wildcat

(2018年11月追記)※wildcatは現在、記事執筆当初から大きく仕様やAPIが変わっています。最新版にも移植しましたので、こちらの記事もご覧ください。


wildcatってなんだ?

Wildcatとは、量子コンピュータ系ベンチャーのMDR社が開発した量子アニーリングっぽい問題を解くためのライブラリで、MDR社のAPIを叩いて結果を取ってくる仕組みになっています。

今のところは、登録不要でサーバが落ちない程度試せる、らしいです。

https://github.com/mdrft/wildcat

pipでインストールする方法も書かれていますが、まだできたばかりなので更新が多いかもしれないと思って、git cloneして、同じディレクトリにJupyter Notebook作ってやってます。


解きたい問題

手始めに、4x4の数独を解かせてみました。

解く問題は、次の問題とします。

1? ??

?? 2?

?3 ??
?? ?4

ちなみに、答えは

12 43

34 21

43 12
21 34

になります。


量子アニーリングで数独、どう解く?

QUBOという形に落とし込んで解きます。

量子アニーリングやQUBOについては

量子アニーリング、イジングモデルとフレームワーク

QUBOを使って日本地図の彩色問題やってみた

を参照ください。


QUBOを作る

QUBOとは

H=\sum_{i,j}Q_{ij}x_ix_j

の、Hを最小にするように $x_i \in { 0, 1 }$ を発見する最適化問題でした。

QUBOを作るときに考えないといけないのは、 $x_i$ とは何を表現する量か、そのためにQをどのようにしたらいいか、です。


xiで何を表現するか

まず、4x4のマス目に数字を割り振ります。

 0  1 |  2  3

4 5 | 6 7
------+-------
8 9 | 10 11
12 13 | 14 15

$x_i$ に、好きな整数を入れられたら、これで終わるのですが、 $x_i$ は0か1しか入らないので、 $x_i$ は次のようにします。

i = 0..15: $x_i$ が1のとき、マス目iに数字1が入っている

i = 16..31: $x_i$ が1のとき、マス目(i-16)に数字2が入っている

i = 32..47: $x_i$ が1のとき、マス目(i-32)に数字3が入っている

i = 48..63: $x_i$ が1のとき、マス目(i-48)に数字4が入っている

このように、 $x_0$ から $x_{63}$ を定めることにします。


Qをどう作るか

ナンプレの制約条件は、以下のように言えます。


  • 全部のマス目を埋めること。?のままは許されない

  • ひとつのマス目には、ひとつしか数字が入らない

  • 同じ列に、同じ数字がないこと

  • 同じ行に、同じ数字がないこと

  • 同じブロックに、同じ数字がないこと

  • 最初から問題文に書かれている数字は書き換えないこと

これらの条件を守ったときに $H=\sum_{i,j}Q_{ij}x_ix_j$ が最小となるよう、Qを作成します。

下準備として、行、列、ブロックや問題文を作っておきます。

n = 4**3

grouping = [
# rows
[ 0, 1, 2, 3],
[ 4, 5, 6, 7],
[ 8, 9, 10, 11],
[12, 13, 14, 15],
# columns
[ 0, 4, 8, 12],
[ 1, 5, 9, 13],
[ 2, 6, 10, 14],
[ 3, 7, 11, 15],
# blocks
[ 0, 1, 4, 5],
[ 2, 3, 6, 7],
[ 8, 9, 12, 13],
[10, 11, 14, 15],
]
problem_str = '1?????2??3?????4'

続いて、QUBOを作っていきます。

# なにか数字を埋めると報酬(Hが小さくなる)がもらえるようにする

qubo = np.eye(n) * -1

# 行、列、ブロックに同じ数字があったら、ペナルティ(Hが大きくなる)を与えるようにする
for g in grouping:
for i in range(4):
for j in range(3):
for k in range(j+1, 4):
qubo[i*16 + g[j], i*16 + g[k]] += 2

# 同じマスには別の数字が入らないようにペナルティを与える
for i in range(16):
for j in range(3):
for k in range(j+1, k):
qubo[i+j*16, i+k*16] += 2.5

# 既に問題文に数字が入っている場合、そこには別の数字を入れないように報酬やペナルティを調整する
for i, v in enumerate(problem_str):
if v == '?':
continue
v = int(v) - 1
qubo[v*16 + i, v*16 + i] -= 20
for j in range(4):
qubo[j*16 + i, j*16 + i] += 4
for g in grouping:
if i not in g:
continue
for j in g:
qubo[v*16 + j, v*16 + j] += 3 + v*0.3

いろいろと係数が入っていますが、正直、勘でやっています。今のがベストじゃない可能性も多いにあります。

符号が逆じゃないこと、制約を無視した最適化が行われないことは必須ですが、そうならない範囲で、いろいろと調整の余地はあるはずなのです。


wildcatで解く

次のように、WildcatにQUBOを渡します。

from wildcat.util.matrix import random_symmetric_matrix

from wildcat.solver.qubo_solver import QuboSolver

solver = QuboSolver(qubo)

foo = None
def callback(arrangement):
global foo
foo = arrangement
print(sum(foo>0))
solver.solve(callback).result()

なお、solver.solveFutureオブジェクトを返します。また、計算が終わるとcallbackを呼び出します。

本来は非同期のお作法に従うといいのですが、Jupyter Notebookなどで試す場合には、こんなもんでいいのかな、と思います。


結果

board = ['?'] * 16

for i,b in enumerate(foo.tolist()):
if b == 1:
#if board[i%16] != '?':
# print('!', end='')
board[i%16] = (i//16) + 1

print('''{}{} {}{}
{}{} {}{}

{}{} {}{}
{}{} {}{}'''.format(*board))

とすると、

12 43

34 21

43 12
21 34

が表示されるはずです。

が、実際には、たまにしか完答できません。

アニーリングによる最適化は割と運ゲーなのと、Qのところの係数の調整がまだ甘かったりするようで、何度か QuboSolver を動かしていると、そのうち答えが合うはずです。


ノートブックはこちら

https://github.com/gyu-don/wildcat/blob/master/Number%20Place%204x4.ipynb