付録D：断熱量子計算とグローバー探索 —— 計算量の劇的な加速

第12部で学んだ「断熱定理」と「エネルギーギャップ」の概念を、具体的なアルゴリズムに応用してみましょう。ここでは、 個のデータから特定の正解を1つだけ探し出す「データベース探索問題」を扱います。 古典コンピュータでは正解を見つけるのに平均して の時間がかかりますが、断熱量子計算の時間進行を工夫することで、これを劇的に加速させることができます。これは Roland と Cerf によって2002年に示されました。

1. ハミルトニアンの設定と2次元部分空間

正解の状態を とします。最終的に到達したいハミルトニアン は、正解状態のエネルギーを 、それ以外を とする と設定します。 一方、初期ハミルトニアン は、すべての状態の均等な重ね合わせ を基底状態とする です。

この系の時間発展は、正解状態 と、それ以外の状態の重ね合わせ が張る「2次元部分空間」の中だけで完全に記述できるという美しい性質を持っています。 全体の進行度合いを としたハミルトニアン は、この基底を用いると次のような 行列として簡潔に表現されます。

2. エネルギーギャップのふるまい

この行列の固有値を計算すると、基底状態と第1励起状態のエネルギー差（ギャップ） は次のように求まります。

この式から、 （アニーリングのちょうど中間地点）のときにギャップが最小になることがわかります。特にデータ数 が極めて大きい場合、中間での最小ギャップは となり、強烈な「疑似交差」が発生します。

3. 断熱条件の厳密な導出：なぜギャップの「2乗」に反比例するのか？

ここで、系が基底状態 から励起状態 へ遷移してしまう確率を、時間依存シュレーディンガー方程式から厳密に見積もってみましょう。 展開係数 の時間発展は、次の方程式で記述されます。

系がほぼ基底状態に留まっていると仮定する（1次近似：）と、励起状態への遷移振幅は次のように積分で書けます。

ハミルトニアンの変化率とエネルギーギャップ が積分区間でほぼ一定（あるいは最悪のケースとして最大値）であると近似して積分の外に出すと、指数関数の積分が実行できます。

この絶対値の2乗をとることで、遷移確率の具体的な上限が得られます。

この結果は極めて重要です。遷移確率は、ハミルトニアンの時間微分の2乗に比例し、エネルギーギャップの4乗に反比例します。 したがって、遷移確率を十分に小さく（）抑え込むための「断熱条件」は、ルートをとって次のように表されます。

つまり、基底状態を保つためには、変化のスピード を**「ギャップの2乗」よりも小さくしなければならない**のです。

4. 局所断熱スケジュール：遅さと速さのメリハリ

もし進行スピード を最初から最後まで「一定」にしてしまうと、最もギャップが狭い の場所で先ほどの断熱条件が破綻し、エラー（励起状態へのジャンプ）が起きてしまいます。これを防ぐために全行程を等速で極端にゆっくり進めると、結果として計算時間が かかってしまい、古典コンピュータに対する優位性が失われます。

そこで Roland と Cerf は、導出した断熱条件を逆手に取り、**「ギャップの大きさに応じて変化のスピード を賢く変える」**という天才的な最適化を行いました。 具体的には、条件式を常に等号ギリギリで満たすように、変化の速度をギャップの2乗 に比例させる（）というルールを課したのです。

この「局所断熱スケジュール」によれば、ギャップが広い序盤と終盤は猛スピードで駆け抜け、ギャップが危険なほど狭くなる の一瞬だけ極端にスピードを落とします。 この微分方程式を積分して全体の計算時間 を求めると、驚くべきことに となります。

これが、時間進行を数学的に最適化することで、断熱量子計算が古典的な の限界を打ち破り、 のスピードアップ（量子ゲート方式におけるグローバーのアルゴリズムと同等の加速）を達成する完璧なメカニズムなのです。