東芝および東芝デジタルソリューションズ(以下、TDSL)は、新薬の開発、配送ルート計画や投資ポートフォリオの作成など、様々な社会課題に現れる組合せ最適化問題を解く東芝独自の「シミュレーテッド分岐マシン」の速度・精度・規模を大幅に向上させることができる2つの新アルゴリズムを開発したと発表した。
この新アルゴリズムは、東芝が2019年4月に発表した「シミュレーテッド分岐アルゴリズム」を疑似量子トンネル効果などにより発展させたもので、短時間で良解(高精度な近似解)を見つける高速アルゴリズムと、より高精度な解を見つける高精度アルゴリズムの2種類であるという。
新アルゴリズムにより、発表当時世界最速を記録した従来アルゴリズムに比べて約10倍の高速化を達成するともに、より大規模な問題の最適解獲得に成功。
また、16台のGPUから成る世界最大規模の100万変数のマシンを実現し、通常の計算機で約1年2か月かかる大規模な計算を約30分で行うことに成功したとのことだ。
同技術は、例えばコロナ禍において必要となる治療薬の開発や医療従事者の最適な勤務シフトの作成など、今まさに求められている社会課題への応用が期待されるという。
なお、同技術の成果は、2021年2月3日付(米国東海岸時間)の米国オンライン科学雑誌「Science Advances」に掲載されたとのことだ。
同技術の特徴は以下。
1つ目は、短時間で良解を見つける高速アルゴリズム「弾道的シミュレーテッド分岐アルゴリズム」。
従来のaSBで生じるエラーを低減する工夫により、シミュレーテッド分岐マシンの高速化と高精度化を実現したという。
これをFPGAで高速実装することで、2,000変数問題の良解を従来のシミュレーテッド分岐マシンに比べて約10倍高速に得ることができるという。
2つ目は、他のマシンを凌ぐ計算速度でより高精度な解を見つける高精度アルゴリズム「離散的シミュレーテッド分岐アルゴリズム(dSB)」。
疑似量子トンネル効果によって古典力学の限界を打破してさらなる高精度化を実現し、同じ2,000変数問題の最適解(厳密解の推定値)を得ることができる。
これをFPGAで高速実装した2,048変数対応シミュレーテッド分岐マシンは、最適解を得るのにかかる計算時間で量子アニーラやコヒーレントイジングマシンなど他のマシンを凌駕する高速性を達成したとのことだ。
また、16台のGPUからなるGPUクラスタを用いることで100万変数という世界最大規模のマシンを実現し、約30分で最適解にほぼ到達したとのことだ。
これは、最適化問題を解くための一般的な手法であるシミュレーテッドアニーリングを通常の計算機(CPU)上で実行した場合およそ1年2か月かかる計算を30分という現実的な時間に短縮したこと(約2万倍の高速化)を意味するという。
実社会の問題に適用する際は、即時に良解が必要な場合はbSB、時間をかけてでも極めて精度の高い解が必要な場合はdSB等といった用途に応じた使い分けが想定されるとのことだ。
今後の展望として、東芝とTDSLは、今回開発した新たなシミュレーテッド分岐アルゴリズムを活用して、FPGAを用いたオンプレミス版およびGPUを用いたクラウド版のシミュレーテッド分岐マシンを2021年中にサービス提供し、効率的で持続可能な社会の実現に貢献していくとしている。