量子コンピューター研究から生まれた 組合せ最適化の新解法

2019/08/07 Toshiba Clip編集部

この記事の要点は...

  • 様々な社会課題の解決に立ちはだかる「組合せ最適化問題」
  • その良解を高速に導く、画期的な新解法が開発された
  • 量子コンピューターのあるべき姿とは?
量子コンピューター研究から生まれた 組合せ最適化の新解法

物流網構築や渋滞緩和、新薬開発など、様々なジャンルにおよぶ社会問題を解決するには、膨大な組合せパターンの中から目的に合ったものを見つけ出す「組合せ最適化問題」と呼ばれる難問を解く必要がある。そこで期待されているのが量子コンピューターの活用だ。このほど東芝は、量子コンピューターの研究を通して、従来のコンピューター(古典コンピューター)で高速に組合せ最適化問題を解く新たな解法(アルゴリズム)を発見した。

 

量子コンピューターを使わずとも各分野の社会課題を解決できるとなれば、世の中に与える影響は計り知れない。著名な米国オンライン科学雑誌「Science Advances」に論文が掲載され、国内外から注目を集める新解法「シミュレーテッド分岐アルゴリズム」の全容、そして今後の展望をひもといていこう。

「組合せ最適化問題」とは何か

物事を効率化するためには、数多くの選択肢から、最良の組合せを選択する必要がある。これが「組合せ最適化問題」だ。例えば昨今、慢性的な人手不足が問題視される物流業界では、できるだけ短い走行距離で配送できる輸送経路が求められるし、渋滞緩和のためには各自動車がスムーズに走行できるルートを採る必要がある。

物流最適化

しかし、問題の規模が大きくなるほど、組合せの総数も爆発的に大きくなり、最大限の効果が得られる解をはじき出すことは困難になる。この「組合せ爆発」のために、組合せ最適化問題は難問として知られる。

 

例えば、セールスマンが複数の都市の全てを1回ずつ訪問して出発点に戻る際に、移動距離が最小になる経路を求める「巡回セースルマン問題」と言われるものがある。10都市を回るルートでも181,440通りあり、30都市、50都市にもなると途方もない数字になり、通常の計算機では追いつかないレベルになる。その中から最適なルートを導き出すにはとてつもない時間がかかり、現実的には不可能に近いとされている。

 

「問題が大規模になるほど、しらみつぶしに最良の組合せを見つけることは難しくなります。物流網構築や渋滞緩和はもちろん、効能が最も高くなる分子の組合せを求める新薬開発や、低リスクで高い収益性のある株の組合せを求める金融ポートフォリオ作成などはその典型例です。こうした膨大な組合せを持つ課題が、社会やビジネスにおいて無数に存在しています

 

そう語るのは、株式会社東芝 研究開発センターの後藤隼人氏だ。

株式会社東芝 研究開発センター フロンティアリサーチラボラトリー 主任研究員 後藤隼人氏

株式会社東芝 研究開発センター フロンティアリサーチラボラトリー 主任研究員 後藤隼人氏

こうした組合せ最適化問題は以前から存在するが、その解法が課題とされていた。最適解を求めるための計算は、「イジング問題(注1)」という標準問題に置き換えて行うことが研究者の中では通例だ。現在、様々な方式が研究され、イジング問題専用の計算機の開発が進んでいる。ただ、従来の古典コンピューターを使った方式は、膨大な変数を持つ大規模計算に対応できるものの、並列計算による高速化が原理的に困難であるとされる一方で、量子コンピューターは並列計算が可能ながら、大規模計算が不得手という問題があった。

 

注1:「イジングモデル」と呼ばれる磁石の最も単純なモデルにおいて、そのエネルギー最小の状態を求める、一種の組合せ最適化問題。

そのため、解法を得ることができれば社会的にも産業的にも絶大なメリットが得られるのは間違いないが、現状では計算処理が極めて困難とされるのが組合せ最適化問題なのだ。

マシンスペック比較表

「これまで、超電導回路やレーザーを用いた専用計算機(量子コンピューター)による研究が進められてきましたが、量子コンピューターの本格的な実用化はまだ先で、おまけに多くのコストが必要です。そこで様々な手法が研究される中、並列計算によって高速処理を行なう現行の計算機を駆使して高速な組合せ最適化を可能とするのが、今回開発した『シミュレーテッド分岐アルゴリズム』です」(後藤氏)

 

東芝社内で長年にわたり量子コンピューターの研究に取り組んできた後藤氏によれば、このアルゴリズムは量子力学のロジックにインスパイアされて生まれたものであるという。

量子力学にインスパイアされて誕生した新アルゴリズム

「研究を始めたきっかけは、2017年当時、世界最速の計算速度を誇ったコヒーレントイジングマシン(注2)に勝てる見込みに気づいたことでした。2015年に量子力学的な分岐現象(注3)によって生じる重ね合わせの状態を利用して最適解を探索する、独自の量子コンピューター「量子分岐マシン」と、古典力学(注4)における分岐現象に基づく「古典分岐マシン」を同時に発見しましたが、その古典分岐マシンを数値シミュレーションすることで大規模問題を解いてみたところ、その性能は非常に高く、FPGA(注5)で実装すればコヒーレントイジングマシンに勝てると思いました。発見から2年を経て、古典の価値に気がついたのです」(後藤氏)

 

