シミュレーテッドアニーリング

最適化問題を解くための一般的な数値手法。焼きなまし法とも呼ばれる。

コスト関数(エネルギー)が最小となる状態(解、基底状態)を求めるために、コスト関数が一番下がる方向へと状態を更新していくと、局所解にトラップされてしまう。それを避けるためには、コスト関数の値が増える方向への変化も許容するような状態更新を行っていく必要がある。コストが増大するような状態更新を許容する度合をコントロールするパラメータを「温度」と呼び、コスト増に寛容な「高温」から、コスト増を許さない「低温」へと徐々に冷やしていくことで、大域解に到達する手法がシミュレーテッドアニーリングである。

物理的な視点では、熱ゆらぎによって自由エネルギー障壁を乗り越えることで局所安定解を脱出する過程を利用して、熱ゆらぎを徐々に弱くすることで最適化問題を解く手法といえる。量子力学では、絶対零度で熱ゆらぎがなくても、量子ゆらぎによってエネルギー障壁を乗り越えることができる(トンネル効果)が、量子ゆらぎの強さを徐々に弱くしていくことで最適化問題を解くのが量子アニーリングである。

数値的に量子アニーリングをシミュレーションすることもできるが、実際に量子ゆらぎをコントロールすることで、自然に最適化問題を解かせることができるのがアニーリング方式の量子コンピュータである。

関連ソフトウェア