東芝は4月7日、「組合せ最適化問題」を解く新たなアルゴリズムである、“第3世代SBアルゴリズム”を開発発表。最適解を得るのにかかる時間は、従来比で約100倍と“ケタ違いの高速化”を実現しており、これによって同社が提供する量子インスパイアード最適化ソリューション「SQBM+」を強化。創薬や物流、金融といった幅広い社会課題(後述)の解決に寄与することが期待されるとしている。

同社独自の量子インスパイアード組合せ最適化計算機「シミュレーテッド分岐マシン」(SBM)に関する新たな技術成果で、詳細は米国物理学会の学術論文誌「Physical Review Applied」に米国東海岸時間2026年4月6日付で掲載されている。

東芝は、並列計算に適した独自の量子インスパイアード組合せ最適化アルゴリズムとして開発した「シミュレーテッド分岐アルゴリズム」(SBアルゴリズム、2019年4月発表)や、計算速度と計算精度を強化した第2世代SBアルゴリズム(2021年2月発表)をベースに、パラメータの数や制御方法を強化し、さらに高度化した第3世代SBアルゴリズムを開発。

従来のアルゴリズムでは大規模問題になると、解の探索過程において局所最適解に陥る場合があり、限られた試行回数で最適解または既知最良解を高確率に得ることはこれまで非常に困難だったという。

今回開発した新たなアルゴリズムでは、解の探索過程の振る舞いが規則的なものと不規則的なものの境界にある、“カオスの縁”と呼称する領域に注目。これを有効利用することで局所最適解から抜け出し、大域最適解に到る成功確率を100%近くまで「飛躍的に向上させた」とアピールしている。

最適解または既知最良解を得るための時間(TTS：Time to solution)で比較した場合、第2世代SBMに対して約100倍の高速化も実現した。この技術開発の過程では、用途に応じてユーザーが機能を書き換えられるFPGA(Field-Programmable Gate Array)の超並列実装も活用したとのこと。

  • 新開発の「第3世代SBアルゴリズム」が、2,000スピン・全結合のイジング問題において、“カオスの縁”で既知最良解をほぼ100%の確率で見つけ出せたことを示す結果

    新開発の「第3世代SBアルゴリズム」が、2,000スピン・全結合のイジング問題において、“カオスの縁”で既知最良解をほぼ100%の確率で見つけ出せたことを示す結果

  • 開発したアルゴリズムを搭載した第3世代SBMが、多くの問題で第2世代SBMの10～100倍高速であることを示す結果

    開発したアルゴリズムを搭載した第3世代SBMが、多くの問題で第2世代SBMの10～100倍高速であることを示す結果

物流の最短配送ルートの選定や、収益性の高い投資ポートフォリオの作成、創薬における新しい分子設計の組合せの特定に至るまで、社会や産業におけるさまざまな活動を効率的に行うためには、膨大な数の選択肢から最適解を見つけ出す必要がある。

こうした問題の多くは、数学的には「組合せ最適化問題」と呼ばれ、いわゆる“組合せ爆発”(問題の規模によって解の候補数が指数関数的に増加すること)が起きるため、解くことが非常に難しい問題として知られる。

組合せ最適化に特化した計算機の研究開発は国内外で進んでおり、大規模な組合せ最適化問題を高速に解ける計算機を開発できれば、効率的な社会や産業の実現に寄与することが期待される。