補遺: QAの収束定理

量子アニーリングは、初期ハミルトニアンの簡単な基底状態から出発し、解きたい問題のハミルトニアンへゆっくり変えていく方法です。直観としては分かりやすいです。しかし、どれくらいゆっくりなら本当に基底状態へ到達できるのでしょうか。

この問いに答えるのがQAの収束定理です。ここでは、有限サイズのIsing型最適化問題に対して、横磁場をどの程度ゆっくり下げれば、実時間Schrodinger方程式に従う量子系が瞬間基底状態に追随できるかを見ます。最後に、補遺: シミュレーテッドアニーリングで扱ったSomma--Batista--Ortiz型の古典-量子対応と、同じ計算の骨格を共有していることも確認します。

GA・SA・QAとHopfの収束評価では、独立突然変異を持つ集団更新を正の行列として扱い、スペクトル評価の共通点と、最適解への収束証明の違いを比較します。

1. 横磁場Ising型のQA

最適化問題を対角ハミルトニアン

$${\hat{H}}_0=-\sum _i{h}_i{\hat{\sigma }}_i^z-\sum _{ij}{J}_{ij}{\hat{\sigma }}_i^z{\hat{\sigma }}_j^z-\sum _{ijk}{J}_{ijk}{\hat{\sigma }}_i^z{\hat{\sigma }}_j^z{\hat{\sigma }}_k^z-\cdots$$

として表します。基底状態が最適解です。横磁場を

$${\hat{H}}_1=-\sum _{i=1}^N{\hat{\sigma }}_i^x$$

とし、全ハミルトニアンを

$$\hat{H}(t)={\hat{H}}_0+\mathrm{\Gamma }(t){\hat{H}}_1$$

とします。$\mathrm{\Gamma }(t)$ は単調減少し、$t\to \mathrm{\infty }$ で0へ向かいます。初期には $\mathrm{\Gamma }$ が大きく、横磁場の基底状態、つまり計算基底の一様重ね合わせに近い状態から出発します。最後には ${\hat{H}}_0$ だけが残ります。

状態は実時間Schrodinger方程式

$$i\hslash \frac{d}{dt}|\psi (t)⟩=\hat{H}(t)|\psi (t)⟩$$

に従います。

2. 断熱条件

瞬間固有状態を

$$\hat{H}(t)|n(t)⟩=E_n(t)|n(t)⟩$$

とします。初期状態が基底状態 $|0(0)⟩$ で、ハミルトニアンの変化が十分遅ければ、状態は各時刻の基底状態 $|0(t)⟩$ に近いまま動きます。

非断熱遷移を抑える十分条件は、概略

$$\frac{|⟨n(t)|\dot{\hat{H}}(t)|0(t)⟩|}{{(E_n(t)-E_0(t))}^2}\ll 1(n\ne 0)$$

です。ここでも、分子はハミルトニアンを動かす速さ、分母はギャップの二乗です。

この模型では時間依存性は $\mathrm{\Gamma }(t)$ だけにあるので、

$$\dot{\hat{H}}(t)=\dot{\mathrm{\Gamma }}(t){\hat{H}}_1=-\dot{\mathrm{\Gamma }}(t)\sum _i{\hat{\sigma }}_i^x$$

です。各Pauli行列の演算子ノルムは1なので、

$$|⟨n(t)|\dot{\hat{H}}(t)|0(t)⟩|\le N|\dot{\mathrm{\Gamma }}(t)|$$

と評価できます。

3. ギャップの下限

難しいのは分母です。一般の最適化問題でエネルギーギャップ

$${\mathrm{\Delta }}_n(t)=E_n(t)-E_0(t)$$

を正確に求めるのは、ほとんど元の問題を解くことに近いです。そこで、厳密値ではなく下限を使います。

有限サイズの横磁場Ising系では、横磁場が小さい漸近領域で

$${\mathrm{\Delta }}_n(t)\ge A\mathrm{\Gamma }(t{)}^N$$

