2019年2月8日 更新

量子アニーリングを駆使して数独を解いてみた

先日,量子アニーリングの勉強会に参加して来ました.そのアウトプットとして,今回,数独ソルバーを作ってみます.

4,208 view お気に入り 1
変数 qi は0または1の値しかとらないので,qi**2 == qi が成立します.これを先程得た式に反映させます.0はその変数を採用しない,1はその変数を採用することを意味します.
for q in re.findall(r'q[0-9]{3}\*\*2', str(E)):
    q = q.replace('**2', '')
    E = E.subs(Symbol(q)**2, Symbol(q))
その5.py
量子アニーリングで先程の式を最小化するため QUBO 行列を作成します.
qubo = pd.DataFrame(index=df['q'].tolist(), columns=df['q'].tolist())

coeff_di = E.as_coefficients_dict()
for var, coeff in coeff_di.items():
    if var == 1:
        continue
        
    var = str(var).split('*')
    if len(var)==1:
        qubo.loc[var[0], var[0]] = int(coeff)
        
    if len(var)==2:
        qubo.loc[var[0], var[1]] = int(coeff)
        
qubo.to_csv('qubo.csv')
qubo = qubo.fillna(0)
その6.py
 (5368)

152×152の QUBO 行列を CSV ファイルに出力しました.行列の要素には,先程得た式の係数が入ります.
MDR の Wildqat と呼ばれる量子アニーリング型のシミュレーション計算を行うライブラリを使用して,先程得た式を最小化していきます.最小値が0になるまで何度も計算を繰り返します.
E_lowest = 100000
i = 0
while True:
    i += 1
    a = wildqat.opt()
    a.qubo = qubo.values
    pred = a.run()
    print('{}/{}: {}'.format(i+1, 100, a.E[-1] + coeff_di[1]))
    if a.E[-1] + coeff_di[1] == 0:
        pred_best = pred
        break
その7.py
得た解が正しいかを検証したところ,正しい解が得られていました.
output_qubo = df.loc[np.array(pred_best)==1, 'q']
for q in output_qubo:
    row = int(q[1])
    col = int(q[2])
    candidate = int(q[3])
    quiz[row, col] = candidate
    
np.array_equal(quiz, sol)
その8.py
24 件

関連する記事 こんな記事も人気です♪

Morphology (モルフォロジー) 変換の実装 ~ Python + OpenCV ~

Morphology (モルフォロジー) 変換の実装 ~ Python + OpenCV ~

画像処理の一つ,モルフォロジー変換をPython と OpenCVのライブラリを用いて実装し,それを2値画像に対して適用します.
等角写像による画像の変換〜Schwarz-Christoffel 変換〜part 2

等角写像による画像の変換〜Schwarz-Christoffel 変換〜part 2

前回の記事「等角写像による画像の変換〜Schwarz-Christoffel 変換〜part 1」の続きです. 実際に実装をして,写像を確かめてみます.
等角写像による画像の変換〜Schwarz-Christoffel 変換〜 part1

等角写像による画像の変換〜Schwarz-Christoffel 変換〜 part1

等角写像の一つであるSchwarz Christoffel 変換を用いて,画像の変換をしてみます. python によるコードも記載しております. 画像はhttps://uk.mathworks.com/help/images/examples/exploring-a-conformal-mapping_ja_JP.html より.
Extracting Straight Lines〜画像から境界線を効率よく求める方法〜

Extracting Straight Lines〜画像から境界線を効率よく求める方法〜

本記事では,IEEE Transactions on Pattern Analysis and Machine Intelligence に投稿された,「Extracting Straight Lines」の論文を説明し,実装を行います.1986年に投稿された少し古めの論文ですが,アイディアは非常に面白いです.
ディジタル画像処理~pythonによる空間フィルタリングpart1~ 

ディジタル画像処理~pythonによる空間フィルタリングpart1~ 

ディジタル画像処理を解説します.今回は,代表的な空間フィルタリングをpythonで実行してみました。
亀谷 桃子 | 13,491 view

この記事のキーワード

この記事のキュレーター

井上 大輝 井上 大輝