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

2017/11/17更新
忙しい人のための要約 量子アニーリングの概要 具体的な定式化 強みと弱み 北米の動向 解説や動画   FAQ

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

 量子アニーリングは最適化問題のための汎用解法であり,D-Waveマシンのような量子アニーリング装置の基本動作原理である。1998年の門脇・西森の論文で提案され,量子力学を使わない手法に比べて高速化が見込める明確な数値データが示された。
 機械学習などの課題の多くが最適化問題であり,最適化問題を効率よく解くアルゴリズムの開発は社会的に大きなインパクトを持つ。
 最適化問題に加えて,量子アニーリングをサンプリングに使って機械学習に応用する研究が立ち上がりつつある。解説論文2件はこちらこちら
 量子アニーリングを多少拡張すると汎用化されて任意の計算が出来るようになり,また指数関数的に高速化される例も提示されている。これを実現するハードウエア開発競争が始まっている。
 量子アニーリング装置がカナダのベンチャー企業D-Wave社から発売され,Google, NASA, Lockheed-Martinと南カリフォルニア大学, Los Alamos国立研究所などが購入した。また,Volkswagen, Oakridge国立研究所リクルートコミュニケーションズなどがクラウドで使用している。
 D-Waveマシンが最適化問題を通常のコンピュータより速くあるいは正確に解けるかどうかについて,問題によって様々な結果が出ているが,最近は肯定的な例が多くなっている。最近の論文リスト
 従来より研究されてきた量子ゲート方式(回路モデル)の量子コンピュータのハードウェア開発は量子アニーリングに比べて遅れている。膨大なオーバーヘッドを伴う誤り訂正を必要としない小規模の問題で量子コンピュータの原理的優位性を検証する動きが始まっているが,実用化には距離がある。
 量子ゲート方式の量子コンピュータでは,その高速性能が発揮され,かつ社会的に有用なアルゴリズムは限られている。現時点で現実的かつ社会的に有用な使い道は小さな分子のシミュレーションが主であり,理論的には汎用だが実質的には専用機である。ある程度以上の規模での効率的な量子シミュレーションが出来れば多大の経済的価値を生むこともあって,米国の巨大IT企業群が集中的な投資を行なっている。
 量子ゲート方式の量子コンピュータでネットのデータのやりとりの安全性を保証しているRSA暗号が破られる可能性が議論されているが,そのためには1億量子ビット程度を実装するマシンが必要とされており実質的には実現不可能である。Googleにおけるハード開発のリーダーJohn Martinis氏の見解はこちら
 アメリカの国家プロジェクトIARPA QEOGoogleの量子人工知能研究所も高機能の量子アニーリング装置を開発している。

量子アニーリングの概要

量子アニーリング(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]が現在の量子アニーリング研究の源流をなしている。なお,1998年以前にも量子アニーリングという言葉は使われていた[5]。これらの論文は量子力学にヒントを得た古典アルゴリズムや連続空間におけるポテンシャル最小化の提案であり,今日使われている意味での量子アニーリングとは異なっている。 実際,D-Waveの2017年の論文[6]には"D-Wave processors solve Ising problems by quantum annealing in the form proposed by Kadowaki and Nishimori. (D-Waveのプロセッサーは門脇・西森が提案した形式での量子アニーリングによりイジング問題を解く。)"と明記されている。
[5] B. Appolini et al , "A numerical implementaton of "quantum annealing"",Proc. Ascona/Locardo Conf. (1998); A. B. Finnila et al, "Quantum annealing: A new method for minimizing multidimensional functions" Chem Phys. Lett. 219, 343 (1994).
[6] J. King et al, "Quantum Annealing amid Local Ruggedness and Global Frustration", arXiv:1701.04579.
また,厳密な最適解だけでなく最適解に近い近似解も含む多数の解を確率的に生成する確率分布の生成法としても有用である。実際の装置では理想的な断熱発展は実現しておらず,非断熱効果や熱雑音などの影響により非最適解も相当な確率で生成される。これを利用して,機械学習におけるサンプリングの研究が急速に活性化している[7]。
[7] J. Biamonte et al, Nature 549, 195 (2017); V. Dunjko and H. J. Briegel, arXiv:1709.02779