という形の下限を得ます。$A>0$ は問題のエネルギー幅やサイズに依存する定数です。直観的には、任意の計算基底状態から別の状態へ移るには、最大で $N$ 個のスピン反転を通ればよいです。横磁場は一度に一つのスピンを反転するので、最小のつながりは ${\mathrm{\Gamma }}^N$ の次数で現れます。

この評価は非常に悲観的です。実際の問題のギャップはもっと大きいかもしれません。しかし、どんな有限サイズ問題でも使える保証としては強い意味を持ちます。

4. スケジュールを解く

断熱条件の左辺を、上の評価で抑えると

$$\frac{N|\dot{\mathrm{\Gamma }}(t)|}{A^2\mathrm{\Gamma }(t{)}^{2N}}\ll 1$$

となります。十分条件として

$$\frac{N|\dot{\mathrm{\Gamma }}(t)|}{A^2\mathrm{\Gamma }(t{)}^{2N}}=\delta$$

と置き、$\delta$ を小さな正定数にします。$\mathrm{\Gamma }(t)$ は減少するので、

$$-\frac{d\mathrm{\Gamma }}{dt}=\frac{\delta A^2}{N}{\mathrm{\Gamma }}^{2N}$$

です。分離して積分すると、

$$\int {\mathrm{\Gamma }}^{-2N}d\mathrm{\Gamma }=-\frac{\delta A^2}{N}\int dt$$

ですから、

$$\frac{1}{2N-1}\mathrm{\Gamma }(t{)}^{-(2N-1)}=\frac{\delta A^2}{N}t+C$$

を得ます。したがって

$$\mathrm{\Gamma }(t)={[(2N-1)(\frac{\delta A^2}{N}t+C)]}^{-1/(2N-1)}$$

です。大きな時刻では

$$\mathrm{\Gamma }(t)\sim t^{-1/(2N-1)}$$

のように、べきでゆっくり減衰させればよい、という条件になります。

コラム 2024大学院講義 第11回 0:57:00-1:06:00

横磁場スケジュールを微分方程式として解く

断熱条件は、見方を変えるとスケジュール $\Gamma(t)$ に対する微分方程式です。分子に $|\dot\Gamma|$、分母にギャップの二乗が出るので、ギャップ下限を入れると、あとは分離変数で積分できます。

講義の面白さは、抽象的な収束定理が最後に「この形で横磁場を落とせばよい」という具体的な関数へ着地するところです。証明の細部は高度でも、最後の足取りは微分方程式として手で追えます。

5. 何を保証しているか

この結果は、有限サイズの系で、十分遅い漸近スケジュールを取れば、量子状態が瞬間基底状態から大きく外れず、最終的に ${\hat{H}}_0$ の基底状態へ近づくことを保証します。

ただし、これは高速性を保証する定理ではありません。$N$ が大きいと指数 $1/(2N-1)$ は非常に小さく、$\mathrm{\Gamma }(t)$ を下げるには膨大な時間が必要です。実用上は、問題構造を使った速いスケジュール、局所断熱条件、反断熱項、ヒューリスティックなチューニングが重要になります。

それでもこの定理は大切です。量子アニーリングが単なる経験則ではなく、少なくとも理想的なSchrodingerダイナミクスの下では、収束を議論できる数学的な足場を持つことを示しているからです。

コラム 2024大学院講義 第11回 1:05:00-1:15:00

理想論と実機の短い時間窓

収束定理は理想的な孤立量子系の話です。実機では、熱環境、ノイズ、制御誤差、コヒーレンス時間が効きます。講義では、ゆっくりすれば断熱性は良くなる一方で、長く動かすほど環境の影響を受けるという、実機ならではの緊張関係が語られました。

だからこそ、短い時間でSchrodinger方程式に近い振る舞いを観測できる領域は貴重です。量子アニーリングマシンは、最適化装置であると同時に、多数の量子ビットを持つ量子多体系シミュレーターでもあります。

6. 横磁場の減衰条件と基底状態への収束

この収束定理の核心は、「任意の有限サイズ問題で、横磁場を十分ゆっくり弱めれば、基底状態へ追随できる」という保証です。講義では、研究の現場でこの問題がどう持ち上がり、どのように断熱定理とギャップ評価へ落とされたかも語られました。

