量子アニーリング by 西森 秀稔  English

2016/9/29更新

2000量子ビット級の次世代機の概要が発表された。量子ビット数や計算速度の向上に加えて,これまでユーザサイドでは調整できなかった個別の横磁場の制御や計算途中でのサンプリング,古典計算機との協調による効率化など,より自由度の高い計算が出来るようになっている。

忙しい人のための要約 量子アニーリングの概要 具体的な定式化 強みと弱み 北米の動向 解説記事や報道,動画

忙しい人のための要約 (Executive Summary)

 量子アニーリングは最適化問題のための汎用的な基本アルゴリズムであり,D-Waveマシンのような量子アニーリング装置の基本動作原理である。1998年の門脇・西森の論文で提案され,量子力学を使わない手法に比べて高速化が見込めることが明確に示された。日本発の量子アニーリング装置用基本動作原理として世界的に注目されている。
 機械学習などの課題の多くが最適化問題であり,最適化問題を効率よく解くアルゴリズムの開発は社会的に大きなインパクトを持つ。
 最適化問題に加えて,データの確率分布を量子アニーリング装置上におけるイジング模型のボルツマン分布で表現して機械学習に応用する研究が立ち上がりつつある。例えばこちら。機械学習を支える次世代ハードの候補として注目を集めつつある。
 量子アニーリングの理論を実装したマシンがカナダのベンチャー企業D-Wave社から発売され,Google, NASA, Lockheed-Martinと南カリフォルニア大学, Los Alamos国立研究所などが導入した。
 D-Waveマシンが量子効果を使って動いているかどうかについて論争があったが,一定水準以上の量子効果が観測されるなどほぼ決着がついてる。
 D-Waveマシンが最適化問題を通常のコンピュータより高速に解けるかどうかについて,問題によって様々な結果が出ている。 量子アニーリングが得意とする問題の種類の解明が進められている。最近の論文リスト
 広く研究されてきた量子回路モデル(ゲート方式)の量子コンピュータのハードウェア開発は量子アニーリングに比べて遅れているが,膨大なオーバーヘッドを必要とする誤り訂正を回避するなど限定された方法で量子コンピュータの優位性を実証する動きが始まっている。
 量子回路モデルの量子コンピュータでは,その高速性能が真に発揮され,かつ社会的に有用な問題は量子シミュレーションなど数個に限られている。その他の用途にも使えるが,通常のコンピュータを上回る性能は出ない。
 Googleの量子人工知能研究所も独自に高機能の量子アニーリング装置を開発している。
 アメリカの国家プロジェクトIARPAで,高機能の量子アニーリング装置の開発に的を絞った大規模なプログラムQEOが開始された。トップクラスの研究機関・研究者を結集し,大規模な資金を集中投資して次世代機の基盤技術を確立しようとしている。

量子アニーリングの概要

量子アニーリング(Quantum annealing)は,量子効果を制御して,多変数1価関数(目的関数)の最小値を探す問題(最適化問題)を解く手法である。 パターン認識,自然言語処理,医療診断,金融その他を始めとする多くの重要な課題が最適化問題として定式化できるため,最適化問題の効率的な解法は社会的に大きなインパクトを持つ。また,データの確率分布を表現して機械学習に応用する研究も急速に立ち上がっていいる。

量子アニーリングを実行するためには,まず目的関数を2値変数の関数(イジング模型)として表現し,その関数の最小値を求める問題として定式化しなければならない。その目的関数に量子効果を現す項を追加する。最初に量子項の係数を大きく取り,すべての許される解候補を同じ重みで重ね合わせた状態(下の図の左側)を実現する。そして,ゆっくりと量子項の係数を小さくしていく。このプロセスにより,容易に実現できる初期状態から出発して,自然な時間変化を経て,下の図の右側のように最適解を高い確率で実現することを目指す。



横軸は2値変数の組の取るいろいろな値の組(古典状態),縦軸の黒の曲線は目的関数の値,青の線は各配位の存在確率を表す。
左の初期状態から始めて,シュレディンガー方程式に従って自然な時間発展をしたのち,右の最終状態に行き着く。

具体的な定式化

目的関数を2値変数の関数として表す典型例として,2値変数の2次形式(Quadratic Unconstrained Binary Optimization, QUBO)がある。統計力学で言うイジング模型である。イジング模型に横磁場を加えたもの(横磁場イジング模型)は,次の演算子で表現される。

