量子アニーリング

横磁場を徐々に弱めながら、系を基底状態へ導く最適化。 Kadowaki と Nishimori が 1998 年に定式化した。

仕組み#

時間依存のハミルトニアンを用意する。

$$H(t)=(1-s(t))H_{\text{初期}}+s(t)H_{\text{問題}},s:0\to 1$$

• $H_{\text{初期}}=-{\sum }_i{\sigma }_i^x$ … 横磁場。基底状態は全スピンの重ね合わせで、簡単に作れる
• $H_{\text{問題}}$ … 解きたいイジング模型

断熱定理により、変化が十分ゆっくりなら系は基底状態に留まり続ける。 終状態を測れば $H_{\text{問題}}$ の基底状態、つまり最適解が得られる。

「十分ゆっくり」がどれくらいか#

必要な時間は、途中で基底状態と第一励起状態のギャップが 最小になる点で決まる。

$$T\sim 𝒪\left(\frac{1}{{\mathrm{\Delta }}_{\min }^2}\right)$$

問題によってはこのギャップが系のサイズに対して指数的に小さくなり、 必要時間も指数的になる。断熱定理は速さを保証しない。

実機の事情#

D-Wave のマシンは有限温度で動作し、コヒーレンス時間も限られる。 理想的な断熱過程ではなく、熱的な緩和が混ざった現象になっている。 また埋め込みにより、 1 つの論理ビットが複数の物理ビットの鎖になるため、 実効的な問題規模はビット数よりずっと小さい。

参考文献#

• Tadashi Kadowaki, Hidetoshi Nishimori. Quantum annealing in the transverse Ising model. Physical Review E 58(5), 1998. https://doi.org/10.1103/PhysRevE.58.5355
• Tameem Albash, Daniel A. Lidar. Adiabatic quantum computation. Reviews of Modern Physics 90(1), 2018. https://doi.org/10.1103/RevModPhys.90.015002
• Philipp Hauke et al. Perspectives of quantum annealing: methods and implementations. Reports on Progress in Physics 83(5), 2020. https://doi.org/10.1088/1361-6633/ab85b8