やること
量子アニーリングはお絵かきロジック（ロジックアート、ピクロス(by任天堂)）のようなマス目のパズルと相性が良いです。今回は量子アニーリングでこちらの問題を解いてみましょう。
おさらい
量子アニーリングでは次の２つの条件設定が使えます。
「ｎ個の量子ビットからｍ個を１にする」
「量子ビットaと量子ビットbが同時に１になったらペナルティ（報酬）を与える」
2023/5/09追記：QUBOで設定可能な条件式まとめもご参照ください↓
どうやってお絵かきロジックを解くのか
一行だけ取り出して考えてみます。
２以上の単発の数字の場合は、「ｎ個の量子ビットからｍ個を１にする」を使って合計数を指定し、さらに、「量子ビットaと量子ビットbが同時に１になったら報酬を与える」を使ってできるだけ隣り合うマスが同時に１になるようにします。
１が並ぶスプリットは、同様に合計数を指定し、こちらは「量子ビットaと量子ビットbが同時に１になったらペナルティを与える」を使ってできるだけ隣り合うマスが同時に１にならないようにします。
念のため、弱い制約の報酬を0.1に弱めている理由を書いておきます。もし報酬が１の場合、合計数を無視したときのエネルギー増加（＋１）と追加隣接報酬（－１）が釣り合ってしまい、やり取りが行われてしまうからです。
また、今回の問題にはないですが [1, 2] のようなスプリットは対象外とします。Fixstars Amplifyさんのピクロスチュートリアルでは任意のスプリットを設定しています → 量子アニーリングマシン・イジングマシンによるピクロスの解法
実行環境
WinPython3.6をおすすめしています。
Google Colaboratoryが利用可能です。
準備
量子ビットを25個用意します。
import numpy as np
from pyqubo import Binary
from dwave.system.composites import EmbeddingComposite
from dwave.system.samplers import DWaveSampler
#量子ビットを用意する
q00 = Binary('q00')
q01 = Binary('q01')
q02 = Binary('q02')
q03 = Binary('q03')
q04 = Binary('q04')
q05 = Binary('q05')
q06 = Binary('q06')
q07 = Binary('q07')
q08 = Binary('q08')
q09 = Binary('q09')
q10 = Binary('q10')
q11 = Binary('q11')
q12 = Binary('q12')
q13 = Binary('q13')
q14 = Binary('q14')
q15 = Binary('q15')
q16 = Binary('q16')
q17 = Binary('q17')
q18 = Binary('q18')
q19 = Binary('q19')
q20 = Binary('q20')
q21 = Binary('q21')
q22 = Binary('q22')
q23 = Binary('q23')
q24 = Binary('q24')強い制約と弱い制約
数字をしっかり確認してください。
#各行、個数の制約
H = 0
H += (q00 + q01 + q02 + q03 + q04 - 2)**2
H += (q05 + q06 + q07 + q08 + q09 - 3)**2
H += (q10 + q11 + q12 + q13 + q14 - 3)**2
H += (q15 + q16 + q17 + q18 + q19 - 3)**2
H += (q20 + q21 + q22 + q23 + q24 - 2)**2
#各列、個数の制約
H += (q00 + q05 + q10 + q15 + q20 - 3)**2
H += (q01 + q06 + q11 + q16 + q21 - 2)**2
H += (q02 + q07 + q12 + q17 + q22 - 5)**2
H += (q03 + q08 + q13 + q18 + q23 - 2)**2
H += (q04 + q09 + q14 + q19 + q24 - 1)**2
#各行、連続の報酬
H += -0.1 * (q00 * q01) -0.1 * (q01 * q02) -0.1 * (q02 * q03) -0.1 * (q03 * q04)
H += -0.1 * (q05 * q06) -0.1 * (q06 * q07) -0.1 * (q07 * q08) -0.1 * (q08 * q09)
H += -0.1 * (q10 * q11) -0.1 * (q11 * q12) -0.1 * (q12 * q13) -0.1 * (q13 * q14)
H += -0.1 * (q15 * q16) -0.1 * (q16 * q17) -0.1 * (q17 * q18) -0.1 * (q18 * q19)
#[1, 1]スプリットは後ほど設定
#各列、連続の報酬
H += -0.1 * (q00 * q05) -0.1 * (q05 * q10) -0.1 * (q10 * q15) -0.1 * (q15 * q20)
H += -0.1 * (q01 * q06) -0.1 * (q06 * q11) -0.1 * (q11 * q16) -0.1 * (q16 * q21)
H += -0.1 * (q02 * q07) -0.1 * (q07 * q12) -0.1 * (q12 * q17) -0.1 * (q17 * q22)
H += -0.1 * (q03 * q08) -0.1 * (q08 * q13) -0.1 * (q13 * q18) -0.1 * (q18 * q23)
#[1]の列は連続設定は不要
#[1, 1]スプリット列のペナルティ
H += 0.1 * (q20 * q21) + 0.1 * (q21 * q22) + 0.1 * (q22 * q23) + 0.1 * (q23 * q24)アニーリング実行
あとはお決まりの実行です。サンプリング回数は1000にしました。
#コンパイル
model = H.compile()
qubo, offset = model.to_qubo()
print('qubo\n{}'.format(qubo))
#D-waveの設定
sampler = EmbeddingComposite(DWaveSampler(endpoint='https://cloud.dwavesys.com/sapi',
token='your_token', #あなたのAPIトークンを記入
solver='DW_2000Q_6')) #利用可能なソルバーを指定
#サンプリングしまくる
response = sampler.sample_qubo(qubo, num_reads=1000)
#レスポンスの確認
print('response')
for (sample, energy, occurrence, _) in response.data():
print('Sample:{} Energy:{} Occurrence:{}'.format(list(sample.values()), energy, occurrence))response
Sample:[0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0] Energy:-79.5 Occurrence:1
Sample:[1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0] Energy:-79.3 Occurrence:1
Sample:[0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0] Energy:-79.2 Occurrence:1
Sample:[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0] Energy:-79.2 Occurrence:1
Sample:[1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0] Energy:-79.2 Occurrence:2
（以下略）一番エネルギーが低い解を５×５に並べ直すと次の通り。
Sample:[0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]
[[0 0 1 1 0]
[0 0 1 1 1]
[1 1 1 0 0]
[1 1 1 0 0]
[1 0 1 0 0]]無事に犬が得られました。
num_reads=2000 にしてもまだヒット率が低いようなので、過去記事で紹介している分割サンプリングの方法を使っても良いかもしれません。
さいごに
[1, 2] のようなスプリットも設定できれば、もっと大きい問題が解けるようになりますね。
また、スターバトル（Star Battle）というパズルもこの方法で解けそうです。
