Edited at

D-Waveによる量子アニーリングで3行4列のピクロスをノリで解いてみた

はい、どーも。みなさま D-Wave はご存知でせうか。量子アニーリングなる不思議な手法により、ちょっぱやで最適化問題を解けたり解けなかったりする、なんかすごいマシンです。

それではですねー、今日はこのピクロス (a.k.a お絵かきロジック) を解いていこうと思います。

1
1, 1
1
2

2


1, 1

1, 1

とりま行・列を数える関数を用意しましてー

def len_lines(qs):

cont = False
result = []
for q in qs:
if q == 0:
cont = False
else:
if cont:
result[-1] += 1
else:
result.append(1)
cont = True
return result

制約をかけていきましょー。

import dwavebinarycsp as dbc

row_constraints = [[2], [1, 1], [1, 1]]
col_constraints = [[1], [1, 1], [1], [2]]

csp = dbc.ConstraintSatisfactionProblem(dbc.BINARY)
for i, lengths in enumerate(row_constraints):
csp.add_constraint(lambda *qs, lengths=lengths: len_lines(qs) == lengths, [f'q{i}{j}' for j in range(len(col_constraints))])
for j, lengths in enumerate(col_constraints):
csp.add_constraint(lambda *qs, lengths=lengths: len_lines(qs) == lengths, [f'q{i}{j}' for i in range(len(row_constraints))])

bqm = dbc.stitch(csp)
print(bqm)

できあがったイジングモデルがこちらになります。

あら不思議、制約充足問題が最小化問題になっていまいましました。どゆこと〜

BinaryQuadraticModel({'q00': 0.0, 'q01': -4.0, 'q02': -2.0, 'q03': -2.0, 'q10': -4.0, 'q11': 0.0, 'q12': -2.0, 'q13': -4.0, 'q20': -4.0, 'q21': -4.0, 'q22': -2.0, 'q23': -4.0}, {('q01', 'q00'): -4.0, ('q02', 'q00'): 4.0, ('q02', 'q01'): -2.0, ('q03', 'q00'): -2.0, ('q03', 'q01'): 4.0, ('q03', 'q02'): -2.0, ('q11', 'q10'): 4.0, ('q12', 'q10'): -2.0, ('q12', 'q11'): -2.0, ('q13', 'q10'): 0.0, ('q13', 'q11'): -2.0, ('q13', 'q12'): 4.0, ('q21', 'q20'): 4.0, ('q22', 'q20'): -2.0, ('q22', 'q21'): -2.0, ('q23', 'q20'): 0.0, ('q23', 'q21'): -2.0, ('q23', 'q22'): 4.0, ('q10', 'q00'): 4.0, ('q20', 'q00'): 4.0, ('q20', 'q10'): 4.0, ('q11', 'q01'): 4.0, ('q21', 'q01'): -4.0, ('q21', 'q11'): 4.0, ('q12', 'q02'): 4.0, ('q22', 'q02'): 4.0, ('q22', 'q12'): 4.0, ('q13', 'q03'): 0.0, ('q23', 'q03'): 4.0, ('q23', 'q13'): 0.0}, 7.5, Vartype.BINARY)

これだとちょっち読みにくいので sympy 先輩を呼びだして

import sympy

expr = bqm.offset
for symb, coef in bqm.linear.items():
expr += sympy.symbols(symb) * coef
for (symb1, symb2), coef in bqm.quadratic.items():
expr += sympy.symbols(symb1) * sympy.symbols(symb2) * coef

sympy.init_printing()
print(expr)

数式表示するであります。ふんふん、なるほどなー。


-4.0⋅q₀₀⋅q₀₁ + 4.0⋅q₀₀⋅q₀₂ - 2.0⋅q₀₀⋅q₀₃ + 4.0⋅q₀₀⋅q₁₀ + 4.0⋅q₀₀⋅q₂₀ - 2.0⋅q₀₁⋅q₀₂ + 4.0⋅q₀₁⋅q₀₃ + 4.0⋅q₀₁⋅q₁₁ - 4.0⋅q₀₁⋅q₂₁ - 4.0⋅q₀₁ - 2.0⋅q₀₂⋅q₀₃ + 4.0⋅q₀₂⋅q₁₂ + 4.0⋅q₀₂⋅q₂₂ - 2.0⋅q₀₂ + 4.0⋅q₀₃⋅q₂₃ - 2.0⋅q₀₃ + 4.0⋅q₁₀⋅q₁₁ - 2.0⋅q₁₀⋅q₁₂ + 4.0⋅q₁₀⋅q₂₀ - 4.0⋅q₁₀ - 2.0⋅q₁₁⋅q₁₂ - 2.0⋅q₁₁⋅q₁₃ + 4.0⋅q₁₁⋅q₂₁ + 4.0⋅q₁₂⋅q₁₃ + 4.0⋅q₁₂⋅q₂₂ - 2.0⋅q₁₂ - 4.0⋅q₁₃ + 4.0⋅q₂₀⋅q₂₁ - 2.0⋅q₂₀⋅q₂₂ - 4.0⋅q₂₀ - 2.0⋅q₂₁⋅q₂₂ - 2.0⋅q₂₁⋅q₂₃ - 4.0⋅q₂₁ + 4.0⋅q₂₂⋅q₂₃ - 2.0⋅q₂₂ - 4.0⋅q₂₃ + 7.5


それではおもむろに、この可愛いやつを D-Wave の実機に投げていきますぞ。やっちゃえ 2000Q。

from dwave.system.samplers import DWaveSampler

from dwave.system.composites import EmbeddingComposite

sampler = EmbeddingComposite(DWaveSampler())
response = sampler.sample(bqm, num_reads=100)

からのー

import pandas as pd

pd.DataFrame([{'num': num_occurrences, 'csp': csp.check(sample), **sample} for sample, energy, num_occurrences, chain_break_fraction in response.data()])

サンプリング結果表示をばー。

num
csp
q00
q01
q02
q03
q10
q11
q12
q13
q20
q21
q22
q23

31
True
0
1
1
0
1
0
0
1
0
1
0
1

1
True
0
1
1
0
1
0
0
1
0
1
0
1

19
False
1
1
1
0
1
0
0
1
0
1
0
1

48
False
1
1
1
0
1
0
0
1
0
1
0
1

1
False
1
1
1
0
1
0
1
1
0
1
0
1

おー、やってんねぇ。

32% の確率で解けてますな。正解のサンプル数が 31 と 1 に分裂してるのは、キメラグラフに埋め込んだときに補助量子ビットが導入されて、そこの観測値に差異があるとかなのかなぁ。そう、たぶん、きっと、そう。

なお調子に乗って6行4列のピクロスも解こうとしたけど無事爆死した模様。

エネルギーギャップとかキメラグラフ埋め込みとかアニーリングスケジュールとか、なにもかもライブラリのデフォルト任せなので、まぁ人生そんなもんじゃないですかね。

あっ、今回の実験結果は GitHub にも置いてますん。

https://github.com/piyo7/dwave-playground/blob/master/jupyter/nonogram.ipynb