MIT Tech Review: 東北大ら擬似アニーリング技術、最適化問題で本物超え

フラッシュ2022年4月5日

東北大ら擬似アニーリング技術、最適化問題で本物超え
by MITテクノロジーレビュー編集部 [MIT Technology Review Japan]

東北大学とカナダ・マギル大学の研究グループは、組み合わせ最適化問題に特化した擬似アニーリング（シミュレーテッド・アニーリング）技術を開発。古典コンピューター上で、量子アニーリングマシンのおよそ16倍の大規模な組み合わせ最適化問題を解くことを実証した。

従来の擬似アニーリング技術では、ノードの内部状態を示すtanh関数（Hyperbolic tangent function：双曲線正接関数）を決定論的計算で正確に計算していたが、組み合わせ最適化問題が大規模化すると最適値への収束が困難だった。今回の技術では、確率的計算の一種であるストカスティック演算を使用。具体的には、ノードの内部状態を0と1からなる確率的ビット列と制限付きアップダウンカウンターを作ることで、tanh関数に近似する結果を得た。

開発した技術を使って古典コンピューターでシミュレーション実験を実施し、Dウェーブ（D-Wave Systems）製の量子アニーリングマシンと性能を比較したところ、グラフ同型性判定問題において、量子アニーシングマシンではノード数が増加するにつれて最適値への収束率が大幅に低下し、ノード数が50以上では最適解を得られなかった。一方、今回開発した技術ではノード数が増加しても最適値への収束率は高く、量子アニーリングマシンに比べておよそ16倍の大規模な問題を解くことに成功したという。

研究成果は3月30日、「IEEEトランザクションズ・オン・ニューラル・ネットワークス＆ラーニング・システムズ（IEEE Transactions on Neural Networks and Learning Systems）」誌にオンライン掲載された。

（笹田）
人気の記事ランキング