#！！！注意事項！！！
本記事は本人なりに頑張っていますが、決して正確なものではありません。
趣味のレベルを全く超えていません。QNNCloudの比較対象もSimulated Annealingをシンプルに実装しただけです。本当はもうちょっと知恵を使った古典的手法もあるでしょう。
#最適化とは
最適化はこの世に遍在します。
春の新緑があふれる日、複雑な木々の葉の形状は、生存競争を繰り広げながら最も適した形を取っています。
夏の晴れの日、上空の氷同士の衝突で蓄積された電荷は最も安定した状態を保つべく雷となって地上へ突き刺さります。
秋の雨が降る日、その雨粒は表面張力、重力、大気の抵抗すべてが最もバランスが取れた形状になって大地に降り注ぎます。
冬の雪が降る日、雪の結晶は水の分子が最も安定する形に結合します。
あ、すいませんタダのポエムなので、事実かどうかは知りません。
#私と最適化
それはそうと、私は大学の時に"正方形への詰め込み問題"をSAで解いた時に「究極にこそ美が存在する」と感じてからすっかり最適化のとりこです。かれこれ20年くらい。遠い昔ですね...。
思い出したついでに、詰め込み問題を探して小一時間ほどネットをさまよったところ、偶然 似た情報がまとめられた以下を見つけました。
こ、これは...
凄く興味深いですが気にしていると全く進まなくなるので、ぐっと我慢します。まぁ世には色々な人もいるというくらいに考えておいてください。
#QNNCloudとは
QNNCloudはコヒーレントイジングマシンで最適化を解いてくれるコンピュータ(?)です。
CodeZineの
日本発の量子コンピュータがついにクラウドで一般公開！ コヒーレントイジングマシン（CIM）とは何か
に非常に詳しいのでどういうものかはそちらをご参照ください。
操作レベルであれば、私が以前に書いた記事、
も参考になるかと思います。（今のバージョンではつまるところはなさそうですけど）
色々論争はあるようですが、正直私にとっては（理解できないので）仕組みはどうでもよく、「高速に最適化をしてくれたら、量子アニーリングだろうがCMOSアニーリングであろうが、コヒーレントイジングマシンであろうが構わない」という気分です。
中身はわかんないけどパソコンが動いて役に立つのとおんなじです。
#比較方法
順に比較方法を説明します。
##比較する内容
では、性能比較してみましょう。性能の見方は色々あると思いますが、
- 処理時間
- 処理結果（ここではカット数）
が代表的なところかと思います。ですが、QNNCloudは実行時間の情報がないため正確にはわかりませんが、Webの資料を確認するとμ秒オーダーのようですので、通常のマシンでは比較にならないくらい早いです。
不公平(QNNCloudに不利)ではありますが、処理結果だけ着目する形とします。
##QNNCloudと比較する最適化方式
個人的に好きなSimulated Annealingです。
分散処理するのであれば、GAもいいかなぁと思いましたが、今手元にHadoopクラスタとかないのでそれっぽい方法で比べてみます。
残念ながらちょうどいいコードがなかったので久々にプログラミングしました。Pythonはほぼ初めてに近いためイマイチだとは思いますが、ご容赦ください。完全に作業用コードレベルです。
せっかくのGitHubなので改良していただけるとハッピーです。 いや、ほんとに。
ご参考までに追証用に100node、1000node、2000nodeの情報もQNNCloudからダウンロードして格納していますので、ご自由にお使いください。
##マシン環境
参考までに、私のマシン環境は以下になります。
- CPU Core i7 4790K 4GHz
- メモリ 16GB
- OS Windows 10 Pro
- GPU GTX GeForce 1080
#比較結果
##100node比較
Simulated AnnealingはCPU 1コアでおおよそ7秒です。並列化実装の方法をしらないため1コアしか使えませんが、この程度の場合の数で時間的にも、結果も大丈夫そうですね。
| 処理時間 | Best | Worst | 備考 | |
|---|---|---|---|---|
| QNNCloud | 数十μ秒 | 339 | 254 | 処理時間は推測 |
| SimulatedAnnealing | 7秒 | 393 | 368 |
100nodeでQNNCloud、Simulated Annealingをそれぞれ100回試行した際のヒストグラムを下に載せます。X軸にCUT数（最大化すべき目的）をとり、Y軸に試行時のCUT数の頻度を取っています。
- グラフが右側に寄っているほうが良い答えが出ている
- グラフの幅が狭いほど、近い解を量産している（十分収束している）
と理解できるため、100nodeでは、Simulated Annealingのほうが良い結果を出しているといえるでしょう。
##1000node比較
1000nodeになると、処理時間が厳しくなったので、CUDA対応（cupy)対応しました。
変更は非常に簡単で、cupyの使い勝手の良さだけでもpythonを選ぶ理由になりますね。初Pythonですが、皆さんがPythonが好きな理由が少しわかった気がします。
時間を延ばせばよりいい解が得られますが、一分程度の時間で終わるようにパラメータを程よく設定しました。
###1000node 100回試行パラメータ
T_MAX = 400.0
T_MIN = 0.001
MAX_STEMPS = 100
T_LOOP = 100
PERSONS = 1000
GPU = True
T_MAX = 400.0
T_MIN = 0.001
MAX_STEMPS = 100
T_LOOP = 300
PERSONS = 1000
GPU = True
###1000node 100回試行結果のBest ＆ WORST
| 処理時間 | Best | Worst | 備考 | |
|---|---|---|---|---|
| QNNCloud | 数十μ秒 | 11876 | 10512 | 処理時間は推測 |
| SimulatedAnnealing(CPU) | 160.3秒 | - | - | 処理時間が長いため、未実施 |
| SimulatedAnnealing(GPU1) | 19.1秒 | 10752 | 9703 | |
| SimulatedAnnealing(GPU2) | 58.1秒 | 11273 | 10464 |
###1000node 100回試行結果のヒストグラム
これだけのnode数になると、目的関数の計算にも時間がかかる上に、組み合わせの数が非常に大きくなるので、Simulated Annealingでは同一温度での十分な繰り返し回数を実施することが困難になってきます。
先ほどとは逆の結果になり、
- QNNCloudのほうが解（CUT数）にばらつきが少ない。
- QNNCloudのほうが解が良い（CUT数が大きい）
非常に興味深いです。
###[ご参考]1000node 温度とCUT数（最適化）の遷移
ご参考までに温度が0.001に下がるまでのCUT数の遷移は以下となります。
まぁ、おおむね落ち着いている感じがしますね。（まだいけそうですけど）
##2000node比較(QNNCloudの設定上限)
さて、2000nodeがQNNCloudの設定上限なので、さらにnode数を増やして2000nodeのパターンも同じように試してみたいのですが、組み合わせの場合の数が多すぎます。一つ一つビットを変更している私の実装したへっぽこSimulatedAnnealingでは60秒では、そこそこ安定した状態に持っていけませんでした。
###2000node 100回試行結果のBest ＆ WORST
QNNCloudは比較的、結果の分散が小さいですね。値だけ見るとSAで約4分回したほうがいい結果が出ています。
★12/11 Updated
| 処理時間 | Best | Worst | 備考 | |
|---|---|---|---|---|
| QNNCloud | 数十μ秒 | 32507 | 31188 | 処理時間は推測 |
| SimulatedAnnealing(GPUその1) | 71.6秒 | 30531 | 28542 | |
| SimulatedAnnealing(GPUその2) | 101秒 | 31564 | 29513 | |
| SimulatedAnnealing(GPUその3) | 253秒 | 32542 | 30991 | |
| SimulatedAnnealing(GPUその4) | 1038秒 | 33604 | 31999 |
###2000node 100回試行結果のヒストグラム
★12/11 Updated
★12/11 Updated
Simulated Annealingの時間でQNNCloudとの解の質を比較しました。
※実行時間は変わりますので、おおよその目安として考えてください。
- 71.6秒程度動作させた場合 明らかにSimulated Annealingのほうが劣っています
- 101秒動作させた場合は、まだQNNCloudが良い結果を出しています。
- 253秒動作させた場合は、若干QNNCloudを上回ります。※SAの最良解(32542)もQNNCloudを上回ります。
- 1038秒動作させた場合は、QNNCloudを上回ります。
とても興味深い結果です
#まとめ ＆ 感想
QNNCloudと、Simulated Annealingの性能比較を行いました。
- 実行時間(QNNCloud側は推測になりますが)は、圧倒的にQNNCloudのほうが高速（μ秒オーダ vs 秒または分オーダ）
- 組み合わせの数が少ない場合（問題の複雑度が低い）は、従来手法でも大丈夫そう！
- 組み合わせの数が多い場合（問題の複雑度が高い）は、QNNCloudは圧倒的に高速だけど最適解に必ずしも近いとは言えない。
- 組み合わせの数が多い場合（問題の複雑度が高い）従来手法も時間をかければQNNCloudを上回る解が得られる
- 従来手法は問題の数に呼応して増えるが、QNNCloudが実行時間がほぼ一定。QNNCloud凄い！
- QNNCloud ＋ 詰めのGA、SAとかよさそうな予感
結論QNNCloud凄いけど、完璧じゃない。
組み合わせの数が増えると、十分な解が得られないのでは...？という疑問
→そのあたりの理由もあって、今回まだ2000qbitのリリースにとどめた？
→QNNCloud、解の精度を上げれればいいな
→たぶん時間を延ばせばいいって感じがしないし、原理的に難しいんだろうな
「量子コンピュータ Advent Calendar 2017」明日は、takus69さんです。
https://qiita.com/advent-calendar/2017/quantum
#お断り
世の中にはもっと性能の良い、高速な組み合わせ最適化手法があると思います。
というより、プログラムもろくにできないへっぽこインフラエンジニアがこんなことをやってもあまり貢献できないので、優秀なひと、助けて...