組み合わせ最適化問題と量子アニーリング : 量子断熱発展の理論と性能評価

Abstract

組み合わせ最適化問題に物理的な過程を応用する方法がある。中でもシミュレーティッドアニーリングはよく知られている。シミュレーティッドアニーリングは熱揺らぎを制御して最適化問題の答えを導く。まず組み合わせ最適化問題を表すハミルトニアンを作り、それに相当する仮想的な物理系の高温の平衡状態を作る。温度が十分に高ければ平衡状態は容易に得られる。そこから系を徐々に冷却し、それに伴う系の緩和を通じて最後にハミルトニアンの基底状態に到達させる。比較的最近、シミュレーティッドアニーリングの類推として量子アニーリングが提案された。この方法は磁場などにより系にトンネル効果(運動エネルギー)を導入し、それを制御することで最適化問題を解く。どのように制御するかというと、まず運動エネルギーがハミルトニアンの中で支配的になるようにし、そこから時間とともに徐々に運動エネルギーの重みが小さくなるようにする。運動エネルギーが支配的な初期ハミルトニアンの基底状態は簡単にわかる。その状態を初期状態として状態を時間発展させ、運動エネルギーの重みが無くなった時点での状態を答えとする。状態が断熱的に発展すれば、終状態は古典ハミルトニアンの基底状態となる。これら二つの方法は基本的にどんな問題にも使える汎用的なものである。最近の研究の進展によって量子アニーリングの性質が徐々に明らかになってきている。注目すべきは古典的なシミュレーティッドアニーリングよりも量子力学的な量子アニーリングの方が終状態を早く基底状態に近づけることである。このことは現時点で一般的に証明されたわけではないが、数値的な状況証拠に加え、解析的な証拠も得られている。本論文ではまずシミュレーティッドアニーリングと量子アニーリングの方法について述べる。次に量子アニーリングの本質である量子状態の断熱発展に関する基礎理論をまとめる。後半では量子力学の断熱定理に基づいて有限系で一般的に成り立つ量子アニーリング後の残留エネルギーの減少則を導く。さらに1次元ランダムイジング模型を例題として、熱力学極限で量子アニーリングとシミュレーティッドアニーリングのダイナミクスを解析的に比較する。それによって量子アニーリングがシミュレーティッドアニーリングより早いことに対する解析的な証拠を与える。