計算機で約1年2カ月かかる計算を約30分に、東芝が量子コンピュータの強みとされる「組合せ最適化問題」で成果

このエントリーをはてなブックマークに追加

株式会社東芝および、東芝デジタルソリューションズ株式会社(TDSL)は2月4日、量子コンピュータの強みとされる「組合せ最適化問題」を解く東芝独自の「シミュレーテッド分岐マシン」の速度・精度・規模を大幅に向上させられるとうたう2つの新アルゴリズムを開発したと発表。本技術の成果は、現地時間2月3日付けの米国オンライン科学雑誌「Science Advances」に掲載された。

新アルゴリズムにより、2019年発表当時世界最速を記録した従来アルゴリズムに比べ、約10倍の高速化を達成し、より大規模な問題の最適解獲得に成功したという。また、16台のGPUから成る世界最大規模とうたう100万変数のマシンを実現し、通常の計算機で約1年2カ月かかる大規模な計算を約30分で実施できるとのこと。

2021年中にサービス提供を目指す

社会や産業におけるさまざまな活動を効率的に実施するためには、膨大な数の選択肢から、最適なものを見つけ出す必要がある場面も少なくない。たとえば、昨今のコロナ禍においては、治療薬に最適な候補物質の選定、医療従事者の最適な勤務シフト作成、患者の最適な搬送先選定などが挙げられる。

このような問題の多くは、数学的には「組合せ最適化問題」と呼ばれる問題が大きく関係していると言える。「組合せ最適化問題」は、問題の規模によって答えの候補の数が指数関数的に増加する、いわゆる組合せ爆発のために解くことが難しい問題として知られており、国内外で組合せ最適化専用計算機の研究開発が活発にされている。

東芝は2019年4月に、「シミュレーテッド分岐アルゴリズム」という独自の組合せ最適化アルゴリズムを発表した。本アルゴリズムを搭載した「シミュレーテッド分岐マシン」は、本アルゴリズムが有する高い並列性を生かすことで、大規模な「組合せ最適化問題」の最適な答えを非常に高速に得られたという。しかし、古典力学における断熱過程に基づく従来のアルゴリズム(「断熱的シミュレーテッド分岐アルゴリズム(aSB))は、大規模問題の最適解(厳密解)が得られない場合があったとのこと。

今回、東芝とTDSLは、従来の断熱的「シミュレーテッド分岐アルゴリズム」を疑似量子トンネル効果などで発展させることで、より高速に、より高精度に組合せ最適化を実行できる2つのアルゴリズムを新たに開発した。新アルゴリズムは、短時間で良解(高精度な近似解)を見つける高速アルゴリズムと、より高精度な解を見つける高精度アルゴリズムの2種類に分けられる。

東芝とTDSLは2021年中に、今回開発した新たなシミュレーテッド分岐アルゴリズムを活用し、FPGAを用いたオンプレミス版およびGPUを用いたクラウド版のシミュレーテッド分岐マシンをサービス提供するとしている。

>>ニュースリリース

量子コンピュータと古典コンピュータとの違いは?

Ledge.ai編集部では、「組合せ最適化問題」に強みを持つとされる量子コンピュータについて、古典コンピュータとの違い、実用化の最前線、AIとの関係などを解説している。気になる人は以下の記事をチェックしてほしい。