はい、どーも。みなさま 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 に分裂してるのは、キメラグラフに埋め込んだときに補助量子ビットが導入されて、そこの観測値に差異があるとかなのかなぁ。そう、たぶん、きっと、そう。
なお調子に乗って６行４列のピクロスも解こうとしたけど無事爆死した模様。
エネルギーギャップとかキメラグラフ埋め込みとかアニーリングスケジュールとか、なにもかもライブラリのデフォルト任せなので、まぁ人生そんなもんじゃないですかね。
あっ、今回の実験結果は GitHub にも置いてますん。
https://github.com/piyo7/dwave-playground/blob/master/jupyter/nonogram.ipynb