【ＩＴ】「世界最速・最大規模」──東芝、量子コンピュータより高速に組み合わせ最適化問題を計算するアルゴリズムを開発［04/22］

しじみ ★

東芝は4月20日、量子コンピュータが得意とする計算の一つである「組み合わせ最適化問題」を、従来のコンピュータ（古典コンピュータ）で高速に解けるアルゴリズムを開発したと発表した。ある問題設定では、現行の量子コンピュータ（※1）に比べて10倍高速に解を求められるという。同アルゴリズムを活用したサービスプラットフォームの、19年中の事業化を目指す。
https://image.itmedia.co.jp/news/articles/1904/22/ki_1609376_toshiba01.jpg

　東芝は、自社が持つ量子計算の理論から、古典力学の「分岐現象」「断熱過程」「エルゴード過程」という3つの現象に着目。これらをうまく利用し、古典コンピュータ上で組み合わせ最適化問題を解くアルゴリズムを「シミュレーテッド分岐アルゴリズム」（Simulated Bifurcation, SB）と名付けた。

　SBは従来の手法に比べて並列計算に向くとしており、GPUを8台つないだクラスタで10万変数・全結合の大規模問題を計算すると、数秒で良解（※2）を導けるという。

　また、FPGA（あるアルゴリズムの計算に特化した集積回路）を用い、2000変数・全結合の問題をSBで解いたところ、良解を0.5ミリ秒で得られたという。同問題を世界最速（2016年時点）で解けるとされていた「コヒーレント・イジングマシン」は良解の導出に5ミリ秒かかることから、「10倍高速に問題を解ける」としている。

　コヒーレント・イジングマシンより高速で、大規模な問題へも適用できることから、同社はSBを用いた組み合わせ最適化問題の計算について「世界最速・最大規模」をうたう。

　組み合わせ最適化問題の高速計算は、効率的な配送ルートの探索（巡回セールスマン問題）や新薬開発の分子構造決定、金融ポートフォリオの組み合わせ決定に有用とされる。

　同社は、「本技術をキー技術として、現代社会におけるあらゆる最適化ニーズに応えるサービスプラットフォームを実現し、19年中の事業化を目指す」としている。

　SBの詳細は、米オンライン論文誌「Science Advances」に4月19日付で掲載された。

SA=シミュレーテッド・アニーリング、CIM＝コヒーレント・イジングマシン、SB＝シミュレーテッド分岐アルゴリズム。SAやCIMより、SBの計算時間の方が短い

https://image.itmedia.co.jp/news/articles/1904/22/ki_1609376_toshiba02_w390.jpg

※1：コヒーレント・イジングマシンの研究を主導する国立情報学研究所の山本喜久教授は量子の性質を用いて計算しているとしているが、他の研究者からは量子性の利用について疑問も呈されている。

※2：最適解とは限らないが、最適解に近い解。

■組み合わせ最適化問題と量子コンピュータ

　組み合わせ最適化問題は、カナダの量子コンピュータベンチャーD-Waveが開発したマシンに実装されている「量子アニーリング」や、量子アニーリングの計算過程を古典コンピュータ上で模した「シミュレーテッド・アニーリング」などが計算に適しているとされる。

　量子アニーリングとは、加熱して徐々に冷却すると物体内部の抵抗力を除去できる「焼きなまし」という自然現象を利用した計算方法。

　金属原子のように量子ビットを格子状に配列し、互いに結合させ、ビット同士の相互作用を定めた「イジング模型」を用い、最も安定する状態（基底状態）を探す。基底状態でのビットの状態が、問題の最適解に対応する。

　量子アニーリングの場合、理論的には量子トンネル効果により基底状態を得られるが、量子ビット同士の結合が物理的な制限を受けるため、大規模化に課題がある。

　一方シミュレーテッド・アニーリングは量子アニーリングのようなハードウェアの制限はない代わり、量子ビットを利用しないため、必ず基底状態を得られるとは限らない。東芝によれば、さらに「並列化による高速化が原理的に困難」だという。

ITmedia NEWS
https://www.itmedia.co.jp/news/articles/1904/22/news097.html