富士通の発表したデジタルアニーラと「組合わせ」のテクニカルタームについて（3/25更新）

ジャバ仙人 @plus7

またおかしな比較をしてる、コンプライアンス事案だろこれ twitter.com/pc_watch/statu…

PC Watch @pc_watch

スパコンで8億年かかる計算を1秒で解く富士通の「デジタルアニーラ」～量子現象に着想を得て開発した、これまでにないコンピュータ pc.watch.impress.co.jp/docs/news/1113… pic.twitter.com/ltzHGAyvh4

2018-03-23 17:50:05

ｈｒｋ先生 @Prof_hrk

@plus7 これは大局的に見ると某社が損をしている。量子といわれるアニーラ―ではMAX-CUT問題を扱っていたことに対し、アナログ要素を排することによりサイズは小さいがTSPが解けるシステムで、日本型量子コンピュータの意義を否定する力を持っているが、あのプレスでトンデモ研究の一種と認定された。

古田彩 Aya FURUTA @ayafuruta

「総当たりだとスパコンでも8億年かかる。デジタルアニーラだと最適に近いルートを1秒以内に見つけることができる」。多分そうなのだと思うが，スパコンも最適化問題を総当たりで解いているとは考えにくい。スパコンの最速アルゴリズムとの比較を知りたい。 pc.watch.impress.co.jp/docs/news/1113…

あ〜る菊池誠(反緊縮)公式 @kikumaco

@ayafuruta アニーリングでしょう？総当たりじゃ、ありませんよ。温度を下げていく計算手法

あ〜る菊池誠(反緊縮)公式 @kikumaco

@ayafuruta もともと熱揺らぎを使ってエネルギーバリアーを超えつつ温度を下げていくのがシミュレーテッドアニーリングという手法で、熱揺らぎの代わりに量子揺らぎを使ってみたというのが量子アニーリングなわけです

あ〜る菊池誠(反緊縮)公式 @kikumaco

@ayafuruta 最適化の技法は問題ごとのヒューリスティックスがあって、本当に問題ごとに違うわけです。それに対して、アニーリングは「遅いけれども、万能な技法」という位置付け。問題を決めてしまえば、アニーリングより速いヒューリスティックスはあります

古田彩 Aya FURUTA @ayafuruta

@kikumaco これＱＡとＳＡとの比較ではなく，総当たりとＱＡの古典シミュレーションの比較じゃないですか？

あ〜る菊池誠(反緊縮)公式 @kikumaco

@ayafuruta そうだと思います。そういう比較はあんまり意味ありませんね

あ〜る菊池誠(反緊縮)公式 @kikumaco

@ayafuruta QAであれSAであれ、真の最適解が求められるわけではないので、総当たりと比較するのは意味ありません

古田彩 Aya FURUTA @ayafuruta

@kikumaco はい，ヒューリスティックのよいものとの比較が知りたいという趣旨でした。

あ〜る菊池誠(反緊縮)公式 @kikumaco

@ayafuruta ヒューリスティックスは問題ごとに違うので、問題を決めてしまわないと難しいですね。それこそ、巡回セールスマン問題とか限定しないと

古田彩 Aya FURUTA @ayafuruta

@kikumaco この記事によると30 ノードの巡回セールスマン問題で比較したようですが，RTしたHideyuki Tanakaさんのツイートによると，ヒューリスティックでは大きな差は出なそうに見えます。厳密解まで得られるとは知りませんでした。 twitter.com/tanakh/status/…

Hideyuki Tanaka @tanakh

まず8億年というのは、ブルートフォースでの話だろうけど、枝狩りをすればはるかに速くなるだろうし、アニーリングで求めるのは実質的には近似解だから、秒数の比較に何の意味があるのだろうとか、スパコンでも疑似焼きなましすればわずか30ノード程度なら普通に1秒でそれなりに良い解出ると思う。

2018-03-23 23:33:29

あ〜る菊池誠(反緊縮)公式 @kikumaco

@ayafuruta 巡回セールスマンに限定するなら、SA使わないほうがいいですね。SAは「遅い代わりに万能」というのが特徴だと思います

古田彩 Aya FURUTA @ayafuruta

@kikumaco ご教示ありがとうございます

ｈｒｋ先生 @Prof_hrk

@ayafuruta Fujitsuに出ている論文では、比較対象を新し目のXeonの1コアSAとして、1ノードだけだと2倍、1024並列で約1000倍、解法の工夫で6倍Speedupで、12000倍性能向上と示されています。逐次とFPGA内並列を比較するのはちょっと不公平ですが、PCより12000倍速いが主張です。（続く）

ｈｒｋ先生 @Prof_hrk

@ayafuruta ただし、SAは最速アルゴリズムではないし、並列と逐次をくらべちゃだめでしょう。私は詳しくないですが、既知の最速アルゴリズムと比べると似たようなもの、または少し遅いくらいじゃないのでしょうか。（さらに続く）

ｈｒｋ先生 @Prof_hrk

@ayafuruta 私の理解するところでは、この論文ではアニーリングマシンでTSPをちゃんと解いて高速化した点が注目で、NIIのアニーリングマシンの限界をこえているところです。実用性はまだ謎ですが、少なくとも量子アニーリングを終わらせる糸口は見せています。

古田彩 Aya FURUTA @ayafuruta

@Prof_hrk ご教示ありがとうございます。すみません，ちょっと意味が取れなかったのですが，「NIIのアニーリングマシン」というのはImPACTのCIMのことでしょうか？　それともD-Waveのような量子アニーリングマシンを作っているのですか。

ｈｒｋ先生 @Prof_hrk

@ayafuruta 書き方が悪くてすみません。ImPACTのマシンです。

古田彩 Aya FURUTA @ayafuruta

@Prof_hrk ありがとうございます。自分の理解に自信がないもので，聞くまでもないことをお聞きしてすみません。

ｈｒｋ先生 @Prof_hrk

@ayafuruta これまでの様々な意見では ・TSPが解けたのは重要。ただし現状ではサイズが小さすぎ。 ・速度は最良のアルゴリズムにはかなり負けるが、そこそこの速さは実現。 ・問題サイズスケーラビリティが今後の問題。完全結合への依存脱却と、複数FPGA拡張が課題 ・現状では将来の実用化は見えない

古田彩 Aya FURUTA @ayafuruta

@Prof_hrk 変な数字を出したので，かえって意義が見えなくなってしまったのですね。「完全結合への異存脱却」というのは，スケールしていくと完全結合は保てなくなる，ということでしょうか？

ｈｒｋ先生 @Prof_hrk

@ayafuruta そうです。別に結合エッジの変数分線を出す必要はないですが、数クロックでUpdateするには、たかだか信号線の数（≦1000くらい）の100倍くらいしかいかないので、N≦450位が限界でしょう。で、TSPのF社の方法ではノード数の平方根が都市数の上限です。