本日、代打で投稿します。
数式は1行しかでてきませんので、気軽に読めます。(物理の素人が書いたので、読み物としてご笑読ください。)
#Simulated Annealing(擬似アニーリング)とは?
探索空間の中から所望のものを発見するするための探索手法です。加熱して柔らかくなった鉄が、冷されるにつれて結晶構造が定まっていく様子に類似していると思う科学者もいます。このことが、焼きなましの英語であるAnnealingになります。
探索アルゴリズムは、広い空間を捜索するエージェントと考えることができます。ある位置から別の位置へと移動しながら、最低の高度の場所を見つけようとします。このようなエージェントのふるまいをランダムプロセスと呼びます。もし、エージェントの記憶能力が悪かったとすると、1単位時刻より過去の記憶については、「どこから跳んできたんだっけ?」と忘れてしまうでしょう。これは、マルコフ鎖と呼ばれている概念です。機械学習をかじったからなら、聞いたことやったことがあるでしょう。では、ある種の探索アルゴリズムは、複数のエージェントを持っているでしょう。そして、エージェント同士で通信をすることもありえます。このような場合、探索アルゴリズムは、ある位置の集合から、別の位置の集合への遷移とみなせます。
温度という考えが出てきます。最初のうちは、エージェントは、活発です。結果として、位置の低い方ではなく、高い方向に行ってしまうことさえあります。これは、最小の高度を見つけるという目的のためには、悪いことじゃないかと思う方もいることでしょう。しかし、高度の高い位置にある谷底に落ち着いてしまうこともあります。機械学習や最適化などで局所的な最小(Local Minima)などと呼ばれている概念です。このような、極小解の谷底に陥らずもっと深い谷底、つまり、高度が低い位置を見つけることができるようになるのです。さて、活発さの度合いを、受理基準と呼ぶことにします。乱数によって決めます。温度スケジュールによって、エージェントの活発さを徐々に低下させていきます。すると、高度の高い方向へと向かう割合が少なくなります。言い換えると受理基準を満たすことは、温度が低下するにつれて困難になります。
#アニーリングのための量子力学(存在することと、認識することの違い)
突然ですが、お昼の時間帯に窓を閉めきった建物の中にいるときに、太陽が存在しないかも?なんて不安になったりしないですよね??が、しかし、物理学者という人たちはそんなこともシリアスに考える人たちなのです。
細かい話はさておき、量子力学では、以下の仮設(議論の前提とし、無条件で成立するとみなす事柄)を2つ置いています。(e.g http://www2.math.kyushu-u.ac.jp/~hara/lectures/09/QM_structure2.pdf 3.5.1)
(仮設1)ミクロな世界でのあるもの(原子など)単体の運動法則は、時間を含む式で記述できるよ(シュレディンガー描像)
(仮設2)「あるものAが存在することをA以外の何か(装置、人)が認識するためには」は「そのものが存在する確率分布」でしか測ることができない。くじ引きをするしかないよ(波束の収縮)。
仮設1では、あるもの(原子など)が存在して運動していたとしても、他の装置や人によって認識されていないということに気をつけましょう。
#量子アニーリング
今までに、考えられた、量子力学の法則を使ったコンピュータの理論(量子チューリング機械、ゲートモデル等)はもっぱら(仮設2)のくじ引きの操作をしやすくするための前処理をどうするか?という点に主眼が置かれていました(Shorの素因数分解アルゴリズムで使用されている、QFTなど)。長所としてどんな関数や手続きも計算できる一方で、物理的な装置として作成するのがとっても困難でした。
これに対して、量子アニーリングでは(仮設1)の時間が経過するに連れてどうなるかという性質に主眼をおいています。
擬似アニーリングを量子力学の法則を使って、拡張したのが量子アニーリングです。
さて、量子アニーリングで最小化される目的関数は以下のような形式です。
H = \frac{t}{T}H_{0}+(1-\frac{t}{T})H_{1}
$H,H_{0},H_{1}$のいずれも物理屋さんが与えた量(ハミルトニアンという名前)だと思って下さい。ただし、実用上の問題をこの量の定義式(省略します)で記述する必要があります。
$H$は、目的関数です。この値を最小化します。
$H_{1}$は擬似アニーリングのエージェントの活発さを量子版で記述するための量です。
$t=0$のとき$H=H_{1}$になります。
$H_{0}$から、求めたい最小値が取り出せます。
$t=T$のとき$H=H_{0}$になります。
といういうわけで、最初($t=0$)は活発な探索を行います。可逆過程と呼ばれる操作をしながら、最終的には($t=T$)求めたい答えを含んだ物理量の最小化という作業を行っていることになります。最初から、$H_{0}$を最小化すればよいのでは?と思う方もいるかもしれません。しかし、それだと局所的最小を避けることができなくなってしまいます。また、$H_{0},H_{1}$の2つの項を含む式は、物理屋さんが「量子ゆらぎ」と呼んでいるもので、量子論の枠組みのなかで、局所的最小解をさけるには$H_{1}$は必要です。
#量子アニーリングは、擬似アニーリングより計算時間が速い??
状況証拠はありますが、確定ではないです。が、物理実験などで、活発に調べられている分野です。
#何が、実際の適用で難しい?
(1)物理屋さんが与えた量ハミルトニアンを使って、実用上の問題をこの量の定義式で記述しないといけない部分
(2)「可逆過程」と呼ばれる操作をしながら、という部分です。理論通りにやろうとすると、計算時間が膨大すぎるので、近似しないといけないです。