東芝が組み合わせ最適化問題の新アルゴリズムを開発、世界最速をうたう：量子コンピュータの10倍高速

東芝は、FPGAやGPUなどを用いた従来型コンピュータだけで、量子コンピュータよりも10倍速く「組み合わせ最適化問題」の解を得られるアルゴリズムを開発した。従来型コンピュータを使って、低コストで大規模な問題にも対応できる。

[＠IT]

　東芝は2019年4月20日、同社が世界最高速度と主張する組み合わせ最適化技術「シミュレーテッド分岐アルゴリズム」を開発したと発表した。既存の同等技術よりも約10倍速く、適用可能な用途が世界最大規模だという。

　そのため、従来の技術では困難だった複雑で大規模な組み合わせ最適化問題でも、既存のコンピュータを使って短時間で高精度な近似解（良解）を導出できる。現在の最適化プロセスを一変させる可能性があるとしている。

　組み合わせ最適化問題とは、膨大な組み合わせの中から、最適な解を探し出す処理をいう。例えば、物流の効率的な配送ルート探索や、新薬開発時の最も有効な分子構造の決定、収益性の高い金融商品の組み合わせなどさまざまな分野に関わる問題だ。よく知られている「巡回セールスマン問題」も、組み合わせ最適化問題の一例。

　膨大な計算が必要な組み合わせ最適化問題を処理するためには、従来のアルゴリズムでは並列化しにくく高速化が困難だ。このため、大規模で複雑な組み合わせ最適化問題を既存のコンピュータで解くことは難しいとされていた。このような背景により、量子コンピュータなど次世代コンピュータを使った組み合わせ最適化問題専用機の研究開発が続いている。

3つの現象を利用して解を見つける

　東芝が開発したシミュレーテッド分岐アルゴリズムは、並列化を可能にした組み合わせ最適化アルゴリズム。同社独自の量子コンピュータの理論から発見に至ったという。具体的には、古典力学の「分岐現象」「断熱過程」「エルゴード過程」という3つの現象を利用して、高精度な解を高速に見つけるとしている。

シミュレーテッド分岐アルゴリズムが利用する3つの現象（出典：東芝）

　同アルゴリズムでは、既存のコンピュータをそのまま利用して並列処理できるため、新たな設備導入が不要だ。大規模化も低コストでできる。

　東芝では、FPGA（Field Programmable Gate Array）を利用した場合、2000変数の全結合（約200万結合）問題の解を0.5ミリ秒で得られるとしている。同社によると、これは同問題の計算で世界最速だったレーザーを用いた量子コンピュータ（コヒーレントイジングマシン）よりも約10倍速いという。

シミュレーテッド分岐アルゴリズムを用いた場合の処理時間（出典：東芝）

　変数を10万に増やし、全結合（約50億結合）した大規模問題でも、GPUを8台つないだGPUクラスタを使えば数秒で解けるとしている。