【東芝】量子インスパイアード組合せ最適化計算機「シミュレーテッド分岐マシン」の成功確率を“カオスの縁”により桁違いに向上させる新アルゴリズムを開発

２０２６－４－７
株式会社　東芝


量子インスパイアード組合せ最適化計算機「シミュレーテッド分岐マシン」の成功確率を
“カオスの縁”により桁違いに向上させる新アルゴリズムを開発
～約100倍の高速化を実現し、創薬や金融など幅広い社会課題の解決に貢献～
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
概要
　当社は、新薬の開発、配送ルート計画や投資ポートフォリオの作成など、さまざまな社会課題に現れる組合せ最適化問題を解く当社独自の量子インスパイアード組合せ最適化計算機「シミュレーテッド分岐マシン」（以下「SBM」）において、組合せ最適化技術の能力を評価する重要な指標の一つである、限られた試行回数で最適解または既知最良解を得る確率（以下、「成功確率」）を桁違いに向上させる新アルゴリズムを開発しました。これまでのアルゴリズムにおいても、十分な回数の試行によって最適解または既知最良解を導き出すことは可能でしたが、大規模問題になると、解の探索過程において局所最適解に陥る場合があり、少ない試行回数で高確率に解を得ることが課題となっていました。
　当社は、2019年4月に発表した「シミュレーテッド分岐アルゴリズム」（以下「SBアルゴリズム」）(*1)および、計算速度と計算精度を向上させ2021年2月に発表した第2世代SBアルゴリズム(*2)を基盤に、SBアルゴリズムの特徴である分岐現象(*3)を引き起こすためのパラメータ（分岐パラメータ）を従来の1個から、位置変数(*4)ごとに割り当てるように拡張しました。さらに各分岐パラメータを対応する位置変数の値に依存して個別に制御させることで、局所最適解から抜け出して大域最適解へ到達しやすいように高度化したのが、第3世代のSBアルゴリズムです。
　新アルゴリズムは、位置変数に依存した分岐パラメータの制御を行うことで、条件により解探索過程が規則的な振る舞いや不規則な振る舞い（カオス（*5））を示します。そして、規則的な振る舞いとカオスの境界である“カオスの縁”におけるカオスを有効利用することで、局所最適解から抜け出しやすくなり、大域最適解に到達する成功確率を100%近くまで飛躍的に向上させました。
　その結果、最適解または既知最良解を得るための時間（TTS: Time to solution）で比較した場合、第2世代SBMに対して約100倍の高速化を実現しました。これにより、さまざまな社会課題解決へつながることが期待されます。
　本技術の成果は、2026年4月6日付（米国東海岸時間）の米国物理学会の学術論文誌「Physical Review Applied」に掲載されました(*6)。

開発の背景
　物流の最短配送ルートの選定、金融市場における収益性の高い投資ポートフォリオの作成、創薬における新しい分子設計の組合せの特定など、社会や産業におけるさまざまな活動を効率的に行うためには、膨大な数の選択肢から最適解を見つけ出す必要があります。こうした問題の多くは、数学的には組合せ最適化問題と呼ばれるものに帰着します。組合せ最適化問題は、問題の規模によって解の候補数が指数関数的に増加する、いわゆる組合せ爆発のために解くことが大変難しい問題として知られており、組合せ最適化に特化した計算機の研究開発が国内外で活発に行われています。大規模な組合せ最適化問題を高速に解くことができる計算機を開発できれば、より効率的な社会や産業の実現に貢献できると期待されています。
　当社は2019年4月、「SBアルゴリズム」という並列計算に適した独自の量子インスパイアード組合せ最適化アルゴリズムを発表し(*1)、2021年2月には計算速度と計算精度を大きく向上させた第2世代SBアルゴリズムを開発・発表しました(*2)。SBアルゴリズムを搭載した計算機「SBM」は、本アルゴリズムが有する高い並列性を生かすことで大規模な組合せ最適化問題を高速に解くことができます。しかし、大規模問題になると、解の探索過程において局所最適解に陥る場合があり、限られた試行回数で高確率に最適解または既知最良解を得ることはこれまで非常に困難でした。

