量子アニーリング(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]，研究が活発化している。
[5] S. H. Adachi and M.P. Henderson, "量子アニーリングの深層ニューラルネットワークの学習への応用", arXiv.1510.06356.
強みと弱み
ある種の問題を解くためにアルゴリズムレベルで量子効果を用いる計算方法であるという意味で，量子アニーリングは量子計算の一種である。量子アニーリングが他の方法に比べて優れているかどうかを判断するには，判定基準をはっきりさせる必要がある。
-
シミュレーテッド・アニーリング
確率的探索を用いて最適化問題を解くシミュレーテッド・アニーリング(Simulated annealing)は，広く普及した強力な方法である。量子アニーリングの横磁場の係数Γをシミュレーテッド・アニーリングの確率を制御する変数である「温度」と対応させる。同じ時間で比較すると，前者が後者より正しい最適解にたどり着く確率が高いことが証明されている[6]。シミュレーテッド・アニーリングと同様に，量子アニーリングは通常の計算機上で量子モンテカルロ法によりシミュレートできる。しかしながら，大規模な問題で量子アニーリングの特性を生かすには，専用の量子デバイスを用いる必要がある。[6] S. Morita and H. Nishimori, "量子アニーリングの数学的基礎", .J. Math. Phys. 49 (2008) 125210.
-
量子回路モデル
量子計算の理論的および実験的な研究は，量子ゲートを離散的に作用させて状態を望ましい方向に誘導して行く量子回路モデル（量子ゲート方式）に基づいたものが伝統的には多かった。膨大な研究の蓄積があるが，環境の影響による量子状態の破壊（デコヒーレンス）が深刻な問題である。デコヒーレンスを修正する誤り訂正の技術を取り入れるとすると，実用に耐える量子計算機の構築には極めて多くの量子ビットの集積と精密な制御が必要であるとされているが，そのようなシステムの構築の目処は立ってないのが実情である。このため，ごく小規模なシステムにデコヒーレンスが起きるまでの時間が比較的長い高性能の超伝導回路を使用して，量子誤り訂正なしに計算を実行する試みが始まっている [7]。基礎的な原理の検証であり，実用性の立場からどのような意味を持つかは明らかでない。
量子回路モデルによる本質的な高速化（指数関数時間の多項式時間への緩和）が保証されているアルゴリズムは，実用性を持つものとしては，素因数分解と量子シミュレーション，最適化および線形代数の一部の演算に限られている。量子回路モデルに基づく量子コンピュータが仮に将来できたとしても，これらの特殊な計算しか高速処理できない。そのほかの用途にも使えるが，通常のコンピュータを上回る性能は出ない。実質的には専用機と理解する必要がある。
素因数分解が高速に出来るとネット上のセキュリティ保持に広く使われているRSA暗号が容易に解読できるようになる。ネット上でのデータのやり取りの安全性を保証している暗号の無効化は社会インフラを破壊する行為であり，犯罪性を帯びた反社会的な行為であることを認識する必要がある。ただし，2000ビット程度のRSA暗号を破るには1億量子ビット程度の量子コンピュータが必要とされており，実際には実現は不可能である。
量子回路モデルの量子コンピュータの現実的な応用があるとすると，比較的小規模な量子系のシミュレーションが候補である。量子誤り訂正を使わずに，100量子ビット規模の装置を用いて比較的単純な分子の性質を調べる研究などが可能性として取りざたされている[7, 8, 9]。また，線形の連立方程式を高速に解くことにより，機械学習などの問題も効率よく扱えるという提案もあるが[10]，注意深い検討が必要である[11]。
[7] P.J.J. O'Malley et al, "Scalable Quantum Simulation of Molecular Energies", Physical Review X6, 031007 (2016).
[8] B. Bauer et al, "Hybrid quantum-classical approach to correlated materials", arXiv:1510.03859.
[9] M. Reiher et al, "Elucidating reaction mechanisms on qunatum computers", Proc. Nat. Acad. Sci. USA., 114, 7555 (2017).
[10] A. W. Harrow, A. Hassidim, and S. Lloyd, "Quantum algorithm for linear systems of equations", Phys. Rev. Lett. 103, 150502 (2009);
Z. Li et al, "Experimental realization fo a quantum support vector machine", Phys. Rev. Lett. 114, 140504 (2015)
[11] S. Aaronson, "Read the fine print", Nature Physics, 11, 291 (2015).
量子回路モデルと比べると，量子アニーリングは安定な基底状態（エネルギーが最も低い状態）をたどるよう設計されているため，デコヒーレンスの影響を受けにくい。また，最適化問題を一旦イジング模型で表現すると，横磁場を大きな値から小さな値に変化させるだけでよく，量子回路のように具体的なアルゴリズムを1ステップずつ明示的に書き下す必要がない。
量子回路モデル（ゲート方式） 量子アニーリング 目的 すべての計算（通常のコンピュータの上位互換） 組み合わせ最適化問題とサンプリング 強み 指数関数的な高速化が保証されているアルゴリズムがある。誤り訂正方式が確立している。 最適化問題やサンプリングは実社会での応用範囲が極めて広い。ノイズに比較的強い。 弱み ハードがノイズに極めて弱い。 誤り訂正によりノイズの影響を除去できることが保証されているが，通常のコンピュータで解けない問題を解くための実装には数千万以上のきわめて多くの量子ビットを必要とし現実性に欠ける。仮に大規模なハードが出来たとしても，高速化が保証されている数個の問題（素因数分解，量子シミュレーションなど）以外では通常のコンピュータを上回る性能は出ないため，実用的な用途が限定された特殊な装置である。 指数関数的な高速化が理論的に保証されている実用的な問題が見つかってない。 解きたい問題が量子アニーリングマシン上で通常のコンピュータに比べて高速に解けるかどうかはやってみないとわからないし，速くない場合も多い。 実装状況 約20量子ビット（超伝導，イオン，フォトン，量子ドットなど） 約2000量子ビット（超伝導） -
通常のコンピュータ（古典コンピュータ）
量子アニーリングの目的は最適化問題とサンプリングに限られおり，広く普及している通常のコンピュータの多くの機能を置き換えるものではない。この後者の点に関しては，量子回路モデルでも同様である。量子コンピュータはどんな処理でも超高速にできる次世代コンピュータと思っている人がいるようであるが，量子回路モデルであれ量子アニーリングであれ，それは間違いである。量子回路モデル方式でも量子アニーリング方式でも，量子コンピュータは特殊な目的のための専用機ないし専用アクセラレーターと理解する必要がある。
最適化問題・サンプリングに限るとすると，量子アニーリングを用いることにより通常のコンピュータより高速に良質の解答を出せるかどうかは問題による。D-Waveマシンによるベンチマークテストでは，大幅な高速化を達成できた例もあるが，逆の例もある。量子ビット間の結合の度合いが限られていることやノイズなどの影響を除去する技術がまだ不十分なこと，速くなる例が原理的に限られている可能性などが原因として検討されている。 -
専門家向けの補足
- QUBO(イジング模型)で表現できる全ての最適化問題中で最も難しい問題について，確実に正解を得るには指数時間がかかる。
- いくつかの特定の問題について，実際に（エネルギーギャップの評価から）指数時間がかかることが明らかにされている。
- 数値計算および解析評価によると，定性的にはともかく（すなわち，指数時間が多項式時間まで緩和されるかどうかは別として），定量的には量子アニーリングはシミュレーテッド・アニーリングに比べて同じ時間でも高い確率で正解に到達する場合が多いという研究が多数報告されている。
- 古典アルゴリズムで指数時間がかかる問題について，たいていの場合量子アニーリングを使うと遙かに高速に正解に行き着けるという期待は過剰である。一方，そのような問題は全くないだろうという思い込みは誤りである。実際，2分木上の遷移に関するこの論文では劇的な（指数関数的な）高速化が示されている。ただ，問題設定が特殊で実用的な広がりには欠ける。量子シミュレーションのような実用的にも重要な例の構築が待たれる。
- D-Waveマシンの動作が量子力学に従って動いているか（量子もつれなどの量子効果があるのか）については，いくつかの論文が提出されている。システム全体にわたる直接的な測定は難しいようであるが，数十量子ビットくらいまででは量子効果の存在は確実視されている
[12,13,14]。
[12] T. Lanting et al, ,"Entanglement in a Quantum Annealing Processo", Phys. Rev. X 4, 021041 (2014)
[13] S. Boixo et al, "Experimental signature of programmable quantum annealing", Nature Commun. 4, 2067 (2013)
[14] S. Boixo et al, "Computational multiqubit tunnelling in programmable quantum annealers", Nature Commun. 7, 10327 (2016)
- D-Waveマシンを構成している量子ビットが量子性を保っている時間（コヒーレンス時間）は数10ナノ秒であるが，計算時間は数10マイクロ秒なので，量子アニーリングに基づく量子力学的な操作が後者の時間スケールで実現しているのはちょっと考えると不思議である。しかし，上述の実験的証拠に加えて理論的な検討もなされ，外部からの擾乱は各量子ビット個別にではなくシステム全体の状態に働くため，個別の量子ビットのコヒーレンス時間からの直接的な推論とは違った見方が必要だと現在では考えられている
[15]。
[15] T. Albash and D. Lidar, "Decoherence in adiabatic quantum computation", Phys, Rev. A 91, 062320 (2015)
- 量子アニーリングは量子回路モデルと違って，問題を一旦QUBOで表現すれば，具体的な問題に対するアルゴリズムを明示的に作成する必要がない。実際に量子アニーリングをハード的に実現する装置において，ともかく実験を実施してみることが出来る。この点が，量子アニーリングの研究の活性化の大きな理由となっている。
- 基底状態を断熱的にたどらなくても，問題サイズに依存しない確率で正解に行き着くことが出来れば十分である。断熱性に
立脚したエネルギーギャップおよび計算時間の評価は，量子アニーリングの性能評価の一面にすぎない。 実際，上記の2分木上の遷移の問題では，基底状態をたどってない。さらに，温度などの外界からの擾乱効果も含めて量子アニーリングをとらえることもできる。完全な孤立系で基底状態を忠実にたどることを前提とした｢断熱量子計算(Adiabatic
Quantum Computation)｣は量子アニーリングQAの一部に含まれる概念であるが，後者には前者に含まれない部分がある。
- 量子回路モデル（ゲート方式）と量子アニーリングは，後者で相互作用の種類を拡張すれば，原理的には等価であることが証明されている [16]。また，同じ拡張により古典的にはシミュレート困難になること(non-stoquastic)も知られている。しかし，具体的に片方の言葉をもう一方に翻訳する作業は単純ではない。例えば因数分解の高速アルゴリズムを拡張された量子アニーリングマシンで動かすことは現実的には大変難しいし，逆に，量子アニーリングで高速に解けることが分かっている2分木遷移の問題を量子回路モデルの量子コンピュータのアルゴリズムとして書き下しても，現実に実行可能なものになるかどうかは，はなはだ疑問である。実質的には別の方式である。
[16] J. D. Biamonte and P. J. Love,"Realizable Hamiltonians for universal adiabatic quantum computers", Phys. Rev. 78, 012352 (2008).
- 量子アニーリングマシンを量子コンピュータと呼ぶどうかは，量子コンピュータの定義による。量子計算にかかわる様々な用語の標準化についてIEEE SAで委員会が設立されて検討が始まる。
- 量子アニーリング研究の最新動向については，AQC2017のプログラム及び講演動画が参考になるだろう。
- QUBO(イジング模型)で表現できる全ての最適化問題中で最も難しい問題について，確実に正解を得るには指数時間がかかる。
北米の動向
D-Wave
カナダのD-Wave Systems社が量子アニーリングをハード的に実現する装置を開発し，数台がすでにGoogle,NASA，Lockheed-Martin, Los Alamos National Laboratoryなどのユーザに納入されている。現行機D-Wave 2000Qは2000を超える量子ビットを有している。筐体は3メートル立方の大きな箱であるが，古典計算機のCPU+メモリに当たる中心部は写真の真ん中にある1センチ平方の小さなチップであり，これが15mK程度の超低温に冷却されて超伝導状態で動作している。
D-Waveマシンをめぐる研究動向
D-Waveマシンの動作を検証した結果や最適化問題を解いた例が学術論文として多数発表されている。これらの論文において，量子アニーリングが実際に実現されているとしないと解釈できないデータが報告されている。現時点では，通常の古典計算機で出来ないスケールの計算が出来るようになったわけではない。その原因が精力的に調べられており，実装された量子ビット数の少なさや結合の仕方の制約の他に，ノイズの影響やパラメータ設定の難しさの影響などが検討されている。これらの問題点を解決するために，温度雑音の影響の評価や誤り訂正符号の研究が急速に進展している。また，量子アニーリングが高速性を発揮する問題群の特徴が明らかにされつつある。さらに，最低エネルギー状態（基底状態）を正確に求める最適化問題だけでなく，比較的低いエネルギー状態への分布を推定して機械学習への応用を目指すサンプリングの研究が始まっている。
また，D-Waveマシンの単独運用でなく通常のコンピュータとのハイブリッド使用に向けて技術開発が急速に進んでいる。例えばこの特許やオークリッジ国立研究所の例を見よ。
米国の国家プロジェクト
米国の国家プロジェクトIARPAで高度な量子アニーリング装置の開発事業が開始された。 膨大な予算を投入して，長時間安定な超伝導素子の開発，古典計算機でのシミュレーション不可能な領域(non-stoquastic)への機能拡張，長距離相互作用や多体相互作用のハード的な組み込みよる高効率化などによる超高性能達成の基盤技術確立を目指している。USC(南カリフォルニア大)，MIT, Harvard, UC Berkeley, Caltechなどとともに東工大から筆者も参加。
Googleのハードウェア研究
Googleは，Quantum Annealer Ver. 2と称する量子アニーリング装置を制作している。カリフォルニア州のサンタバーバラにあるグーグルの量子人工知能研究所のハードウエア研究所は，世界最初で最大の量子データセンターを目指しているとのことである。通常のコンピュータ上での処理の一部を量子プロセッサーに渡すことにより，全体としての計算効率の向上を図るいわばハイブリッドによる新たな方向性を模索している。
実問題への応用などソフトウェアの展開
D-Wave社および関連ベンチャー企業が実問題に対応する応用ソフトの開発を急速に進めている。現行機上には直接は乗せられない大規模な問題を部分問題に分割してD-Waveマシン上で最適化し，最後に部分問題の解をつなぎ合わせて全体の解を構成する手法を自動化して実行するアプリケーションなども開発しているようである。実問題に対処している一般ユーザがハードの構成やその制約を意識することなく問題の解を得られる環境が整い始めている。
例えば，VolkswagenとD-Wave社の協業による交通流の最適化の論文[17]では，量子および古典コンピュータのハイブリッド計算や，D-Waveマシンに大きな問題を分割して載せるためのインターフェースqsolveの利用など，興味深い応用技術について記述されている。
[17] F. Neukert et al, "Optimizing traffic flow using quantum annealing and classical machine learning", arXiv:1708.01625.
解説や動画
量子アニーリングに関する総合的な解説を列挙しておこう。原論文については，これらの記事の中の参考文献を参照。筆者の論文一覧もご覧下さい。
西森秀稔，大関真之「量子コンピュータが人工知能を加速する」日経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
動画
- NHK Eテレ サイエンスZERO｢量子コンピュータ｣ 2014年9月28日（日）放送
会員登録すると「単品108円」のボタンから108円で視聴できます。番組紹介はこちら。
- TEDxTitech2014
- Google Tech Talk
- AQC2017
