量子アニーリングを機械学習に応用し、実ビジネスのデータを解析する試み始まる

データサイエンスの最先端と物理学の研究の最先端が、ビジネスの現場で出会った──話を聞いて、そんな感想を持ちました。

どういう話かというと、リクルートグループ内でWebサービスの開発などを担当する機能会社であるリクルートコミュニケーションズ(RCO)が、同社のビジネスに量子物理の最新の知見を取り入れた手法である「量子アニーリング」を活用しようとしている、という内容です。

以下、先日行われたイベントから、早稲田大学高等研究所の田中宗助教の講演「次世代量子情報処理技術「量子アニーリング」が拓く新時代 ─ 情報処理と物理学のハーモニー」の内容に沿って説明します。

RCOと田中助教は共同研究を開始しています。RCO側の狙いは、データ解析の手法として利用が進む機械学習に欠かせない情報処理である「クラスタリング」に対して、最新の手法「量子アニーリング」を活用することです。一方、田中助教の狙いは、リクルートグループのビジネスに伴って発生するが大規模データ、それも現実世界を反映した大規模データを素材として、量子アニーリングが向く分野、向かない分野の知見を蓄えることです。いわば、データサイエンス分野を物理学の実験として活用しようとしているのです。


http://www.slideshare.net/shu-t/ss-57178026
田中宗助教の講演資料。100ページの大作。

物理現象を応用した計算手法で問題を解く

量子アニーリングという手法は日本で生まれました。この手法を提案した1998年の「門脇-西森の論文」は有名です。最近になってカナダD-Wave Systems社が量子アニーリングのための専用マシンを開発し、それを米国の研究機関やGoogleが評価したことで一躍有名になりました。2015年12月には、GoogleはD-Waveを使うことにより従来手法より1億倍速く計算できたとの研究結果を発表しています。

量子アニーリングとはどういう手法かというと、「組み合わせ最適化問題」と呼ぶ、通常の計算手法では問題のサイズが増えるのに従い計算量が爆発的に増えてしまう問題を、

「物理現象に計算をしてもらう」

ことにより、効率よく解こうとするものです。

組み合わせ最適化問題は、コンピュータサイエンスではお馴染みの問題です。例えば「巡回セールスマン問題」などがそうです。工場のシフト計画、集積回路の設計、医用画像読影技術、それにFinTech分野と、様々な分野で組み合わせ最適化問題が現れます。機械学習で出てくるクラスタリングも、やり方しだいで計算量が爆発的に増大してしまう種類の問題です。そこで、この問題を物理現象に置き換え、物理現象に計算をしてもらうことで効率よく解こうとするものです。

一方、この問題を解くための計算手法として、量子アニーリングが考え出されました。アニーリングとは「徐冷」「焼きなまし」と訳されるように、熱に関係する言葉です。以前からある「シミュレーテッドアニーリング法」では熱のゆらぎを用いて問題を解きます。量子アニーリングでは量子ゆらぎを用います。

専用マシンD-Waveで有名に、通常のコンピュータを使う手法も

ところで、量子アニーリングはD-Waveという専用マシンで有名になったわけですが、このマシンは約10億円(推定)はする高価な装置です。装置の内部には減磁や冷却のための装置が詰まっていて、絶対零度に近い極低温で動作する超伝導デバイスを守っています。超高級な物理実験装置を、組み合わせ最適化問題を解く仕組みとして使うわけです。

価格は推定10億円、取り扱いにも技能が必要と想像される専用マシンの話はちょっとワクワクします。一方で、10億円もする専用マシンを使える機会を持てる人はごく少数でしょう。では、多数派の人にとって量子アニーリングは手が届かないのかというと、そうではありません。私たちが慣れ親しんだ、普通のコンピュータを使う別のやり方があるのです。それを量子モンテカルロ法(QMC)と呼びます。

D-Waveは高価で取り扱いが難しいという問題がありますが、それだけでなく別の問題もあります。田中助教が指摘するD-Waveの限界は、「解ける問題のサイズに上限がある」ことです。巡回セールスマン問題でいうと、今のD-Waveの能力である「1000量子ビット」では、「30都市を回る巡回セールスマン問題」を解くことが限界になります。結構、小さい数字で限界に到達してしまうのです。ソフトウェアによる量子アニーリング法は、もちろん所要時間はかかりますが、それよりサイズが大きい問題を解くことが可能です。

今回の取り組みではソフトウェアによる量子アニーリング、量子モンテカルロ法を試みようとしています。コンピュータの中でサイコロをふることで、量子現象をシミュレートします。ソフトウェアで専用マシンに勝てるのでしょうか? 速度ではかないません。しかし、D-Waveの性能曲線(問題のサイズに対する所要時間のカーブ)と、ソフトウェアによる量子アニーリングの性能曲線は、傾きがだいたい同じです。


ソフトウェアによる量子アニーリング法(図中の「QMC」の性能曲線は、量子アニーリング専用マシンD-Waveと傾きがだいたい同じ。横軸は問題の大きさ(ビット数)、縦軸は所要時間(対数軸)。
Googleによる研究論文から引用。
出典: Denchevほか,"What is the Computational Value of Finite Range Tunneling?"

そしてグラフの傾きは、従来手法(図中の「SA」)に比べればずっと緩やかです。片対数グラフでほぼ直線のグラフなので、指数関数的な(爆発的 な)増加ではあるものの、あるサイズ以上の問題では従来手法に比べてはるかに短い時間で問題を解けます。“使いどころ”がある手法なのです。

田中助教は、既存方式(シミュレーテッドアニーリング法)と量子アニーリング法を組み合わせた新たな方式を開発するなど、より性能が良い手法を作り上げようとする研究を行っています。こうした手法の工夫を繰り返すことができるのも、ソフトウェアの良いところです。

私たちが慣れ親しんだコンピュータとソフトウェアによって、最新の物理学の知見を取り入れた手法を機械学習に応用し、現実のビジネスに直結する成果を出せる可能性が、目の前に広がっています。コンピュータサイエンス、物理学、そしてビジネスの最先端が出会う、そんな世界がやってきているのです。