量子アニーリング法(クラスタ分析への適用)

情報科学の中心的な課題の1つに、与えられた問題の最適解を求めるという最適化問題と呼ばれるものがある。最適化問題は一般に難しく、それぞれの問題の特性に応じたアルゴリズムや、汎用性があり、かつ実装が容易な数値計算アルゴリズムが数多く考案されてきている。 多くの場合には、物理学の言葉に焼き直すと、与えられたハミルトニアンの基底状態を求める問題と等価となる。 そのため最適化問題を効率良く解く手法の開発は、情報科学の問題としてだけではなく、物性科学や統計力学においても極めて重要な問題である。 物理学の知見を活かした汎用的アルゴリズムの一例として、交換法[A]やシミュレーテッドアニーリング法[B]と呼ばれる方法があり、幅広い分野で適用されている有用な手法である。 シミュレーテッドアニーリング法では、温度パラメータを変化させることにより、熱揺らぎを巧みに制御することで、安定状態を探索するアルゴリズムである。 一方、シミュレーテッドアニーリング法の類似アルゴリズムとして、量子アニーリング法と呼ばれる手法が開発された[C,1]。 量子アニーリング法では熱揺らぎの代わりに量子揺らぎを巧みに制御することで、安定状態を探索する。 取り扱いが容易で、性質が明確に理解される統計力学的モデルに対する量子アニーリング法の有用性はよく研究されてきている。 そこで我々は、情報工学における重要な課題の1つである、クラスタ分析に対する量子アニーリング法の有用性を検討した。 クラスタ分析は解の空間が非常に大きく、また幾つもの準安定状態があるタイプの問題であるから、工夫された方法を用いない限り、良い解を見つけることができない問題である。 我々は熱揺らぎと量子揺らぎを同時に巧みに制御する「熱・量子同時制御型アニーリング法」を用い、実データを用いたクラスタ分析の問題を解析した。 その結果、通常のシミュレーテッドアニーリング法よりも良い解をほぼ同程度の計算実行時間で得ることに成功した[2,3]。 実用的な問題に対する量子アニーリング法の適用はまだ殆ど無く、量子統計力学・計算物理学・情報科学・情報工学の境界領域としての研究としても意義深いと考えられる。

本研究は佐藤一誠氏(東大情報基盤センター)、栗原賢一氏(Google)、中川裕志教授(東大情報基盤センター)、宮下精二教授(東京大学)との共同研究である。


本項目に関する我々の論文:
[1] Shu Tanaka and Ryo Tamura, to appear in Kinki University Series on Quantum Computing Series "Lectures on Quantum Computing, Thermodynamics and Statistical Physics".
[2] Kenichi Kurihara, Shu Tanaka, and Seiji Miyashita, Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI2009).
[3] Issei Sato, Kenichi Kurihara, Shu Tanaka, Hiroshi Nakagawa, and Seiji Miyashita, Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI2009).

References:
[A] K. Hukushima and K. Nemoto, Journal of the Physical Society of Japan, 65, 1604 (1996).
[B] S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi, Science 13, 671 (1983).
[C] T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998).