富士通の発表したデジタルアニーラと「組合わせ」のテクニカルタームについて（3/25更新）
-
kamakiri_ys
- 15027
- 11
- 1
- 41
-
- いいね！41
笑い猫
@bokudentw
@jun_makino math.uwaterloo.ca/tsp/concorde/b… 厳密法アルゴリズムによるベンチマークはここで数百都市から１０００都市以上まで解かれています。解は当然厳密解です。この手の話題が出るたびに何度でもいわないといけませんが、やさしい問題＝インスタンスはベンチマークとして使えません。３２都市では小さすぎ
2018-03-24 22:26:56
Umepon
@shunji_umetani
math.uwaterloo.ca/tsp/index.html に巡回セールスマン問題に関する情報が良くまとまっています．1954年には49都市，2004年には24978都市，これまでに85900都市の問題例が解かれた記録があります．
2018-03-24 22:58:54
Jun Makino
@jun_makino
Fのはそもそもまともな定義なら量子コンピュータじゃないしFも量子コンピュータではないといってるわけで、古典を超えるはずはない。専用回路か汎用かというだけ。で、計算量のオーダーが変わる（ふえる）専用回路は大体将来がない。
2018-03-25 12:25:24
ｈｒｋ先生
@Prof_hrk
@jun_makino 最初から量子と言ってないので、Ising Machineでどこまで最適化できるかの勝負で、それはFも認識していると思います。とりあえず桁が凄く違わないところまで行ったが、スケーラビリティが無いことが課題というところでは？将来性については、まあ、、、
2018-03-25 12:43:32
™
@tmaehara
ヒューリスティクス研究は「その比較フェアじゃないよね」との長い戦いの歴史（現在も戦火の真っ只中）なので、専門家は何と比較すればフェアかを熟知しているはず。
2018-03-25 17:41:58
Hideyuki Tanaka
@tanakh
>組み合わせ最適化問題の代表例が(略)「巡回セールスマン問題」だ。（略）30都市だと1京×1京通りと、総当たりだとスパコンでも8億年かかる。これがデジタルアニーラ、アニーリングアプローチだと最適に近いルートを1秒以内に見つけることができる。 同じ問題解いてないのにこの比較はなあ(´･_･`)
2018-03-23 23:33:28
Hideyuki Tanaka
@tanakh
まず8億年というのは、ブルートフォースでの話だろうけど、枝狩りをすればはるかに速くなるだろうし、アニーリングで求めるのは実質的には近似解だから、秒数の比較に何の意味があるのだろうとか、スパコンでも疑似焼きなましすればわずか30ノード程度なら普通に1秒でそれなりに良い解出ると思う。
2018-03-23 23:33:29
Hideyuki Tanaka
@tanakh
そもそも30ノード程度ならば、DPで厳密解をそれなりに求められるはずなんで、普通のマシンで1分もせずに厳密解が求まるぐらいだと思うんですよね。なんていうか、比較対象を（意図的に？）ずらして、実際の成果をわかりにくくするのは、なんていうか、評価するのも難しくなるだけだと思うんだけど…。
2018-03-23 23:33:29
Hideyuki Tanaka
@tanakh
pc.watch.impress.co.jp/img/pcw/docs/1… あといつの間にか焼きなましはAIに分類していいことになってるみたいだ(´･_･`)
2018-03-23 23:36:14
Mori
@Ryuhei_Mori
富士通の古典イジングマシンの発表の適当さが話題になっているけど、 japan.cnet.com/extra/fujitsu_… これに近い説明は西森・大関本「量子コンピュータが人口知能を加速する」にもある。 30都市巡回セールスマンの初出は2014年のNHKの番組 nhk-ondemand.jp/goods/G2014055… だろうか？ 英語で検索してもヒットしない
2018-03-24 17:36:22
Mori
@Ryuhei_Mori
「量子コンピュータは古典コンピュータの〜倍速い」という言明の初出は Google の arxiv.org/abs/1512.02206 なんだろうけど、これは比較対象がシミュレーテッドアニーリング(SA)及び、量子モンテカルロ(QMC)、ただし古典コンピュータはシングルコア。
2018-03-24 17:36:22
Mori
@Ryuhei_Mori
富士通の発表の問題は2つあって、 1. 巡回セールスマンの計算量を O(n!) とするのはやりすぎ(DPでO(2^n n^2)時間で厳密に解けることなんて蟻本にも書いてあるし高校生でも知ってる)。 en.wikipedia.org/wiki/Held%E2%8… 2. 厳密解法と近似解法で計算時間を比較している。 だと思う。
2018-03-24 17:36:23
Mori
@Ryuhei_Mori
前者は strong exponential time hypothesis (SETH) でも仮定すれば、他の問題で起き換えれば済むことなんだけど、 en.wikipedia.org/wiki/Exponenti… 後者はまるっきりどうしようもない。 諸悪の根源は量子アニーリング(QA)についてこんな説明をし始めた(容認した)日本の物理学者なんじゃないかと思うけど、
2018-03-24 17:36:23
Mori
@Ryuhei_Mori
古典イジングマシンはともかく、QAについて、敢えて同情するところがあるとすれば「量子コンピュータってどうして速いの？」って説明に端的に答えるのが難しいってところ。結局(IBMなどもそう説明しているように)「重ね合わせ状態を使って並列に計算してるから速いんだよ」という説明になってしまう。
2018-03-24 17:36:23
Mori
@Ryuhei_Mori
ただ説明をそこで終わらせてしまうと「量子コンピュータ = 超巨大な並列計算機」という認識になり、全ての NP の問題が多項式時間で解けるような誤解を生む。実際には解候補の構造、性質を用いない純粋な全探索の計算時間は平方根にしか改善されない。問題にとてもよい性質がある場合だけ指数の改善。
2018-03-24 17:36:24
シータ
@Perfect_Insider
理論的な議論をするなら「問題サイズを大きくした際のスケーリング」を議論しない限り意味がない。実用ベースで考えるなら、最適化問題は相当にアルゴリズムの改良が行われて対象なので、現時点で最良のアルゴリズムと同一の問題で勝負して勝てることを言わないと役に立たない。
2018-03-24 22:58:51