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

CNET Japan @cnet_japan

8億年分の計算を1秒で処理── 量子のパワーをデジタルに転換した 「デジタルアニーラ」の衝撃 japan.cnet.com/extra/fujitsu_…

Jun Makino @jun_makino

引用:ここで言う「8億年かかる計算」とは、コンピュータ科学の領域では有名な「巡回セールスマン問題」のことだ。これは、セールスマンがすべての都市を巡回して出発地点に戻るときの最短ルートを求める問題である。

Jun Makino @jun_makino

引用:例えば、巡回するのが3都市であれば、3の階乗（3×2×1）である「6通り」の組み合わせを比較計算すれば答えが求められる。だが、巡回する都市の数が増えると計算対象は指数関数的に増えていき、30都市なら実に1京×1京通り以上の計算が必要になる。

Jun Makino @jun_makino

引用:これは、1秒間に1京回の演算ができる富士通のスーパーコンピュータでも、8億年かかる計算量である。デジタルアニーラは、こうした1京×1京通り以上もの「組み合わせ最適化問題」を1秒以内に解いてしまうのである。

Jun Makino @jun_makino

引用:アニーリング自体は目新しい手法ではない。ただ、デジタルアニーラが革新的なのは、量子コンピュータではなく、これまでのコンピュータと同じく、デジタル回路を使ったコンピュータによってアニーリングによる超高速計算を可能にしている点だ。

Jun Makino @jun_makino

なんというか色々な革新的かつ衝撃的な文章ではある。ポスト真実時代の技術開発みたいな。

Jun Makino @jun_makino

普通にSAやっても30都市くらいなら1秒くらいで十分な答求まる気が。

ｈｒｋ先生 @Prof_hrk

@jun_makino まるでデジタルアニーラが厳密解を短時間で求められるような書きっぷりだ。Fがふかしたのか、記者が誤解して書いたのかどちらだろうか？

Jun Makino @jun_makino

@Prof_hrk こちらをご覧下さい fujitsu.com/jp/digitalanne…

ｈｒｋ先生 @Prof_hrk

@jun_makino 確かに厳密解をもとめるとは書いてないが、何の２x10の16乗倍はやいかが書いてなくて、言われていますと書いてあるところが味噌ですね。でも、誤解をわざわざ招く表現でプレスするのはルール違反だと思います。

Jun Makino @jun_makino

@Prof_hrk はい、そう思います。

ジャバ仙人 @plus7

わしゃ一応ImPACTがやらかしたときに社内SNSで「うちも誇大広告にはくれぐれも気をつけて」って釘刺しといたからな！もう知らん

ｈｒｋ先生 @Prof_hrk

@plus7 @jun_makino これ、思いっきり炎上案件なのだけれど、論文は出している？ImPACTの場合は論文を読めば本当のことが判るようになっていたけれど、これは論文無しの宣伝しっぱなしの感じがある。

Jun Makino @jun_makino

@Prof_hrk @plus7 学会発表はあるようです smapip.is.tohoku.ac.jp/~aqc2017/AQC20…

Jun Makino @jun_makino

@Prof_hrk @plus7 論文もありますね pdfs.semanticscholar.org/fd79/4c47edf63…

ｈｒｋ先生 @Prof_hrk

@jun_makino @plus7 1024の1ビット変数を全結合で重み計算をして更新し、局所解を避けるノイズは0-1の一様乱数みたい。2フェーズに分けて全ビットを同時更新するなどの最適化で高速化している。比較は1コアのSA。内容は妥当なので、プレス用の宣伝が酷いのだろう。FPGA使わないで2フェーズ更新したらどうなのだろうか？

ｈｒｋ先生 @Prof_hrk

@jun_makino @plus7 論文の日本語版はfujitsu.com/jp/documents/a… 基本アップデート速度が1コアより2倍、1024並列完全結合でのアップデートにより1000倍、他の最適化で6倍で合計12000倍1コアより速い。これはとても妥当な結論（しかも素晴らしい）だけれど、何が間違ってプレスでは10の16乗倍も速いと書いたのだろうか？

Jun Makino @jun_makino

@Prof_hrk ImPACT に合わせたんではないかと、、、

ｈｒｋ先生 @Prof_hrk

@jun_makino ImPACTは1コアより50倍高速で、しかもMAX-CUT問題。こちらは12000倍でTSPなのでより効果的かつ実用性があると読めます。評価が99％値をつかっていることは、この分野では普通なのかな？（素人ですみません）

Jun Makino @jun_makino

@Prof_hrk でもこれ、32都市に1024ビット使う方法ですね。普通に32都市の順列にアニーリングかける方法は1コアでは比較した実装の数十倍速いのではないかと、、、

ｈｒｋ先生 @Prof_hrk

@jun_makino それはその通り。

Jun Makino @jun_makino

@Prof_hrk 論文だと試行回数が3000万になってますが、通常の方法で32都市なら3000もあれば十分だと思うので、、、

ｈｒｋ先生 @Prof_hrk

@jun_makino そもそも99％という値設定がちょっと謎です。もう少し下げれば、1000位で結構収束するはずです。

Jun Makino @jun_makino

@Prof_hrk あ、いえ、これは1ビットの更新を1回と数えてるので、1000回では全体が1度更新されるだけです。なので、意味がある解に行くまでは100から1000万試行（並列試行で1000ー1万ステップ）はいると思います。