コラム 2024大学院講義 第10回 1:09:00-1:22:00

森田・西森の定理が講義に出ること

講義では、森田・西森の収束定理が、単なる定理名ではなく、研究室の時間感覚を伴って語られました。若い研究者が短い周期で結果を出し、周囲がそれに刺激を受けます。その空気ごと残ると、定理が教科書の外側で生きていたことが分かります。

数学的には、断熱条件、横磁場Ising模型、Perron--Frobenius型の固有値評価が組み合わさります。物語としては、シミュレーテッドアニーリングのGeman--Geman定理に対応する、量子アニーリング側の保証を探す試みです。

7. 古典平衡分布と量子基底状態の対応

シミュレーテッドアニーリングの補遺では、古典Markov連鎖の平衡分布

$${\pi }_{\beta }(\sigma )=\frac{e^{-\beta E(\sigma )}}{Z_{\beta }}$$

を、平方根振幅を持つ量子状態

$$|{\mathrm{\Psi }}_{\beta }⟩=\sum _{\sigma }\sqrt{{\pi }_{\beta }(\sigma )}|\sigma ⟩$$

へ写しました。この写像では、詳細釣り合いを満たすMarkov生成行列が、適切な相似変換によってHermitianなハミルトニアンとして読めます。該当する計算は、補遺: シミュレーテッドアニーリングの式 (84)付近に置いてあります。

この古典-量子対応では、SAの温度 $\beta (t)$ を変えることが、量子ハミルトニアンの基底状態を動かすことに対応します。すると、平衡分布を追いかける古典Markov連鎖の条件が、量子断熱定理の条件として再解釈されます。Geman--Geman型の対数冷却条件は、式 (90)の形で現れます。

QAの収束定理では、温度ではなく横磁場 $\mathrm{\Gamma }(t)$ を動かします。しかし、議論の構造は似ています。

$$\text{動く標的を追う速さ}\lesssim \text{ギャップまたは緩和率}$$

SAでは、低温でMarkov連鎖の緩和が遅くなります。QAでは、横磁場が小さくなるとギャップ下限が小さくなります。どちらも、標的を急に動かすと追随できない、という同じ数理を持っています。

8. 収束定理をどう読むか

この定理を読むとき、二つの感想を同時に持つのが健全です。

一つ目は、理論的な安心です。量子アニーリングは、有限サイズの理想系では収束保証を持ちます。横磁場をただの雰囲気で入れているわけではなく、断熱定理の言葉で追随条件を評価できます。

二つ目は、実用上の厳しさです。一般保証として得られるスケジュールは遅く、実機では有限時間・ノイズ・開放系効果があります。だから、現実の研究では、問題構造を使ったギャップ評価、局所スケジュール、短時間量子ダイナミクス、反断熱項、ハイブリッドアルゴリズムが重要になります。

Grover探索で $O(\sqrt{N})$ が出るのは、ギャップが具体的に分かるからです。SAで対数冷却が出るのは、低温での緩和の遅さを安全側に見積もるからです。QAの収束定理でべき減衰の $\mathrm{\Gamma }(t)$ が出るのは、横磁場が作るギャップを安全側に押さえるからです。これらは別々の話ではなく、「動く基底状態、あるいは動く平衡分布を、遅れず追う」という一つの話です。

PDF画像では、大学院講義2024板書 p.34以降で断熱条件と収束定理の計算を確認できます。参考文献: [1], [2], [3]。

参考文献

1. Satoshi Morita, Hidetoshi Nishimori, “Convergence theorems for quantum annealing,” Journal of Physics A: Mathematical and General 39, 13903–13920 (2006). 出典

2. Satoshi Morita, Hidetoshi Nishimori, “Convergence of Quantum Annealing with Real-Time Schrödinger Dynamics,” Journal of the Physical Society of Japan 76, 064002 (2007). 出典

3. Satoshi Morita, Hidetoshi Nishimori, “Mathematical foundation of quantum annealing,” Journal of Mathematical Physics 49, 125210 (2008). 出典