量子焼きなまし法

ウィキペディア

量子焼きなまし法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/27 21:07 UTC 版)

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

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

概説

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

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

脚注

[脚注の使い方]

1. ^ Ray, P.; Chakrabarti, B. K.; Chakrabarti, Arunava (1989-06). “Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations”. Phys. Rev. B (American Physical Society) 39 (16): 11828-11832. doi:10.1103/PhysRevB.39.11828. https://doi.org/10.1103/PhysRevB.39.11828. 
2. ^ Finnila, Aleta Berk; Gomez, Maria A; Sebenik, C; Stenson, Catherine; Doll, Jimmie D (1994). “Quantum annealing: A new method for minimizing multidimensional functions”. Chemical physics letters (Elsevier) 219 (5-6): 343-348. doi:10.1016/0009-2614(94)00117-0. https://doi.org/10.1016/0009-2614(94)00117-0. 
3. ^ Kadowaki, Tadashi and Nishimori, Hidetoshi (1998). “Quantum annealing in the transverse Ising model”. Physical Review E (APS) 58 (5): 5355. doi:10.1103/PhysRevE.58.5355. https://doi.org/10.1103/PhysRevE.58.5355. 
4. ^ Edward, Farhi; Jeffrey, Goldstone; Sam, Gutmann; Joshua, Lapan;;rew, Lundgren; Daniel, Preda (2001-04). “A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem”. Science (American Association for the Advancement of Science (AAAS)) 292 (5516): 472-475. doi:10.1126/science.1057726. ISSN 0036-8075. https://doi.org/10.1126/science.1057726. 
5. ^ Johnson, Mark W; Amin, Mohammad HS; Gildert, Suzanne; Lanting, Trevor; Hamze, Firas; Dickson, Neil; Harris, Richard; Berkley,;rew J; Johansson, Jan; Bunyk, Paul; others (2011). “Quantum annealing with manufactured spins”. Nature (Nature Publishing Group UK London) 473 (7346): 194-198. doi:10.1038/nature10012. https://doi.org/10.1038/nature10012. 

参考文献

出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 記事の信頼性向上にご協力をお願いいたします。（2025年2月）

• Santoro, Giuseppe E; Tosatti, Erio (2006). “Optimization using quantum mechanics: quantum annealing through adiabatic evolution”. Journal of Physics A: Mathematical and General (IOP Publishing) 39 (36): R393. doi:10.1088/0305-4470/39/36/R01. https://doi.org/10.1088/0305-4470/39/36/R01. 
• Das, Arnab; Chakrabarti, Bikas K (2008). “Colloquium: Quantum annealing and analog quantum computation”. Reviews of Modern Physics (APS) 80 (3): 1061-1081. doi:10.1103/RevModPhys.80.1061. https://doi.org/10.1103/RevModPhys.80.1061. 
• S. Suzuki, J.-i. Inoue & B. K. Chakrabarti,"Quantum Ising Phases & Transitions in Transverse Ising Models", Springer, Heidelberg (2013), Chapter 8 on Quantum Annealing.
• Bapst, Victor; Foini, Laura; Krzakala, Florent; Semerjian, Guilhem; Zamponi, Francesco (2013). “The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective”. Physics Reports (Elsevier) 523 (3): 127-205. doi:10.1016/j.physrep.2012.10.002. https://doi.org/10.1016/j.physrep.2012.10.002. 
• 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).
• Ghosh, Asim; Mukherjee, Sudip (2013). “Quantum annealing and computation: a brief documentary note”. arXiv preprint arXiv:1310.1339. doi:10.48550/arXiv.1310.1339. https://doi.org/10.48550/arXiv.1310.1339. 
• 西森秀稔、大関真之：「量子アニーリングの基礎」、共立出版、ISBN 978-4320035386（2018年5月23日）。
• Shu Tanaka、Ryo Tamura、Bikas K. Chakrabarti：「量子アニーリングの物理」、森北出版、ISBN978-4-627-87191-5（2023年1月）。

関連項目

• D-Wave Systems
• 焼きなまし法（simulated annealing）
• トンネル効果
• 量子コンピュータ

外部リンク

• 大関真之、西森秀稔 (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法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 切断ニュートン法 ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法	Optimization computes maxima and minima.
非線形(制約付き)	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 逐次二次計画法 逐次線形計画法
凸最適化	凸縮小化 切除平面法 簡約勾配法 劣勾配法 線型 および 二次 内点法 アフィンスケーリング法（英語版） カーマーカーの射影変換法 メロートラの予測子修正子法（英語版） 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） ネットワークフロー (最大流問題) Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア