@yuichirominato 2018.09.06更新

Wildqatで500×500の全結合のイジング計算

QUBO wildqat イジング 量子アニーリング

はじめに

実用問題を解くためには、大きな問題を解く必要があります。D-Waveマシンなどは2000量子ビットのキメラグラフと呼ばれるものを0.00002秒程度で解いてしまいます。ここでは、心もとない手元マシンですが、同様の計算をmacbookで行ってみたいとおもいます。

スペックは、
MacBook (Retina, 12-inch, Early 2015)
プロセッサ 1.2 GHz Intel Core M
メモリ 8 GB 1600 MHz DDR3

になります。

Wildqatの導入

導入や使用の仕方は下記参照でお願いします。

「Wildqatでquboとイジングを解いてみる」
http://blog.mdrft.com/post/32

一番簡単な導入方法は、pip3が入っている状態で、


$ pip3 install wildqat

となります。

ベンチマーク

とりあえず300量子ビットの全結合を計算してみます。SA、温度はT=5から。温度の減衰は0.95で。
パラメータはかなり控えめです。


import wildqat as wq
import numpy as np
a = wq.anneal()

早速行列を300*300で作ります。


a.J = [np.random.random_sample(300) for i in range(300)]

できているか確認してみます。


print(a.J)

スクロールするのも大変な300*300の9万要素の行列ができていました。


[array([0.27223951, 0.11582413, 0.8537373 , 0.68451826, 0.83795206,
       0.41718616, 0.79091685, 0.02558825, 0.44930124, 0.97000804,
       0.19686452, 0.70276479, 0.27445115, 0.18279091, 0.081066  ,
       0.80448799, 0.14987819, 0.93594616, 0.47769104, 0.95963766,
       0.97006227, 0.91507235, 0.5298118 , 0.66356586, 0.50405138,
       0.95707183, 0.81802269, 0.08397173, 0.38341766, 0.59588018,
       0.20115511, 0.59720664, 0.66316095, 0.40555114, 0.65898468,
       0.81594693, 0.11726589, 0.54864427, 0.26497304, 0.13064719,
       0.58744562, 0.89680077, 0.99242796, 0.77146605, 0.15285207,
       0.23666875, 0.3928213 , 0.01492846, 0.40741656, 0.14909061,
       0.74083653, 0.55860046, 0.33997566, 0.92497433, 0.70431911,
       0.84920262, 0.96377128, 0.22823769, 0.34200423, 0.69621567,
       0.71974205, 0.81509924, 0.49833644, 0.89762663, 0.76490437,
       0.72055351, 0.46624861, 0.76030717, 0.38207675, 0.04945336,
       0.06356331, 0.28848716, 0.94662852, 0.55882756, 0.5337017 ,
       0.08548897, 0.97129591, 0.148791  , 0.14479273, 0.70983915,
       0.88017392, 0.80010034, 0.83739542, 0.81235722, 0.34032376,
       0.04385888, 0.22443709, 0.61098247, 0.91261401, 0.07607121,
       0.87543557, 0.29731911, 0.6621431 , 0.87237642, 0.52211587,
       0.90963574, 0.28746307, 0.66710821, 0.72038866, 0.22335384,
       0.57990906, 0.23559566, 0.72950258, 0.200573  , 0.71778289,
       0.07989944, 0.2967553 , 0.83857607, 0.49336365, 0.23609261,
       0.60163295, 0.14002365, 0.7441875 , 0.92293475, 0.1596855 ,
       0.83248351, 0.38128228, 0.17102044, 0.96279642, 0.14553235,
       0.90732728, 0.90197863, 0.66772611, 0.10967984, 0.39234108,
       0.6007659 , 0.21242349, 0.55423414, 0.52205368, 0.54386667,
       0.52934749, 0.49825587, 0.51018824, 0.92985092, 0.59052989,
       0.54882431, 0.35436333, 0.79902848, 0.34305336, 0.94298752,
       0.60311179, 0.43712994, 0.35209435, 0.28125907, 0.95464615,
       0.16468912, 0.4567547 , 0.67574569, 0.2101239 , 0.42229506,
       0.06354134, 0.24015799, 0.18198313, 0.22229068, 0.66704737,
       0.09674139, 0.0211167 , 0.0202683 , 0.59546886, 0.70552746,
       0.96660295, 0.47978826, 0.4471346 , 0.52815665, 0.53387387,
       0.68635571, 0.36960888, 0.55676289, 0.04278489, 0.81566838,
       0.47930262, 0.12167555, 0.54155569, 0.56924464, 0.9455223 ,
       0.32967493, 0.54122097, 0.3305931 , 0.22231216, 0.51529003,
       0.27519017, 0.5166544 , 0.77437926, 0.06553852, 0.01113543,
       0.44350981, 0.93939509, 0.12224167, 0.9569553 , 0.96106131,
       0.53767166, 0.46051219, 0.55368461, 0.9756516 , 0.49757121,
       0.14131002, 0.42991537, 0.50070947, 0.58936348, 0.10580222,
       0.88380013, 0.76948255, 0.71114714, 0.81333117, 0.96905152,
       0.36004692, 0.77440924, 0.29389254, 0.9970924 , 0.16973517,
       0.6366081 , 0.90523468, 0.36888486, 0.42793944, 0.80446498,
       0.23157317, 0.22222268, 0.32446795, 0.05508816, 0.02494156,
       0.43801224, 0.43533876, 0.24736645, 0.90174337, 0.245837

以下略

早速計算しちゃいます。


a.sa()

6.3046228885650635秒で計算完了です。


array([ 1, -1,  1, -1, -1, -1, -1, -1, -1,  1, -1, -1,  1, -1,  1,  1, -1,
        1,  1,  1, -1,  1, -1, -1,  1, -1, -1,  1, -1, -1,  1, -1,  1, -1,
        1, -1,  1, -1,  1,  1, -1, -1, -1, -1,  1,  1, -1, -1, -1, -1,  1,
        1, -1,  1, -1, -1,  1,  1,  1,  1,  1,  1, -1,  1, -1, -1, -1, -1,
       -1,  1,  1,  1,  1,  1, -1,  1, -1,  1,  1,  1, -1,  1,  1, -1, -1,
       -1, -1,  1, -1, -1,  1, -1,  1, -1,  1, -1, -1, -1, -1,  1,  1,  1,
       -1, -1,  1, -1, -1,  1, -1, -1,  1,  1,  1, -1,  1, -1, -1, -1,  1,
        1,  1,  1,  1, -1, -1,  1, -1,  1,  1, -1, -1,  1, -1,  1, -1,  1,
       -1, -1,  1, -1,  1,  1, -1, -1, -1, -1,  1,  1, -1, -1, -1, -1,  1,
        1,  1, -1, -1,  1,  1, -1, -1, -1,  1,  1, -1,  1,  1, -1,  1,  1,
       -1,  1,  1, -1, -1,  1, -1,  1,  1,  1,  1,  1, -1, -1, -1,  1, -1,
       -1,  1,  1,  1, -1, -1, -1,  1, -1, -1,  1,  1, -1,  1,  1,  1, -1,
        1,  1,  1, -1, -1, -1, -1,  1, -1,  1,  1,  1,  1, -1,  1,  1, -1,
        1,  1, -1,  1, -1, -1, -1, -1,  1, -1, -1, -1,  1, -1, -1, -1,  1,
       -1,  1,  1,  1, -1, -1, -1,  1, -1,  1, -1,  1,  1,  1,  1, -1, -1,
        1, -1, -1, -1, -1,  1, -1, -1, -1,  1,  1, -1, -1,  1,  1,  1,  1,
       -1, -1,  1,  1,  1,  1,  1,  1, -1, -1,  1,  1,  1,  1,  1,  1,  1,
        1, -1,  1,  1,  1, -1, -1, -1,  1, -1, -1])

続いて500量子ビット、8.609660863876343秒でした。

1000は?

1000量子ビットでやってみます。
15.606795072555542秒程度かかりました。

正直パラメータをあげないとどこらへんが最適解かわかりませんので、他のマシンと比較しないとあまり意味がありませんが、精度を落とせばとりあえずそれっぽい答えはでます。とりあえずエネルギーを求めてみます。-7000前後となりました。多少待ちますが、暫定的なシミュレーションとしては十分じゃないでしょうか。量子コンピュータなどの前の練習には使えそうです。


In [15]: wq.Ei(a.sa(),a.J)
Out[15]: -6774.721819294456

In [16]: wq.Ei(a.sa(),a.J)
15.385426998138428
Out[16]: -6916.5732985478535

In [17]: wq.Ei(a.sa(),a.J)
15.625043153762817
Out[17]: -6672.1911293053

In [18]: wq.Ei(a.sa(),a.J)
16.239644050598145
Out[18]: -6766.683994592476

あわせて読みたい