強みと弱み

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

北米の動向

解説や動画

量子アニーリングに関する総合的な解説を列挙しておこう。原論文については,これらの記事の中の参考文献を参照。筆者の論文一覧もご覧下さい。 
NHK 【視点・論点】「量子コンピューターの可能性と課題」(2017年9月4日放送)
西森秀稔,大関真之「量子コンピュータが人工知能を加速する」日経PB
西森 秀稔 JST CRDSワークショップでの講演記録 2016.3
西森 秀稔 "最適化問題を解く量子アニーリングとD-Wave" 応用物理学会微小光学研究会予稿
NHK Eテレ サイエンスZERO「量子コンピュータ」 2014年9月28日(日)放送
大関真之・西森 秀稔 "量子アニーリング"日本物理学会誌 66(2011)25
西森 秀稔 "量子アニーリングとD-Wave" 情報処理 (情報処理学会誌) 原稿
西森 秀稔 ”量子アニーリング法とD-Waveマシン” (日本計算工学会誌) 原稿
T. Albash and D. A. Lidar, "Adiabatic Quantum Computing" arXiv:1611:04471
I. Zintchenko, E. Brown and M. Troyer, "Recent developments in quantum annealing" December 7, 2015
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

動画

FAQ

Whurleyさんによるsuperposition.comでのインタビュー記事の一部の和訳です。全文は元の記事をご覧ください。 

Q: 量子コンピュータは古典コンピュータ(普通のコンピュータ)に取って代わるのでしょうか。
A: 量子コンピュータは古典コンピュータを全面的に置き換えるものではありません。量子コンピュータは,古典コンピュータではひどく時間がかかる特定の種類の問題を解くのに使われます。量子コンピュータをレーシングカーに例えてみましょう。レーシングカーはサーキットではとてつもなく速く走りますが,買い物や通勤などの日常用に使う人はいません。
量子コンピュータと古典コンピュータはそれぞれの役割を担い,場合によっては協力し合って共存し続けるでしょう。

Q: ゲート模型の量子コンピュータと量子アニーリングマシンは,問題の解き方がどう違うのですか。素人にも分かるように説明してください。
A: ゲート模型は,1ステップずつプログラムを書いてそれに従って動作します。非常にうまく出来たアルゴリズムを走らせるととてつもなく速く走りますが,そのようなアルゴリズムを作れるのは飛びぬけた才能の人だけです。
アニーリングマシンは,細かなプログラムの指示で動くのではなく自然な物理法則に従って,ある意味勝手に答えを見つけます。高い山や谷,あるいは盆地,それらを結ぶトンネルなどがあちこちにある地形を想像してみましょう。雨が降ると,雨水は谷やトンネルを通って自然に低い方に流れていきます。アニーリングもこれと似たようなところがあります。最適化問題をエネルギーの地形に翻訳すれば,後はマシンが答えを見つけてくれます。

Q: 量子コンピュータについてのよくある誤解は何でしょうか。
A: 量子コンピュータはどんな問題でも超高速に解く夢の次世代コンピュータだというのは広く行き渡った誤解です。ゲート模型でもアニーリングであっても,量子コンピュータはそれに適した問題には威力を発揮しますが,適した問題の数は限られています。

Q: 量子コンピュータの使い方として,どんな応用が一番面白いと感じますか。
A: 量子シミュレーションです。量子磁性について,D-Waveの研究者が古典コンピュータではほとんど不可能なサイズのシミュレーションをすでに行っています。次世代のD-Waveマシンでは,他のどんな方法でも調べることが出来ない領域に入っていくと思われます。

トップに戻る