(2019031: 少し書き換え)
この記事だけを読むと、また劣化 SA で NP-hard な問題の近似解を求める話かとうんざりした気分になるが、ちょっと気になったので調べてみる。東芝のプレスリリースにはもう少し情報がある。
世界最速・最大規模の組合せ最適化を可能にする画期的なアルゴリズムの開発について
通常のコンピュータで実装可能な最適化手法であることが分かる。論文はたぶんこれ。
元となった量子アニーリング手法はこれ。
ただ、手法としては論文 (0) の式 (7), (8) だけ睨んでも問題ない。すごくざっくり言うとイジング変数を実数にして、井戸型から二重井戸型へとゆっくり変化するポテンシャルの中を古典運動方程式に従って時間発展させる。感覚的には MCMC に対する HMC にちょっと近い (違うけれど)。これで収束が速くなるなら素晴らしいし、速くなっても不思議はないように思える。
論文では SA より 10 - 100 倍程度速くなると主張している (同じマシン構成ではなく CPU, GPU, FPGA のうち各手法で最速のものを選択したらしい…) が、収束のオーダーは SA と同等 (2k nodes, Fig. 2) か、悪化している (100k nodes, Fig. 3-B) ように読める。問題の次元が高いほど SA に比べ収束のオーダーが悪化していくと考えられる。
一方、定数倍で勝っている理由は simultaneous update ができて並列化しやすいからだと書いてある。これがよく分からない。 SA でも収束性能を落として並列化するのは可能だし、提案手法も SA も変数の依存関係は変わっていないはず。どの程度フェアな比較なのかよく分からない。
実際に Fig. 3-A を見ると、同じ PC クラスタ上で提案手法と SA のアップデートにかかる時間は同等であることが分かる。 Fig. 3-B は SA on CPU vs 提案手法 on GPU での比較であり、両者を照らし合わせると M_{100k} 問題の SA on CPU vs 提案手法 on CPU では SA の方が 10 倍速いという結論になる。
ということで、プレスリリースから受ける印象とは違って手法自体は試みとして全うなものにみえるけれど、収束のオーダーは SA から悪化している上、同一 CPU 上での実装では絶対性能でも SA に負けると考えられる。となると GPU や FPGA フレンドリーさが主な利点となるが、その点についても質的な違いがあるかは怪しい…という印象。