このページの本文へ移動
  1. ホーム >
  2. プレスリリース >
  3. 組合せ最適化手法の実問題適用を容易にする技術を開発

PRESS RELEASE (技術)

2017年9月20日
株式会社富士通研究所

組合せ最適化手法の実問題適用を容易にする技術を開発

量子コンピューティング技術を応用し、「デジタルアニーラ」を化学・金融分野に適用

株式会社富士通研究所(注1)(以下、富士通研究所)は、組合せ最適化問題を高速に解く計算機アーキテクチャー「デジタルアニーラ(注2)」において、複雑なパラメーター設定を行わずに組合せ最適化問題を解く技術を開発しました。

アニーリング法の計算では、解を収束させる速度と解の精度にトレードオフの関係があるため、事前に扱う問題の種類ごとに短い時間で十分な精度の解が得られるパラメーターを、場合によっては数週間といった時間をかけて探索する必要がありました。

今回、デジタルアニーラ内部で演算中の状態を観測した結果に基づいて、パラメーターを自動制御する回路を組み込むことにより、複雑なパラメーター設定の必要がなく十分な精度の解を出力することが可能となる技術を開発しました。これにより、新材料を探索する際の分子類似性比較問題(注3)やポートフォリオ最適化問題(注4)において、デジタルアニーラを適用する際の準備期間に2週間程度を要していたのが、1日未満にまで短縮できることを確認しました。本技術により、様々な実社会における組み合わせ最適化問題への迅速な対応が可能になります。

富士通研究所は、本技術を2018年前半に実用化し、化学、金融、エネルギーや流通などの様々な分野の組合せ最適化問題に適用することで、新規ビジネス創出に貢献していきます。

開発の背景

考えうる様々な組合せの中から最適な解を選択したいという要求は、実社会のあらゆる分野において存在します。このような要求は、組合せ最適化問題と呼ばれるものに分類されます。組合せ最適化問題は、考慮する要因の数が増えると組合せの数が爆発的に増えるため、従来のプロセッサでは高速に解く事ができませんでした。

そこで富士通研究所は組合せ最適化問題を高速に解くデジタルアニーラを開発しました。

課題

アニーリング法は、金属を高い温度に熱してから徐々に冷ますことにより材料の結晶構造を最適な状態に収束させることに例えられたもので、温度に相当するパラメーターを高い状態から徐々に下げていくことで、解の探索範囲を広い範囲から徐々に狭めていき、最もエネルギーの低い状態を探索します。この状態を高速に探索するためには、温度をゆっくり下げるように動作させれば最適な解の精度が得られる一方で計算時間が長くなり、逆に速く下げるように動作させれば計算時間が短くなる一方で解の精度が悪くなるといったトレードオフの関係があり、適用する問題の種類ごとに初期値や動作中の下げ方といったパラメーター設定の最適値が異なります。

分子類似性比較やポートフォリオ最適化などこれまで適用したことない問題に対してアニーリング法を用いる場合は、問題の種類ごとに最初に最適なパラメーター設定を見つけ出すことで、その後は、その種類の問題を高速に計算できるようになります。しかし、短い時間で十分な精度の解が得られる最適なパラメーター設定を得るには、パラメーター設定を変えたアニーリング計算を場合によっては数万回以上繰り返したり、数週間といった時間が必要でした。

開発した技術

今回、デジタルアニーラの適用分野拡大に向けて、事前の複雑なパラメーター設定を不要にすることにより、使いやすさを向上させる新技術を開発しました。

本技術では、デジタルアニーラにおいて最適化処理を行う複数の基本回路に簡易な初期パラメーターを与えて並列動作させます。さらに、基本回路の外に設けた状態制御回路により一定頻度ごとに演算中の状態を観測し、パラメーターを適宜変更することで、効率的な最適解の探索を実現します。

図1 従来のデジタルアニーラを新しい種類の問題へと適用する時のフロー
図1 従来のデジタルアニーラを新しい種類の問題へと適用する時のフロー

図2 状態制御回路を搭載した新規デジタルアニーラ
図2 状態制御回路を搭載した新規デジタルアニーラ

効果

本技術により、ユーザーは事前に複雑なパラメーター設定を行うことなく高い確率で最適解を得ることが可能となります。そのため、従来、人の手により時間をかけて行っていたチューニング作業が不要となり、初めて適用される種類の問題に対しても、準備期間が10分の1から100分の1に短縮できます。これにより、短期間でデジタルアニーラの性能を引き出し、実データを使った運用を開始することができます。

今回、1QB Information Technologies Inc. (注5)の量子コンピューティング技術を応用したソフトウェアを利用し、化学分野と金融分野における実用規模の問題に対して効果の検証を行いました。その結果、化学分野では50原子規模の分子類似性比較問題、金融分野では500銘柄を使ったポートフォリオ最適化問題に対して、従来は必要な精度の解を得るための準備期間に2週間程度を要していたのが、1日未満にまで短縮されることを確認しました。

図3 50原子規模の分子類似性比較問題への適用例
図3 50原子規模の分子類似性比較問題への適用例

図4 500銘柄のポートフォリオ最適化問題への適用例
図4 500銘柄のポートフォリオ最適化問題への適用例

今後

富士通研究所は、本技術を2018年前半に実用化し、化学、金融、エネルギーや流通などの様々な分野の組合せ最適化問題に適用してお客様の新規ビジネス創出に貢献していきます。

商標について

記載されている製品名などの固有名詞は、各社の商標または登録商標です。

以上

注釈

注1 株式会社富士通研究所:
本社 神奈川県川崎市、代表取締役社長 佐々木繁。
注2 デジタルアニーラ:
「量子コンピュータを実用性で超える新アーキテクチャーを開発」(2016年10月20日プレスリリース)
注3 分子類似性比較問題:
2つの分子において、分子や構造上の類似性を比較・判定する問題。
注4 ポートフォリオ最適化問題:
リスクを最小化する分散投資配分を決定する問題。
注5 1QB Information Technologies Inc.:
本社 カナダ バンクーバー市、最高経営責任者Andrew Fursman。富士通研究所と1Qbitは、2017年5月より、組合せ最適化や機械学習などのAI分野において協業を開始している。
「富士通と1QBit、量子コンピュータ技術を応用したAIクラウドで協業を開始」(2017年5月16日プレスリリース)

本件に関するお問い合わせ

株式会社富士通研究所
コンピュータシステム研究所
電話 044-754-2931(直通)
メール ngcs_qc_press_mem@ml.labs.fujitsu.com


プレスリリースに記載された製品の価格、仕様、サービス内容、お問い合わせ先などは、発表日現在のものです。その後予告なしに変更されることがあります。あらかじめご了承ください。