注2:半導体ではなくレーザーを用いて計算処理を行なう、組合せ最適化問題専用マシン。
注3:非線形力学系において、安定状態の数が1個から複数へ分かれる現象。
注4:量子力学以前の力学。
注5:Field-Programmable Gate Arrayの略称。演算処理集積回路の一種で,製造後にユーザーが用途に応じて機能を書き換えることが可能。

新たに開発したアルゴリズムは、古典力学における断熱過程やエルゴード過程といった現象をうまく利用してイジング問題を解く、これまでにない全く新しいものである。

 

「シミュレーテッドアニーリング」と呼ばれる従来技術における計算処理は、変数を一つひとつ更新していく方式(逐次計算)のため、並列計算による高速化が原理的に困難であり、解を出すのに時間を要する。これに対し、新アルゴリズムは微分方程式を解く方式であり、変数を同時に更新することが出来る。このため、既存の並列計算機で高速化が図れるのだ。新アルゴリズムは、並列化という現在の計算機の技術トレンドとうまくマッチしている。

 

後藤氏は、同じく研究開発センターに籍を置く辰村光介氏と連携し、コヒーレントイジングマシンを超える速さを持つ古典コンピューターの開発に着手する。具体的には、新アルゴリズムを徹底的にブラッシュアップし、さらにその新アルゴリズムのための超並列処理回路を設計し、FPGAに実装するという取り組みだ。

 

「その結果、FPGA1台のみを使った古典コンピューターが、世界最速とされるコヒーレントイジングマシンと比較しておよそ10倍の計算速度を記録したのです。生産性や効率が求められるシステム上の問題というのは、数学的に突き詰めていくと組合せ最適化問題に行き着くことが多いのですが、この結果はそうした諸問題の良解を非常に短時間で導き出すことができる可能性を示したと言えます」(辰村氏)

株式会社東芝 研究開発センター コンピュータ&ネットワークシステムラボラトリー 主任研究員 辰村光介氏

株式会社東芝 研究開発センター コンピュータ&ネットワークシステムラボラトリー 主任研究員 辰村光介氏

現在、この技術を社会に実装するための実証実験を進めている最中であると辰村氏は語る。

 

「シミュレーテッド分岐アルゴリズムで社会や産業の問題を解決するには、まず諸問題をどのようにしてイジング問題として定式化するかを考える必要があります。これには数学的に高度な工夫が必要です。すでに各方面から大きな反響をいただいていますが、我々としてはこのアルゴリズムをどう活用するか、具体的かつ現実的なアイデアが寄せられることを期待しています」(辰村氏)

組合せ最適化問題の解決で社会は大きくアップデートする

東芝では現在、シミュレーテッド分岐アルゴリズムの実用化を進めている。では、それによって世の中にどのような変化が起こるのだろうか。

 

物流効率が上がって配送コストが下がったり、資産運用が有利になったりといったことに加え、例えば個々の体質や状態に合わせたパーソナル創薬が実現するなど、まだまだ多くの可能性が考えられます。また、我々としては今回の技術は、既存事業の効率化だけでなくパートナー企業とのアライアンスも活用した新規事業の立ち上げなど、様々なビジネスに生かせると思っています」(辰村氏)

 

かつてインターネットの登場で社会のベースに変革が起きたように、シミュレーテッド分岐アルゴリズムもまた、サービスプラットフォームとしてあらゆる技術の土台となるに違いない。組合せ最適化問題を解決する術の登場は、各分野を劇的にアップデートさせることになるだろう。

 

今回開発したアルゴリズムは、量子コンピューターの研究開発の過程から生まれたものだ。後藤氏は、量子コンピューターの目指す姿をこう語る。

 

「古典コンピューターは量子コンピューターより性能面で劣るものと位置づけられていますが、シミュレーテッド分岐アルゴリズムによって古典コンピューターの性能は飛躍的に向上しました。古典コンピューターがこうして大規模問題を高速に解けるようになった今、量子コンピューターは、少なくともそのパフォーマンスを超えるレベルに達していることが必須条件だと思います。そのうえで、費用対効果でメリットがあり、社会実装可能となって、初めて実用化されていくことになるでしょう

 

古典コンピューターの可能性を大きく引き上げた今回のアルゴリズム。この画期的な発明が実現した背景について両者が強調するのは、東芝ならではの研究環境だ。

 

「私のような計算機科学の者のほか、物理学、数学、数理工学、情報処理,クラウドコンピューティングと、多岐にわたるエキスパートがすべて揃っている企業は珍しいでしょう。シミュレーテッド分岐アルゴリズムは、こうした多様な人材が集まった東芝だからこその結晶であると思います。」(辰村氏)

 

「そもそも今回の着想を得たタイミングで、たまたま社内で辰村と出会えたのは運命的でした。一通りの人材が揃う東芝でなければ、これほど早く回路に実装することはできなかったはずです。」(後藤氏)

 

多彩な人材が有機的に連携したことで生まれたシミュレーテッド分岐アルゴリズム。これは社会や産業に大きな変革をもたらす最初の一歩なのだ。

後藤氏と辰村氏

Related Contents