付録E：量子アニーリングの収束定理 —— 最悪ケースの理論的保証

量子アニーリングは強力な計算手法ですが、問題によっては途中でエネルギーギャップが極端に狭くなり、基底状態から逃げてしまう危険性があります。 では、「絶対に失敗しない」ためには、どれほどゆっくり計算を進めればよいのでしょうか？ Morita と Nishimori (2006) は、統計力学と線形代数の定理を駆使して、この問いに厳密な答えを与えました。

1. 断熱条件の定式化と分子の評価

量子アニーリングのハミルトニアンを とします。 ここで は解きたい問題（イジングモデル）、 は横磁場 、そして は初期値 から へ向かって単調に減少するスケジュール関数です。

第12部で学んだ通り、遷移確率を抑え込むための断熱条件は次の式で表されます。

まず、分子であるハミルトニアンの時間微分を評価します。 は時間に依存しないため、微分が生き残るのは横磁場の項だけです。

は1つのスピンをフリップさせる演算子です。この行列要素の絶対値の和は、スピンの総数 を超えることはありません。したがって、分子は大きくても 程度に抑えられることがわかります（ は減少関数なので微分は負であり、マイナスをつけて正にします）。

2. ホップの定理と最小ギャップの評価

次に、分母であるエネルギーギャップ が「最悪の場合、どれくらい小さくなるか」を評価します。ここで**ホップの定理（Hopf's theorem）**という、要素がすべて正である行列に関する強力な数学的ツールを使用します。

ハミルトニアン を直接扱う代わりに、十分に大きな定数 を用いて という行列を作ります。これにより、行列のすべての要素を正にすることができます。 ホップの定理によれば、この行列の最大要素と最小要素の比 を用いることで、固有値の広がり（つまりエネルギーギャップ）を下からバウンドさせることができます。

• 最大要素の評価: 非対角要素よりも対角要素の方が大きくなるため、 という形で上限が抑えられます。
• 最小要素の評価: これは「すべてのスピン（個）が反転する」遷移に対応し、 に比例します。

ここでスターリングの近似 を適用すると、比 は次のように指数関数的に巨大になることがわかります。

（ は何らかの定数）

ホップの定理が教えるところによれば、エネルギーギャップ はこの巨大な に反比例します（）。したがって、最小ギャップは次のように「指数関数的に小さくなる」ことが導かれます。

3. 究極のスケジュール の導出

分子の上限と、分母（ギャップ）の下限が求まりました。これらを断熱条件の式に代入します。

（ は諸々の定数をまとめたもの）

この不等式を満たすギリギリの境界を求めるため、「」を非常に小さな定数 と置いて、 に関する微分方程式として解きます。

両辺を積分します。

これを について解くと、最終的に量子アニーリングが確実に収束するためのスケジュール関数が得られます。

結論： データサイズ が大きくなると、 という指数はゼロに限りなく近づきます。これは、**「最悪のケースを想定した場合、確実に基底状態を得るためには を驚くほどゆっくり（ほぼ平坦に）変化させなければならない」**ということを意味しています。

計算に必要な全時間は に対して指数関数的に爆発（）してしまいます。 しかし、これはあくまで「どんなに意地悪な問題でも絶対に解ける」という**最悪ケースの保証（理論的上限）**です。現実の問題の多くはここまで悪条件ではなく、付録Dのグローバー探索のように賢いスケジュールを組むことで、指数関数的な時間を回避して高速に最適解を得られるケースが多々存在します。