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

要約 解説や動画  量子アニーリングの概要 具体的な定式化 強みと弱み

要 約

  • 量子アニーリングは組み合わせ最適化問題を解くための汎用近似解法である。1998年の門脇と西森の論文において現在広く使われている形で提案・定式化された。

  • 多くの実用的に重要な問題が組み合わせ最適化問題として定式化できるので、その解法の研究は大きな社会的意義を持つ。また、確率分布を生成するサンプリングやある種の量子シミュレーションへの適用の研究も進んでいる。後者の例はこちら

  • D-Wave システムズが量子アニーリングを実現するデバイスを開発し市販している。 Google, NASA, ロッキードマーティン, ロスアラモス国立研究所、ドイツのユーリッヒ研究機構などが実機を導入(あるいは導入契約)した。 また、数多くの企業、大学、研究所がクラウドで使用している。高機能の量子アニーリング装置のプロトタイプを作成する国家プロジェクトがで進行している。

  • 量子アニーリングが最適化問題を通常の(古典)コンピュータより効率よく解けるのかについては、一般論は確立していない。様々な具体例や近似理論などによる研究が進んでいる。D-WaveとGoogleのチームによる最近の論文は、難しいシミュレーションの問題でD-Waveマシンは古典シミュレーションより優れていると主張している。量子アニーリングに関する最近の論文リストはこちらこちらを参照。

  • 極めて大規模なゲート模型の量子コンピュータが出来たとすれば、ある種の問題を通常の(古典)コンピュータより劇的に高速に処理できるようになる。ゲート模型の量子コンピュータは、理論的にはどのような計算でも処理できるという意味で「汎用」とされている。ただし、通常のコンピュータより劇的に速くなる計算課題で実用性を持つものはごく限られている。米国科学アカデミーの報告書「量子コンピュータは、コプロセッサやアクセラレータに似た古典プロセッサを補完する特殊用途デバイスとして設計されている。」と述べている。

解説や動画

量子アニーリングに関する全般的な参考文献や動画を挙げておく。

経産省シンポジウム「次世代コンピュータが実現する革新的ビジネス」基調講演
米国科学・工学・医学アカデミーによる量子コンピュータの進歩と展望 (西森秀稔訳) 共立出版
量子アニーリングの基礎(西森秀稔、大関真之著)共立出版
P. Hauke, H. G. Katzgraber, H. Nishimori, and W. D. Oliver, Rep. Prog. Phys. 83, 054401 (2020).
T. Albash and D. A. Lidar, Rev. Mod. Phys. 90, 015002 (2018)
E. K. Grant and T. S. Humble, Oxford Research Encyclopedia of Physics (2020)
D-WaveのEdward (Denny) Dahl 氏によるウェビナー

量子アニーリングの概要

量子アニーリングは、量子効果を制御して、多変数1価関数(目的関数)の最小値を探す問題(組み合せ最適化問題)を解く手法である。 経路最適化、ポートフォリオ最適化、工場内の装置配置最適化などを始めとする多くの重要な課題が組み合せ最適化問題として定式化できるため、最適化問題の効率的な解法は社会的に大きなインパクトを持つ。また、量子アニーリング装置を量子力学系のシミュレーションに使う動きもある

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



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

具体的な定式化

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

σは2行2列の行列(パウリ行列)である。右辺第1項が通常の古典的イジング模型(最小化するべき目的関数)であり、第2項が量子ゆらぎを引き起こす横磁場項である。この係数Γ(t)を時間t=0で非常に大きい値に設定し、tが増えるとともに0に向けて小さくしていくのである。系全体の状態は、シュレディンガー方程式に従って自然に発展していく。
初期の歴史的経緯
現在広く研究されている意味での量子アニーリングは1998年に提案された[A1]。この論文では、スピングラス問題を中心とするいくつかの典型的な最適化問題に対して、古典的なシミュレーテッドアニーリングより優れていることが数値的に示された。 磁性体での実験や [A2]、大規模な数値計算も続いて行われた [A3]。門脇正史の博士論文も参照のこと[A4]。 離散変数関数の最適化とは違う連続変数の場合の定式化が [A5]で行われた。この論文では虚時間のシュレディンガー方程式方程式が用いられたため、[A6]と同様、本質的に古典アルゴリズムになっている。
2001年には、有限の時間T ですべての過程を終了するタイプのプロセスが提案された[A7]。

論文[A7]では、断熱定理に基づいて基底状態をたどる問題として量子アニーリングが再定式化されて計算量の観点から解析が行われ、量子断熱計算という名前が与えられた。ただし、この論文の最終的な結論(難しい問題での量子断熱計算による指数関数的な高速化)は、現在では、数値計算の規模が小さすぎたため信頼できないとされている[A8]。

[A1] T. Kadowaki and H. Nishimori, Phys. Rev. E58, 5355 (1998) .
[A2] J. Brooke, D. Bitko, T.F. Rosenbaum and G. Aeppli, Science 284, 779 (1999) .
[A3] G. E. Santoro, R. Martonak, E. Tosatti, and R. Car, Science 295, 2427 (2002).
[A4] T. Kadowaki, Thesis, Tokyo Inst. Technology; arXiv:quant-ph/0205020
[A5] A. B. Finnila, M. A. Gomez, C. Sebenik. C. Stenson, and J. D. Doll, Chem. Phys. Lett. 219 (1994) 343.
[A6] B. Apolloni, C. Carvalho, and D. de Falco, Stoc, Proc, Their Appl. 33, 233 (1989); P. Amara, D. Hsu, and J. Straub, J. Phys, Chem. 97, 6715 (1993)
[A7] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292, 472 (2001), arXiv:quant-ph/0007071.
[A8] A.P. Young, S. Knysh, V. Smelyanskiy, Phys. Rev. Lett. 104, 020502 (2010).

量子アニーリングは量子断熱計算にノイズや非断熱遷移を加えたものだと理解している人もいる。上記の論文[A1, A7]をよく読むと、これら2つは本質的な考え方としては同じものだということが分かる。ただ、量子断熱計算では厳密に断熱条件を要求するが量子アニーリングはそうとは限らないという点は異なる。量子アニーリングでは熱その他の原因による環境からの雑音の効果は本質的ではないが、それらを排除しているわけではない。

最適解に近い近似解も含む多数の解を確率的に生成して機械学習に応用する研究[A9]や、量子系のシミュレータとして利用する研究[A10]も始まっている。

[A9] J. Biamonte et al, Nature 549, 195 (2017); V. Dunjko and H. J. Briegel, arXiv:1709.02779
[A10] A. King et al, Nature 560, 456 (2018); R. Harris et al, Science 361, 162 (2018); A. King et al, arXiv:1911.03446.

強みと弱み

量子アニーリングを他の計算手法と比較してみよう。



トップに戻る