「組合せ最適化問題」をアニーリング方式で解決する「デジタルアニーラ」とは

「組合せ最適化問題」とは何か、デジタルアニーラでどうやって高速に解決できるのか、どのようにプログラミングを行うのか、他のアニーリングマシンとは何が違うのかを解説します。【富士通フォーラム 2018 セミナーレポート】

「ムーアの法則」の限界を超える?! 全く新しいコンピュータアーキテクチャ

従来のコンピュータ技術はムーアの法則によって進化してきましたが、既に限界が来ており、これを解決するために量子コンピュータや脳型コンピュータと呼ばれる次世代コンピューティング技術に期待が集まっています。しかし、これらの実用化にはまだ年月がかかると言われています。

その間を埋めるものとして、富士通研究所は量子現象に着想を得てデジタル回路を設計した「デジタルアニーラ」を開発しました。デジタルアニーラは、「組合せ最適化問題」に特化して解を高速に導く、全く新しいコンピュータアーキテクチャです。従来のコンピュータではかなり時間かかる問題が数秒で解けるため、従来ならば夜間バッチで演算していた問題や解くことを諦めていた問題をほぼリアルタイムに解くことが可能です。

「組合せ最適化問題」とは、複数の選択肢から組み合わせた結果を評価することで、その中から最適な組み合わせを決めるものです。あまりにも膨大な組み合わせがあると、従来のコンピュータを使用して総当たりで解くには膨大な時間がかかります。

組合せ最適化問題の典型例が「巡回セールスマン問題」と呼ばれるものです。これは「セールスマンが複数の都市を訪問する際、必要な総移動距離を最短にするためにはどのように回ればいいか」という問題です。5都市ならば120通りの組み合わせですが、32都市になると「263×10の33乗」という膨大な数になります。

分かりやすくするために1万円の商品券でおつりが出ない条件のもとで、2人分のディナーメニューを選ぶ例も提示しましょう。5つの要素が4通りの組み合わせある場合、一人ならば4×4×4×4×4で1024通りですが、カップルで行くと1024×1024通りになりますし、要素ごとに2つまで選べるハーフ＆ハーフならば組み合わせは膨大なものになります。

実社会においても金融の投資ポートフォリオ、創薬、物流など、様々な組合せ最適化問題があります。デジタルアニーラは、多種の組合せ最適化問題に特化した社会的要求に応えます。

デニタルアニーラの原理と、定式と評価式の作成によるソフトウェア開発

デジタルアニーラという名称は、金属の加工で「アニーリング（焼きなまし）」と言われる物理現象に由来します。焼きなましとは、金属を加熱してから徐々に落ち着かせることで安定した状態にすることです。「水を沸騰させてからゆっくり冷却することによって透明で綺麗な氷ができる」とイメージしやすいと思います。

組合せ最適化問題におけるアニーリングとは、パラメータを変化させ、最終的に最も安定した状態になったものを最適解とします。デジタルアニーラはある計算式を用意してパラメータを変更させることによって、最も安定した解を導きます。

従来の総当たりでは膨大な計算時間が必要となり、人がアタリをつけると大体の正解を導き出すことはできても、それが最適解かどうかはその人の経験に左右され、取りこぼしもあります。デジタルアニーラは全体を見てアタリをつけたものを優先するため、取りこぼしの可能性が非常に少なくなります。

デジタルアニーラのソフトウェア開発にはいくつかのステップがあります。まず、どんな課題を解決するのかを決めます。複雑な意思決定に際し組み合わせが膨大すぎて諦めていたものや、かなりの工数をかけていた問題を選ぶのが最適です。

次にその課題を現状どうしているかを突き止め、現状と比べてどの程度の改善を行えばビジネス上のメリットが得られるというゴール設定を行います。ここまでが準備段階です。