σは2行2列の行列(パウリ行列)である。右辺第1項が通常の古典的イジング模型(最小化するべき目的関数)であり,第2項が量子ゆらぎを引き起こす横磁場項である。この係数Γ(t)を時間t=0で非常に大きい値に設定し,tが増えるとともに0に向けて小さくしていくのである。系全体の状態は,シュレディンガー方程式に従って自然に発展していく。

実際に解きたい問題をイジング模型で表現する過程が,いわばプログラミングに相当すると考えてもよい。組み合わせ最適化問題の変数は離散変数なので,2値変数の組み合わせで表現できることは明らかであるが,複雑な組み合わせが生じないように効率よく表現する問題は埋め込みと呼ばれ,重要な研究分野となっている。

現在広く使われている横磁場イジング模型を用いたこの形での量子アニーリングは,1998年に初めて定式化され,その有効性が示された[1]。この論文をきっかけとして,磁性体における実験的検証や[2],より複雑な系での大規模な数値計算による検証[3]などの研究が開始された。2001年には,有限の時間T ですべての過程を終了するタイプのプロセスが提案された[4]。

論文[4]では,断熱定理に基づいて基底状態をたどる問題として量子アニーリングが再定式化されて計算量の観点から解析が行われ,量子断熱計算(Quantum adiabatic computation)という名前が与えられた。
[1] T. Kadowaki and H. Nishimori, "横磁場イジング模型における量子アニーリング", Phys. Rev. E58 (1998) 5355.
[2] J. Brooke, D. Bitko, T.F. Rosenbaum and G. Aeppli, "ランダムな磁性体の量子アニーリング", Science 284 (1999) 779.
[3] G. E. Santoro, R. Martonak, E. Tosatti, and R. Car, "イジングスピングラスの量子アニーリングの理論", Science 295 (2002) 2427.
[4] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, "量子断熱変化のNP完全問題のランダムな例への応用", Science 292 (2001) 472.
論文[2,3,4]はいずれも論文[1]を引用しており,論文[1]が現在の量子アニーリング研究の源流をなしている。
また,厳密な最適解だけでなく最適解に近い近似解も含む多数の解を確率的に生成する確率分布の生成法としても注目を集めるようになっている。実際の装置では理想的な断熱発展は実現しておらず,非断熱効果や熱雑音などの影響により非最適解も相当な確率で生成される。これを逆手に取って,機械学習におけるボルツマン学習のサンプリングマシンとして有効な証拠が挙がっており[5],ここ1年度ほどで研究が急速に活発化している。
[5] S. H. Adachi and M.P. Henderson, "量子アニーリングの深層ニューラルネットワークの学習への応用", arXiv.1510.06356.

強みと弱み

最適化問題を解くために量子効果を用いる計算方法であるという意味で,量子アニーリングは量子計算の一種である。量子アニーリングが他の方法に比べて優れているかどうかを判断するには,判定基準をはっきりさせる必要がある。

北米の動向

解説記事や報道

量子アニーリングに関する総合的な解説や報道を列挙しておこう。原論文については,これらの記事の中の参考文献を参照。筆者の論文一覧もご覧下さい。 
西森 秀稔 JST CRDSワークショップでの講演記録 2016.3
西森 秀稔 "最適化問題を解く量子アニーリングとD-Wave" 応用物理学会微小光学研究会予稿
NHK Eテレ サイエンスZERO「量子コンピュータ」 2014年9月28日(日)放送
大関真之・西森 秀稔 "量子アニーリング"日本物理学会誌 66(2011)25
西森 秀稔 "量子アニーリングとD-Wave" 情報処理 (情報処理学会誌) 原稿
西森 秀稔 ”量子アニーリング法とD-Waveマシン” (日本計算工学会誌) 原稿
A. Das and B. K. Chakrabarti, "量子アニーリングとアナログ量子計算" Rev. Mod. Phys. 80 (2008) 1061
G.E. Santoro and E. Tosatti, "量子力学による最適化:断熱発展による量子アニーリング" J. Phys A 39 (2006) R393
S. Suzuki, J. Inoue, and B. K. Chakrabarti, "横磁場イジング模型における量子イジング相と転移" Springer, 2012

A. Ghosh and S. Mukherjee, "量子アニーリングと計算: 関連文献集" arXiv:1310.1339
中田敦 "驚愕の量子コンピュータ" 日経コンピュータ 2014年4月17日 ITPro
I. Zintchenko, E. Brown and M. Troyer, "Recent developments in quantum annealing" December 7, 2015

メディアでの報道一覧

動画

トップに戻る