本技術の特徴
　そこで当社は、第2世代SBアルゴリズムをさらに一般化・高度化することにより、成功確率を100%近くまで飛躍的に向上させる第3世代SBアルゴリズムを新たに開発しました。
　当社は、まず、SBアルゴリズムの特徴である分岐現象を引き起こすための調整パラメータである分岐パラメータを、従来の1個から、位置変数ごとに割り当てるように拡張し、さらに、個々の分岐パラメータを対応する位置変数の非線形関数に依存して個別に制御する非線形制御を導入しました。その際、非線形制御の強さを調整する非線形強度パラメータを変えていくと、あるところで成功確率が100%近くまで飛躍的に向上することを発見しました（図1下）。
　さらに、その原理を追求するため、第3世代SBMにおけるダイナミクスを詳しく調べ、非線形強度パラメータが小さいときは規則的な振る舞いを示し、大きいときはカオスとなることを明らかにし、そのちょうど境界にあたる“カオスの縁”において、局所最適解に陥ることなく大域最適解に到達する成功確率の急向上が観測されることを発見しました（図1）。
　この発見は、初め2000スピン・全結合のイジング問題(*7)でなされましたが、複数の異なる変数の問題においても同様の現象が起こることを確認しました。さらに、SBアルゴリズムの特長である高い並列性は維持されており、FPGA(*8)を用いて超並列実装することで、第2世代SBMに比べて10～100倍の高速化を達成しました（図2）。


[画像1]https://digitalpr.jp/simg/1398/132368/350_451_2026040611501069d31f6219616.png


図1：今回開発した第3世代SBアルゴリズムが2000スピン・全結合のイジング問題においてカオスの縁で
既知最良解をほぼ100%の確率で見つけ出せることを示す結果




[画像2]https://digitalpr.jp/simg/1398/132368/500_387_2026040611501869d31f6a3d7bc.png


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

今後の展望
　当社は、今回開発した第3世代SBアルゴリズムによって、当社が提供する量子インスパイアード最適化ソリューションSQBM+TMを強化し、効率的で持続可能な社会の実現に貢献してまいります。


*1　東芝プレスリリース：https://www.global.toshiba/jp/technology/corporate/rdc/rd/topics/19/1904-01.html;
H. Goto, K. Tatsumura, A. R. Dixon, Sci. Adv. 5, eaav2372 (2019). https://advances.sciencemag.org/content/5/4/eaav2372
(American Association for the Advancement of Science)
*2　東芝プレスリリース：https://www.global.toshiba/jp/technology/corporate/rdc/rd/topics/21/2102-02.html;
H. H. Goto et al., Science Advances Vol. 7, no. 6, eabe7953 (2021). https://advances.sciencemag.org/content/7/6/eabe7953
(American Association for the Advancement of Science)
*3　非線形力学系において、系のパラメータ（分岐パラメータ）の変化によって安定点が１つから複数へ変化する現象。
*4　シミュレーテッド分岐アルゴリズムでは、多数の振動子の古典力学系の運動方程式を解くが、その各振動子の位置を表す変数のこと。この位置変数が組合せ最適化問題の決定変数（離散変数）に対応する。
*5　非線形力学系において、初期値が少し異なるだけでその後の運動の軌跡が大きく変わってしまう（無秩序になる）現象。このカオスの初期値敏感性をバタフライ効果と呼び、図1上はそれを定量的に評価したもの。
*6　H. Goto, R. Hidaka, K. Tatsumura, Phys. Rev. Applied 25,044011(2026). https://doi.org/10.1103/2qd9-x6v8
*7　イジング問題とは、磁性体の最も簡易的なモデルであるイジングモデル（±1を取るイジングスピンが2次のエネルギー関数で結合したモデル）のエネルギー最小のスピン配位を求める問題であり、代表的な組合せ最適化問題の1つ。
*8　Field-Programmable Gate Arrayの略称。演算処理集積回路の一種で，製造後にユーザーが用途に応じて機能を書き換えることが可能。


以　上