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

2016/5/23 更新

忙しい人のための要約

 量子アニーリングは最適化問題の解法のひとつである。1998年の門脇・西森の論文で提案され,量子力学を使わない手法に比べて高速化が見込めることが明確に示された。
 機械学習などの課題の多くが最適化問題であり,最適化問題を効率よく解くアルゴリズムの開発は社会的に大きなインパクトを持つ。 最近,金融分野への応用に関するフォーラムQuantum for Quantsが開設された。
 量子アニーリングの理論を実装したマシンがカナダのベンチャー企業D-Wave社から発売され,Google, NASA, Lockheed-Martinと南カリフォルニア大学, Los Alamos国立研究所などが導入した。
 D-Wave社のマシンが量子効果を使って動いているかどうかについて論争があったが,一定水準以上の量子効果が観測されるなどほぼ決着がついてる。
 D-Wave社のマシンが最適化問題を通常のコンピュータより高速に解けるかどうかについて,問題によって様々な結果が出ている。 量子アニーリングが得意とする問題の種類の解明が進められている。最近の論文リスト
 D-Wave社のマシンが量子コンピュータかどうかについて論争があるが,ひとつの理由は「量子コンピュータ」の定義に曖昧さがあるためである。
 広く研究されてきた量子回路モデル(ゲート方式)の量子コンピュータのハードウェア開発は量子アニーリングに比べて大きく遅れており,実用化の目処は立ってない。
 量子回路モデルの量子コンピュータでは,その性能が真に発揮される問題は素因数分解(量子フーリエ変換)や量子シミュレーションなど数個に限られている。その他の用途にも使えるが,通常のコンピュータを上回る性能は出ない。
 NHK EテレサイエンスZEROの量子コンピュータ特集では一般向けの解説をしている。応用物理学会微小光学研究会予稿物理学会誌の記事もどうぞ。
 The Guardianの2016年5月22日付けのこの記事は,正確で分かりやすくかつ客観的な立場から書かれた大変良い解説です。

概 要

量子アニーリング(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]が現在の量子アニーリング研究の源流をなしている。

強みと弱み

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

北米の動向

カナダのD-Wave Systems社が量子アニーリングをハード的に実現する装置を開発し,数台がすでにGoogle, NASA,Lockheed-Martin, Los Alamos National Laboratoryなどのユーザに納入されている。現行機D-Wave 2Xは1000を超える量子ビットを有している。筐体は3メートル立方の大きな箱であるが,古典計算機のCPU+メモリに当たる中心部は写真の真ん中にある1センチ平方の小さなチップであり,これが15mK程度の超低温に冷却されて超伝導状態で動作している。

D-Waveマシンの動作を検証した結果や最適化問題を解いた例が学術論文として多数発表されている。これらの論文において,量子アニーリングが実際に実現されているとしないと解釈できないデータが報告されている。現時点では,通常の古典計算機で出来ないスケールの計算が出来るようになったわけではない。その原因が精力的に調べられており,実装された量子ビット数の少なさの他に,ノイズの影響やパラメータ設定の難しさの影響などが検討されている。これらの問題点を解決するために,温度雑音の影響の評価や誤り訂正符号の研究が急速に進展している。また,量子アニーリングが高速性を発揮する問題群の特徴が明らかにされつつある。

米国の大規模国家プロジェクトIARPAで高度な量子アニーリング装置の開発プログラムが開始される。 安定な超伝導素子の開発,古典計算機でのシミュレーション不可能な領域への機能拡張,多体相互作用のハード的な組み込みよる高効率化などによる超高性能の達成を目指している。

金融分野への量子最適化手法の応用に関するフォーラムQuantum for Quantsが開設された。金融や投資などの問題を,量子アニーリングを用いて最適解を探索する手法など実社会の問題への量子最適化の応用が議論されている。

GoogleのQuantum Artificial Intelligence Laboratoryもハード開発に着手している。

解説記事や報道

量子アニーリングに関する総合的な解説や報道を列挙しておこう。原論文については,これらの記事の中の参考文献を参照。筆者のグループの論文一覧のページもご覧下さい。 
西森 秀稔 "最適化問題を解く量子アニーリングと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

メディアでの報道一覧

トップに戻る