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

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


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

この記事の要点は…

様々な社会課題の解決に立ちはだかる「組合せ最適化問題」

その良解を高速に導く、画期的な新解法が開発された

量子コンピューターのあるべき姿とは?

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

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

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

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

物流最適化

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

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

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

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

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

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

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

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

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

マシンスペック比較表

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

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

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

  • ↓ スクロールで続きを読む ↓