次に用意した課題が組合せ最適化問題で解けるかを検討します。基本的には選択肢を調べ、選択肢を組み合わせると解になるという問題に落とし込みます。そして制約条件をリストアップし、評価方法を決定します。これにより、評価方法を数式として定式化することができます。この数式を書くことがデジタルアニーラのコーディングになります。

例えば選べるディナー問題を定式化する場合、すべての選択肢を1ビットの変数で表します。さらに、制約条件を各変数の関係式で表現します。制約条件は評価式に入るのでこの二次式は小さい方がよい値ということになります。これらの制約条件を重みづけして足したものが評価式になります。コーディングはその数式を作ることです。その数式をデジタルアニーラに入力すると評価式が一番小さくなるような変数の組み合わせを発見します。

デジタルアニーラの内部では全変数をランダムに変化させます。それによって評価式が上下しますが、下がる方向ばかりに変更すると最適解が得られません。そこで初めのうちは評価が悪化する変化も確率的に許し、悪化させる確率を徐々に下げることで最適値を見つけ出します。これによって全変数を変化させつつ短時間で最適解を得ることが可能になるわけです。

実用レベルの難問が解けるデジタルアニーラ

デジタルアニーラを他のアニーリングマシンと比較した時の特徴と提供方法について、実用性の観点から比較してみます。まず、回路をどういう物理的原理で作っているかという「実装技術」ですが、デジタルアニーラは既存のデジタル回路なので通常の設備で動きます。一方D社のマシンは超電導回路を使った量子効果を利用しているので、絶対零度に近い温度まで冷却しなければいけません。またX社のマシンは光パラメトリック発振という原理を使って、長さ1kmの光ファイバーをループにして、そこに光を1000回ぐらい回すことで安定させて答えを見つけるため、大がかりな装置になってしまいます。

次はビット数と結合数についてです。ビット数は大まかにいうと扱える選択肢の数、結合数は選択肢と選択肢の関係を何通り用意できるかというものです。デジタルアニーラは1024ビットで全結合です。D社は2048ビットですが超伝導回路を使っているので最大で6個ずつしか結合できません。それ以上必要な場合は繋がる6個をダミーにしてそれぞれが先に5個繋げて30個にすることができます。一方ダミーを使うと評価に使えるビット数が減ってしまい、全結合にすると64ビット相当になってしまいます。

一方、デジタルアニーラは1024ビットで全結合です。このため、前述の巡回セールスマン問題は32都市の最適ルートの解が可能です。D社の64ビット全結合の場合、8都市が可能です。評価精度ですが、先ほどの評価式を何ビットで表せるかというもので、デジタルアニーラは16ビット、65536階調の式ができます。D社は5ビットで32階調になっています。つまり、巡回セールスマン問題で言うと都市と都市の間の距離を32種類で表す事しかできません。X社は3階調しかなく1か0か-1でしか評価できないので、現時点でX社の製品では巡回セールスマン問題に適用できません。
このため、実用レベルの難問に挑戦する場合、デジタルアニーラが最適な選択肢になります。

デジタルアニーラのサービスと、今後のマイルストーン

富士通は、デジタルアニーラを2018年5月15日に発表し、クラウドサービスとテクニカルサービスを開始しています。
クラウドサービスではカナダの量子ソフトウェアのトップベンダー1QBit社と提携し、評価式をデジタルアニーラで動かすためのミドルウェアを搭載して提供しています。評価式を投入するだけで解が得られます。テクニカルサービスは弊社の知見と1QBit社のノウハウに基づいて、定式化、実証検証、アプリケーション構築、保守サポートまでお客様の課題解決をすべてのフェーズでご支援するサービスになっています。

デジタルアニーラの研究開発のマイルストーンですが、第二世代として、2018年度中に規模が最大8192ビット、精度は最大64ビットを提供する予定です。適用する問題によって規模と精度のどちらを優先するか切り替えられるようになっています。さらに2019年度には大規模並列処理によって100万ビット規模を目指しています。