- 田中宗（Shu Tanaka） 助教（2015年11月当時）
産業界との共同研究がスタート
2015年11月、早稲田大学と株式会社リクルートコミュニケーションズは、量子アニーリングを使ったデータ分析法を開発するために共同研究をスタートさせました。マーケティング効果を最適化するために量子アニーリングを利用しようという試みで、実現すれば量子アニーリングの産業利用が始まります。この共同研究で私は、技術の核となる「理論の構築」を行います。量子アニーリングとはいったい何なのでしょうか。また、それによって何ができるのでしょうか。
膨大な選択肢から、一番◯◯を探す
私たちの日常生活では、「一番◯◯」なものを知りたいという状況にしばしば直面します。例えば、いくつかの場所に出かける場合には一番交通費が安く済むルートや到着時刻が一番早いルートを知りたいですし、何か作業をする場合には一番短い時間でできる方法はないか考えます。このように、膨大な選択肢から、「一番◯◯」な何かを探すことを「組合せ最適化問題」といいます。このような問題は身近な日常生活だけでなく、様々な場面に現れます。例えば、荷物の配達スケジュールや工場の作業手順、集積回路の設計など、産業界における重要なタスクに、組合せ最適化問題は多数潜んでいます。そのため、組合せ最適化問題を高速に解く方法が開発されれば、効率化やコスト削減といった産業界のニーズに応えることが可能になるわけです。
組合せ最適化問題の答えを知ることは、実はとても難しい問題です。それを、二択問題を例に考えてみましょう（図1）。全ての解答パターンの中から、全問正解、すなわち一番高い得点の解答を見つけたいとします。もし問題数が1問であれば、答えは正しいか間違っているかの2通りしかありません。問題数が2問でも、解答は4通りですから、全ての解答パターンから全問正解を見つけることは簡単です。問題数がずっと増えて50問になるとどうでしょうか。250通り（約10兆通り）の解答パターンになります。この場合、現在のスーパーコンピュータを用いて全ての解答パターンから全問正解を見つけるためにかかる時間は0.1秒になります。それほど困難ではないように思えるかもしれません。ところがその2倍の100問になると、スーパーコンピュータを使っても1000万年かかってしまいます。このように、膨大な選択肢から、一番◯◯を探す問題は大変難しい問題です。実際、私たちが直面するのは、この程度の規模、ないしはこれよりも遥かに大きい規模の組合せ最適化問題です。このように組合せ最適化問題の規模が大きくなるにつれて、急激に候補数が増えることを「組合せ爆発」と呼びます。組合せ爆発が、組合せ最適化問題の困難さの原因です。
図1: 二択問題の問題数の増加に伴う解答パターン数の増加と、スーパーコンピュータを使って、全ての選択肢から最高得点の解答を見つけるために要する時間（提供：田中宗助教）
物理現象を模倣した情報処理方法
理論物理学のアイディアを情報処理に活かす、という考え方は、実は古くから知られています。その1つに熱アニーリング（焼きなまし）という手法があります。焼きなましとは、合金を生成する際に、材料となる金属をいったん高温に熱してから徐々に冷ます工程のことです。高温にすると、“熱ゆらぎ”効果により、金属原子は激しく運動しバラバラになりますが、その後ゆっくり冷ますと原子は“最も安定な（最適な）状態”に落ち着き、強い合金が形成されます。実は、組合せ最適化問題は、ある種の物理モデル（イジングモデルといいます）に置き換えることができます。この置き換えをすることにより、組合せ最適化問題の答えと、イジングモデルの最適な状態が対応するのです。ですから、この原理を計算機上でシミュレーションし、組合せ最適化問題を解くという試みは30年以上前から活発に行われてきました。これをシミュレーテッドアニーリングといいます。
日本発の画期的情報処理方法「量子アニーリング」
シミュレーテッドアニーリングでは、熱ゆらぎにより、いったんランダムな状態を形成したうえで、徐々に温度を下げることにより、自発的に組合せ最適化問題の答えを出すという計算方法でした。キーワードは「ゆらぎ」です。実は、自然界にはもう一つ重要なゆらぎがあります。“量子ゆらぎ”です。量子ゆらぎを導入し、徐々に量子ゆらぎを弱めることにより、自発的に組合せ最適化問題の答えを出す方法として、量子アニーリングは提案されました。1998年、東京工業大学の西森秀稔教授と当時大学院生だった門脇正史博士による先駆的な研究です。その後の多くの研究により、量子アニーリングを使うとシミュレーテッドアニーリングに比べて、短時間で良い答えを得ることができると示唆されていました。
そのイメージを二択問題で表すと図2のようになります。“量子ゆらぎ”が加わっているとき、全ての解答が重なっています。それぞれの解答はAでもあり、かつBでもあるという重ね合わさった状態です。量子ゆらぎは、この重なり度合いを表しています。この重なり度合いを徐々に弱めていくことにより、全問正解が現れるという仕組みです。
図2: 量子アニーリングで答えが現れるイメージ（提供：田中宗助教）
新しい段階に入った量子アニーリング研究
量子アニーリングは、組合せ最適化問題を高速に解くと期待されている計算方法です。さらに私は、量子アニーリングをクラスタ分析に応用しようと考えています（図3）。クラスタ分析とは、膨大なデータを、潜在的な意味によって分類することを言います。データはただ持っているだけでは何の役にも立たず、意味ごとに分類することが重要です。量子アニーリングを使えば、より良質なデータ分類が短時間で可能と予想しています。
私が「量子アニーリング」を研究するようになったきっかけは、大学学部生時代に、統計力学を情報科学の分野に応用する研究を行っていた西森秀稔教授（東京工業大学）の研究室に所属したことが始まりです。統計力学は、原子や分子1つ1つの運動を統計的に扱うことで、巨視的な自然現象を理解する物理学です。この統計力学が情報科学に応用されていることは、これまで「物理学は自然現象を説明するもの」だと思ってきた私にはとても新鮮でした。西森研究室に所属していた当時は、量子アニーリングのことを全く知らなかったのですが、宮下精二教授（東京大学）の研究室に所属していた大学院生博士課程が終わる頃、量子アニーリングの研究を、宮下精二教授、中川裕志教授（東京大学）、当時東京工業大学の情報工学系の大学院生だった栗原賢一博士、当時東京大学の情報工学系の大学院生だった佐藤一誠博士と本格的に始めました。
時代が流れ、2011年にはカナダの企業が「世界初の商用量子コンピュータ」として、D-Wave（ディーウェイブ）と呼ばれる、量子アニーリング専用機械を発表しました。これは量子アニーリングを、物理現象として実際に起こすことのできるデバイスです。この発表を契機に、量子アニーリングの注目度は飛躍的に向上しました。
私は、量子アニーリングの課題はまだ多いと考えています。大きく分けて以下の3つが挙げられます。「量子アニーリングのキラーアプリケーションを発見する」「量子アニーリングがその能力を発揮する問題のタイプを検討する」「量子アニーリングを始めとした、イジングモデル型情報処理デバイスを開発する」です。これらの非常に大きい問題を少しずつ解決していくため、地道に研究を進めています。その中の1つが、冒頭で述べた、産業界との共同研究です。また、量子アニーリングをより広く知って頂くため、複数の書籍の執筆を行っております。
図3: 量子アニーリングを使ったクラスタ分析（提供：田中宗助教）
取材・構成：池田 亜希子
協力：早稲田大学大学院政治学研究科J-School
