LoginSignup
4

More than 3 years have passed since last update.

posted at

updated 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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
4