東芝、組み合わせ最適化問題の近似解を得る新アルゴリズムを開発。並列処理で大幅な高速化が可能 31
ストーリー by hylom
詳細は論文をどうぞ 部門より
詳細は論文をどうぞ 部門より
東芝が、組み合わせ最適化問題の近似解を高速に得る新しいアルゴリズムを開発したと発表した（Science Advances掲載論文、毎日新聞、NHK）。
今回考案されたアルゴリズムは「シミュレーテッド分岐アルゴリズム」と名付けられており、並列処理によって容易に高速化できるのが特徴。FPGAを使って演算を行った場合、2000変数・全結合（約200万結合）の問題の良解を0.5ミリ秒で得られるとしており、これはレーザーを用いた量子計算機よりも約10倍高速だという。
ディジタルアニーラよりも１０倍以上速い？ (スコア:1)
論文を斜め読みすると富士通のやってるディジタルアニーラ( https://www.fujitsu.com/jp/digitalannealer/ [fujitsu.com] )よりも１０倍以上速いと言っているように見える。論文中ではディジタルアニーラは SA と表記、参考文献29番。頑張れ富士通。
Re:ディジタルアニーラよりも１０倍以上速い？ (スコア:1)
デジタルアニーラは「おおむね一秒以下」と言ってたから、0.5ミリ秒よりも全然遅い。赤射の半分(オイ
一方東芝のは最適解とは言っておらず、良解と言ってるので局所最適解になっていて、収束しきっていない可能性もありそう。
Re: (スコア:0)
デジタルアニーラも最適解ではないはず。
Re: (スコア:0)
流行に乗って量子アニーリングの研究をぶち上げたものの、いつまでもハードウェアは出来そうもなく、シミュレーションテクニックの発表でお茶を濁してる感じ
Re:ディジタルアニーラよりも１０倍以上速い？ (スコア:1)
量子アニーリングハードウェアに比べて枯れたFPGAで同等以上の性能が出る
アルゴリズムが見つかったなら実用的にはより有用なのでは？
Re: (スコア:0)
量子アニーリングの時点で、
従来の方法で厳密解を探す時間＞＞＞＞＞＞量子アニーリングで近似解を探す時間
という話だったわけで。
従来の方法とも比べないと実用性はわからん。
これでフカシギおねえさんも (スコア:1)
ロボにならずに済むかも･･･
Re: (スコア:0)
おねえさんは厳密解を求めてたので、多分、近似解法なこの手のとは話が違う。
# そもそも、お姉さんは高速に厳密解を求められたとしても、その後に列挙しようとして死ぬほど時間がかかりそうだけど
シミュレーテッド分岐? 投機実行みたいなのか (スコア:0)
仮定保留のままその先進めて最後に生き残りパスを求めるのだろうか
最尤推定のような。
でも、年内の実用化?
何でそんなに時間が掛かるんだろう
Re: (スコア:0)
素人の想像だけど、現時点では問題に合わせたハードコーディングで想定した理屈通りに高速処理できることが確認できただけ、実用品として公開するには汎用的に扱えるライブラリのような形に整備して、特に問題や結果の受け渡しをするAPIの仕様を検討中とかかな？
Re: (スコア:0)
どんな問題を渡されても、「42」という答えを返すだけの簡単なお仕事
Re: (スコア:0)
今日でも年内やで
＃東芝がその気になれば商業化は2020年3月31日からということも可能だということ
Re: Re:シミュレーテッド分岐? 投機実行みたいなのか (スコア:0)
Re: (スコア:0)
ついに東芝は非決定性機械を実現してしまったのか
言うて東芝の企業秘密でしょ? (スコア:0)
アメリカや中国のライバルは10倍スパコンを用意するなりクラスターの規模を10倍に増やすなりすればいいだけだからな。金の力には勝てんわ
Re: (スコア:0)
ロシアの鉛筆か
Re: (スコア:0)
中国 「日本企業に秘密なんて存在しないんやで」
Re: (スコア:0)
SAベースのアーキテクチャではどれだけ大規模なクラスターを組んでもイジングモデルによる組み合わせ最適化問題を実用的な時間内に汎用的に解くのは無理。
東芝が実現した（と言っている）ようなハミルトニアンの評価を並列化してネットワークによる遅延を隠蔽する仕組みを導入しないと。
Re: (スコア:0)
主要な部分はFPGA一個で実装したみたいよ。一個150万円位するインテルの石だけれど。
Re: (スコア:0)
どちらかと言うとこれは並列アルゴリズムの発見だから10倍のクラスタを作れば10倍？速くなることが革新性なんじゃ無い？
日本に対して並列ではなく10倍速いマシンを用意するのは中国/アメリカといえど容易ではない。
日本の研究レベルの凋落を表す嘘プレスリリース (スコア:0)
レーザーを用いた量子計算機よりも約10倍高速だという。
これはコヒーレントイジングマシンを指していて、コヒーレントイジングマシンは量子計算機（コンピュータ、アニーラ）ではありません [mainichi.jp]。話題の量子コンピュータより速い方法を開発したと誤解させる嘘プレスリリースを大企業東芝が流すあたり、日本の技術レベルの凋落をはっきり表しています。
Re: (スコア:0)
コヒーレントイジングマシンが量子コンピュータかどうかはともかく、東芝のリリース内容に嘘が無ければ真正の量子コンピュータであるD-Waveより高速だよ。
速度の比較のために現存するイジングマシンとしてコヒーレントイジングマシンやデジタルアニーラを持ち出すのは別に間違っちゃいない。
Re: (スコア:0)
D-Wave=量子アニーリングマシンを真正の量子コンピュータと言っていいのかどうか。
Re: (スコア:0)
なんで？
ちゃんと量子アニーリングの基礎理論に沿って実装されてるでしょ。
量子ゲート方式以外は量子コンピュータと認めないっていうスタンス？
Re: (スコア:0)
速度の比較のために現存するイジングマシンとしてコヒーレントイジングマシンやデジタルアニーラを持ち出すのは別に間違っちゃいない。
コヒーレントイジングマシンはGPUに20倍速度の差で負けている [arxiv.org]ので間違いです。
Thus the question naturally arises: Can the optical portion of the coherent Ising machine be replaced with classical mean-field arithmetic? Here we answer this in the affirmative by showing that a straightforward noisy version of mean-field annealing closely matches
Re: (スコア:0)
その論文、問題サイズN=2000の時のNMFAアルゴリズムでの処理時間は載せてないね。
ちゃんと数字載せてるのはN=200までなんだけど、なんで？
なんかズルくない？
アルゴリズム自体も式を見る限りあんまり並列性良くなさそうなんだけど、これで本当に「N=2000全結合でもCIMより20倍速い」って言えるの？
Re: (スコア:0)
量子効果使ってりゃ量子コンピュータでしょ
わざわざ書き分けのためにレーザーとまで書いてくれてんのに何が不満かね
Re:日本の研究レベルの凋落を表す嘘プレスリリース (スコア:1)
量子効果使ってないコンピュータなんてあるんか？
the.ACount
Re: (スコア:0)
友「お前今何やってんの？」
俺「量子演算」
Re: (スコア:0)
どこにぶら下げるか迷ったけど、どうせ誰も読まないから末端にこそっとコメント。
半導体でスイッチング素子(トランジスタ)が作れるのは、半導体の中では電子のエネルギーがバンド構造を持つためです。このエネルギーバンドは量子力学を使わないと説明できないので、明らかにトランジスタは量子効果を用いたスイッチング素子です。なので我々が普段使っているコンピュータは全て量子効果を使っています。でもお分かりの通り普通の計算機で計算しても、それはいわゆる「量子演算」ではありません。
以上、量子通信装置による書き込みでした。
量子照明(LED照明)消してもう寝ます。
Re: (スコア:0)
> 量子効果使ってりゃ量子コンピュータでしょ
間違ってますよ