疑似量子効果などによって大規模問題の約10倍の高速化、最適解の獲得、
100万変数への規模拡大を実現し、創薬や金融など幅広い社会課題の解決に貢献

開発の背景
　社会や産業における様々な活動を効率的に行うためには、膨大な数の選択肢から最適なものを見つけ出す必要があります。例えば昨今のコロナ禍においては、治療薬に最適な候補物質の選定、医療従事者の最適な勤務シフト作成、患者の最適な搬送先選定などが挙げられます。こうした問題の多くは、数学的には組合せ最適化問題と呼ばれるものに帰着します。組合せ最適化問題は、問題の規模によって解の候補の数が指数関数的に増加する、いわゆる組合せ爆発のために解くことが大変難しい問題として知られており、組合せ最適化専用計算機の研究開発が国内外で活発に行われています。大規模な組合せ最適化問題を高速に解くことができる計算機を開発できれば、より効率的な社会や産業の実現に貢献できるものと期待されています。
　東芝は2019年4月、シミュレーテッド分岐アルゴリズムという独自の組合せ最適化アルゴリズムを発表しました(*1)。本アルゴリズムを搭載した「シミュレーテッド分岐マシン」は、本アルゴリズムが有する高い並列性を活かすことで大規模な組合せ最適化問題の良解を非常に高速に得ることができます。しかし、古典力学における断熱過程(*5)に基づく従来のアルゴリズム（「断熱的シミュレーテッド分岐アルゴリズム（aSB）(*6)」）は、大規模問題の最適解（厳密解）が得られない場合がありました。

本技術の特徴
　今回、東芝とTDSLは、従来の断熱的シミュレーテッド分岐アルゴリズムを発展させることにより、より高速に、より高精度に組合せ最適化を実行できる2つのアルゴリズムを新たに開発しました。
　1つ目は、短時間で良解を見つける高速アルゴリズム「弾道的シミュレーテッド分岐アルゴリズム（bSB）(*7)」です。従来のaSBで生じるエラーを低減する工夫により、シミュレーテッド分岐マシンの高速化と高精度化を実現しました。これをFPGA(*8)で高速実装することで、2,000変数問題の良解を従来のシミュレーテッド分岐マシン(*1)に比べて約10倍高速に得ることができます（図1）。
　2つ目は、他のマシンを凌ぐ計算速度でより高精度な解を見つける高精度アルゴリズム「離散的シミュレーテッド分岐アルゴリズム（dSB）(*9)」です。疑似量子トンネル効果によって古典力学の限界を打破してさらなる高精度化を実現し、同じ2,000変数問題の最適解（厳密解の推定値）を得ることができます。これをFPGAで高速実装した2,048変数対応シミュレーテッド分岐マシンは、最適解を得るのにかかる計算時間で量子アニーラやコヒーレントイジングマシンなど他のマシンを凌駕する高速性を達成しました（図2）。また、16台のGPU(*3)からなるGPUクラスタを用いることで100万変数という世界最大規模のマシンを実現し、約30分で最適解にほぼ到達できました（図3）。これは、最適化問題を解くための一般的な手法であるシミュレーテッドアニーリングを通常の計算機（CPU）上で実行した場合およそ1年2か月かかる計算を30分という現実的な時間に短縮したこと（約2万倍の高速化）を意味します。
　実社会の問題に適用する際は、即時に良解が必要な場合はbSB、時間をかけてでも極めて精度の高い解が必要な場合はdSB等といった用途に応じた使い分けが想定されます。