東北大学 電気通信研究所,科学技術振興機構（ＪＳＴ）

令和４年４月１日

東北大学 電気通信研究所
科学技術振興機構（ＪＳＴ）

大規模な組み合わせ最適化問題を解く確率的計算技術を開発

～解収束時間を３桁以上低減し実時間で社会還元できる道を開く～

ポイント

組み合わせ最適化問題は、膨大なデータの組み合わせから最適解を求める問題として知られています。組み合わせ最適化問題を高速に処理可能な技術として注目されているのがＤ－Ｗａｖｅ Ｓｙｓｔｅｍｓ社などの量子アニーリングマシンですが、いくつもの難点があり、大規模な組み合わせ最適化問題を解くことは困難です。東北大学 電気通信研究所の鬼沢 直哉 准教授、羽生 貴弘 教授、カナダ・マギル大学のＷａｒｒｅｎ Ｊ．Ｇｒｏｓｓ 教授らの共同研究チームは、確率的演算に基づく新たなシミュレーテッドアニーリング技術を開発し、量子アニーリングで知られるＤ－Ｗａｖｅ Ｓｙｓｔｅｍｓ社のマシンと比較して、約１６倍の大規模な組み合わせ最適化問題を解くことに成功しました。

今回開発した確率的計算技術は、一般的なパソコン（古典コンピューター）で利用可能なアルゴリズムでありながら最適解への収束率を飛躍的に高めることに成功し、極低温動作を必須とする量子アニーリングマシンを実用性で大幅に上回る性能を実証しました。また、決定論的計算に基づく従来手法と比較して、約１，０００倍高速に組み合わせ最適化問題を解くことにも成功しました。多くの点で既存のアニーリング技術を大幅に超える性能を示しており、今後の情報処理技術に新たな展開をもたらし得るものと期待されます。

本研究成果は２０２２年３月３０日付で米国の科学誌「ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ ａｎｄ Ｌｅａｒｎｉｎｇ Ｓｙｓｔｅｍｓ」でオンライン公開されました。

本研究の一部は、科学技術振興機構・戦略的創造研究推進事業・さきがけ ＪＰＭＪＰＲ１８Ｍ５、科学技術振興機構・戦略的創造研究推進事業・ＣＲＥＳＴ ＪＰＭＪＣＲ１９Ｋ３、日本学術振興会・科学研究費助成事業・基盤研究（Ｂ） ＪＰ２１Ｈ０３４０４などの支援を受けて行われたものです。

＜プレスリリース資料＞

＜論文タイトル＞

“Fast-Converging Simulated Annealing for Ising Models Based on Integral Stochastic Computing,”IEEE Transactions on Neural Networks and Learning Systems
ＤＯＩ：10.1109/TNNLS.2022.3159713

＜お問い合わせ先＞

（英文）“Fast-Converging Simulated Annealing for Ising Models Based on Integral Stochastic Computing”

前に戻る