量子焼きなまし法

量子焼きなまし法（りょうしやきなましほう、英: quantum annealing、略称: QA、量子アニーリングともいう）は、量子ゆらぎを用いた過程によって、解候補（候補状態）の任意の集合から任意の目的関数の最小値（グローバルミニマム）を探す一般的方法である。

主に探索空間が多くのローカルミニマムを持ち離散的である問題（特に組合せ最適化問題）に対して用いられる（量子トンネリングを使用したスピングラスの基底状態の探索など）^[1]。1994年にJ. D. Dollらによって現在とは別の形式が提案されていたが^[2]、現在の形式は西森秀稔らによって1998年に考案されたものである^[3]。

概説

量子焼きなまし法は、均等な重み付けを持つ全ての可能な状態（候補状態）の量子力学的重ね合わせから開始する。次に、系は物理系の自然な量子力学的発展である時間依存シュレーディンガー方程式に従って変化する。状態間の量子トンネリングを引き起こす横磁場の時間依存強度に応じて、全ての候補状態の振幅は変化し続ける。横磁場の変化速度が十分遅い場合、系は瞬間ハミルトニアンの基底状態の近くにとどまる（断熱量子計算（英語版））^[4]。横磁場は最終的に切られ、系は元々の最適化問題の解に対応する古典的イジング模型の基底状態に到達していることが期待される。

2011年にD-Wave社の世界初の商用量子コンピュータの動作原理としてこの理論が採用されたことで大きな注目を集めることになった^[5]。なお、量子焼きなまし法による量子コンピュータは最適化問題に特化した専用計算機であり、当初から提案されてきた量子ゲート方式による汎用型の量子コンピュータとは異なる。

脚注

[脚注の使い方]

^ P. Ray, B. K. Chakrabarti and A. Chakrabarti, "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations", Phys. Rev. B 39 11828 (1989)
^ A. B. Finilla, M. A. Gomez, C. Sebenik and J. D. Doll, "Quantum annealing: A new method for minimizing multidimensional functions" Chem. Phys. Lett. 219, 343 (1994)
^ T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model" Phys. Rev. E 58, 5355 (1998)
^ E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Ludgren and D. Preda, "A Quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem" Science 292, 472 (2001)
^ M. W. Johnson et al., "Quantum annealing with manufactured spins", Nature 473 194 (2011)

参考文献

G. E. Santoro and E. Tosatti, "Optimization using quantum mechanics: quantum annealing through adiabatic evolution" J. Phys. A 39, R393 (2006).
A. Das and B. K. Chakrabarti, "Colloquium: Quantum annealing and analog quantum computation" Rev. Mod. Phys. 80, 1061 (2008).
S. Suzuki, J.-i. Inoue & B. K. Chakrabarti,"Quantum Ising Phases & Transitions in Transverse Ising Models", Springer, Heidelberg (2013), Chapter 8 on Quantum Annealing.
V. Bapst, L. Foini, F. Krzakala, G. Semerjian and F. Zamponi, "The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective", Physics Reports 523 127 (2013).
Arnab Das and Bikas K Chakrabarti (Eds.), "Quantum Annealing and Related Optimization Methods", Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005).
Anjan K. Chandra, Arnab Das and Bikas K Chakrabarti (Eds.),"Quantum Quenching, Annealing and Computation", Lecture Note in Physics, Vol. 802, Springer, Heidelberg (2010).
A. Ghosh and S. Mukherjee, "Quantum Annealing and Computation: A Brief Documentary Note", arXiv:1310.1339.
西森秀稔、大関真之：「量子アニーリングの基礎」、共立出版、ISBN 978-4320035386（2018年5月23日）。
Shu Tanaka、Ryo Tamura、Bikas K. Chakrabarti：「量子アニーリングの物理」、森北出版、ISBN978-4-627-87191-5（2023年1月）。

外部リンク

大関真之、西森秀稔 (2011). “解説量子アニーリング”. 日本物理學會誌 66 (4): 252-258. NAID 110008593705. http://www-adsys.sys.i.kyoto-u.ac.jp/mohzeki/QA.pdf.
西森秀稔 (東京工業大学)：量子アニーリング
- 量子アニーリング（西森秀稔）

表話編歴量子コンピュータ
全般	量子コンピュータ量子力学
ハードウェア	超伝導イオントラップ型核磁気共鳴光子
アルゴリズム• プログラミング言語	量子プログラミング言語ドイッチュ・ジョサのアルゴリズムグローバーのアルゴリズムショアのアルゴリズム（英語版）
項目	量子ビット量子回路量子テレポーテーション量子暗号量子アニーリング量子状態量子もつれ量子超越性量子ウォーク量子情報
関連分野	量子情報科学情報工学
メーカー	IBM D-Wave Google
実機	九章
人物	ピーター・ショアロブ・グローバー（英語版）デイヴィッド・ドイッチュリチャード・ジョサ（英語版）
カテゴリ

数理最適化 • 最適化問題 : メソッド • ヒューリスティック

非線形(無制約)

… 関数　

黄金分割探索
直線探索
ネルダー–ミード法
連続放物線補間（英語版）

勾配法

収束性	信頼領域ウルフ条件（英語版）
準ニュートン法	BFGS法ブロイデン法 L-BFGS（英語版） DFP法対称ランク1法（英語版）
その他の求解法	ガウス・ニュートン法最急降下法レーベンバーグ・マルカート法共役勾配法（非線形共役勾配法）切り捨てニュートン法（英語版）ドッグレッグ法

… ヘッセ行列

最適化におけるニュートン法（英語版）

非線形(制約付き)

一般	バリア関数ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法逐次二次計画法連続線形計画（英語版）

凸最適化

凸縮小化

切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版）
簡約勾配法
劣勾配法（英語版）

線型および
二次

内点法	カチヤン楕円体法カーマーカーの投影アルゴリズム
ベイズ-交換	単体法改訂シンプレックス法（英語版）十字法（英語版）レムケの主ピボット操作法（英語版）

組合せ最適化

系列範例
(Paradigms)

グラフ理論

最小全域木	ベルマン–フォード法ブルーフカ法ダイクストラ法ワーシャル–フロイド法ジョンソン法（英語版）クラスカル法
最大フロー問題	Dinic法（英語版）エドモンズ・カープフォード・ファルカーソンプッシュリラベル最大流アルゴリズム（英語版）