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

はい、どーも。みなさま D-Wave はご存知でせうか。量子アニーリングなる不思議な手法により、ちょっぱやで最適化問題を解けたり解けなかったりする、なんかすごいマシンです。
それではですねー、今日はこの[ピクロス (a.k.a お絵かきロジック) ](https://ja.wikipedia.org/wiki/%E3%81%8A%E7%B5%B5%E3%81%8B%E3%81%8D%E3%83%AD%E3%82%B8%E3%83%83%E3%82%AF)を解いていこうと思います。

|          | 1   | 1, 1 | 1   | 2   |
| :---     | --- | ---  | --- | --- |
| **2**    |     | ■    | ■   |     |
| **1, 1** | ■   |      |     | ■   |
| **1, 1** |     | ■    |     | ■   |

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

```python
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
```

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

```python
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)
```

できあがったイジングモデルがこちらになります。
あら不思議、制約充足問題が最小化問題になっていまいましました。[どゆこと〜](https://qiita.com/piyo7/items/5782576aa97b7449a3cf)

```python
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 先輩を呼びだして

```python
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。

```python
from dwave.system.samplers import DWaveSampler
from dwave.system.composites import EmbeddingComposite

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

からのー

```python
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 に分裂してるのは、キメラグラフに埋め込んだときに補助量子ビットが導入されて、そこの観測値に差異があるとかなのかなぁ。そう、たぶん、きっと、そう。

なお調子に乗って[６行４列のピクロス](https://www.nonograms.org/nonograms/i/4353)も解こうとしたけど無事爆死した模様。
エネルギーギャップとかキメラグラフ埋め込みとかアニーリングスケジュールとか、なにもかもライブラリのデフォルト任せなので、まぁ人生そんなもんじゃないですかね。

あっ、今回の実験結果は GitHub にも置いてますん。
https://github.com/piyo7/dwave-playground/blob/master/jupyter/nonogram.ipynb