富士通、トランジスタで組み合わせ最適化問題を1万倍速く解く技術を開発

　株式会社富士通研究所は、トロント大学と共同で、汎用性を持ちながらも問題を高速に解ける、“量子コンピュータを実用性で超える”新しいコンピュータアーキテクチャを開発したと発表した。

　同アーキテクチャは、「組合せ最適化問題」と呼ばれる問題を高速に解くことを目指し開発されたもの。

　組合せ最適化問題とは、災害復旧の手順の決定、投資ポートフォリオ最適化、経済政策の決定など、限られた人や時間などの制約の下で行なわれる意思決定のような、「さまざまな要因の組合せを考慮して評価を行ない、最適なものを選択する」という問題。組合せ最適化問題は、考慮する要因の数が増えることで組合せの数が爆発的に増加するため、実社会の問題を実用的な時間内に解くためには、コンピュータの大幅な性能向上が必要となる。

　従来のプロセッサは、ソフトウェア処理のため、扱える組合せ最適化問題の自由度が高い反面、問題を高速に解くことができない。一方、量子コンピュータは、組合せ最適化問題を高速に解くことが可能だが、物理現象を利用しているため、近接した素子同士でしか接続できないという制限があり、現時点では多様な問題を扱う汎用性を持つことができない。

従来コンピュータの限界

組合せ最適化問題解法の課題

　同社とトロント大学は、従来の半導体技術を用いて、組合せ最適化問題を高速に解ける新しいアーキテクチャを開発。現行の量子コンピュータより多様な問題が扱え、並列化により扱える問題の規模や処理速度を向上できるとする。

　開発されたアーキテクチャは、デジタル回路を用いた基本最適化回路を複数個用いて、階層構造での並列動作を行なうよう設計されている点。この際、基本最適化回路間のデータの移動を極小化する構造とすることで、高密度な並列実装を実現した。また、基本最適化回路の内外で自由な信号のやりとりができる、全結合の構造を採用しているため、多様な問題を扱うことができるという。

　さらに、基本最適化回路において、確率論の手法を用いて、ある状態からより最適な状態への探索を繰り返し行なう際、複数ある次の状態の候補に対する、それぞれの評価結果の値を一括して並列計算することにより、次の状態を見つけ出す確率を向上させる技術と、探索の途中で局所的な解に辿り着いて、膠着状態になった場合を検知し、脱出確率を高めるための評価値に一定値を繰り返し加えることで、次の状態に移行しやすくする技術を開発。これにより、高速に最適な解を求めることができるという。

開発アーキテクチャ

基本最適化回路の高速化技術

　1,024bitで表される組合せを扱うことができる基本最適化回路をFPGAに実装して評価を行なったところ、従来プロセッサで動作する、「シミュレーテッドアニーリング」と呼ばれるソフトウェア処理に比べ、約1万倍の速度で動作することを確認したという。

　富士通研究所では、よりbit規模を拡大することで、数千拠点ある物流の最適化、限られた予算で複数のプロジェクト利益の最適化、投資ポートフォリオ最適化など、計算量の多い組合せ最適化問題を高速に解くことが可能となり、最適かつ迅速な意思決定を支援する、新たなICTサービスの実現に繋がるとしている。今回開発したアーキテクチャの改良を進め、2018年度までに実社会の問題が適用できる規模である、10万bitから100万bitの計算システムを試作し、実用化に向けて実証を進めていく予定。