断熱量子計算 その1

ちょっと興味が湧いたので、ようやくですが量子アニーリングの基礎を勉強していきたいと思います。今回は理論編。

はじめに&訂正

当初このノートは「量子アニーリングの基礎」と題していたのですが、よくよく考えるに量子アニーリングというよりは断熱量子計算と言ったほうがいい気がしてきました。それに伴って題と内容を一部訂正しました。

資料

西森さんのこちらをベースにします。

断熱量子計算と量子アニーリング

断熱量子計算というのは「計算内容」であり、量子アニーリングというのは「計算方法」です。つまり量子アニーリングという実装により断熱量子計算というアルゴリズムを行うと考えればいいでしょう。その意味では断熱量子計算と対すべきはゲート型量子計算であり、アニーリングと対になるのは分子によるゲート計算やあるいはシミュレータといった具体的な実装です。

断熱量子計算のモチベーション

やりたいことは、任意の相互作用$J_{ij}$に対し

$$ H_0 \equiv - \sum^N_{ij} J_{ij} \sigma^z_i \sigma^z_j $$

なるHamiltonianの基底状態を求めることです。この$H_\0$は一般に$\sigma^z$と可換なので固有状態は$\sigma^z$の固有状態です。つまり、$\sigma^z_i$の固有値$s_i = {1, -1}$ $N$個でラベルされた状態になります。$H_0$の基底状態というのは、言い換えればこの${s_i}$を求めることに相当します。

なんでそんなことをしたいかというと、世の中に存在する多くの最適化問題がこの形に落とせるからです。特に、巡回セールスマン問題がこの形にできますから、この基底状態${s_i}$がわかればNP完全な問題が多項式時間で解けることになります。

量子アニーリングとは

無論、一般の$J_{ij}$に対し、その基底状態をexactに求めるのは不可能です。そこでなんとかしてそれなりに正しそうな答えを得られないかと考えるわけですが、ひとつのやり方は焼きなまし法です。すなわち、もはや$\sigma^z_i$を${1, -1}$のどちらかの値しか取らないbitだと思い、系を熱浴に入れます。熱浴の温度を$0$に近づければ徐々に系の状態はその基底状態に近づきます。こうして${s_i}$を求めるというわけです。

これとは全く独立な方法が断熱量子計算とそれを実現するための量子アニーリングです。アニーリングと言っていますが温度は本質的には関係ありません。むしろ、量子力学のいわゆる断熱過程に相当する操作を行います。すなわち、簡単な(基底状態が自明な)Hamiltonian $H_1$を用意し、

$$ H(t) \equiv H_0 + \Gamma(t) H_1 $$

とします。ただし$\Gamma(t)$は時間に依存する無次元の$C$数(演算子ではないただの数)で、$t=0$で十分大きいものとします。そして、時刻$T$で$\Gamma(T)\ll 1$を満たすようにしておきます。

すると、この過程は断熱過程となり、$t=0$で基底状態から始めれば$t=T$でも基底状態にとどまっていることになります。これを量子アニーリングと呼ぶのですね。

$H_1$に関しては$H_0$と可換なものをとってきてもHilbert空間が当然直積になってしまうだけなので、非可換なものをとってきます。具体的には

$$ H_1 \equiv \sum \sigma^x_i $$

とかするとよいです。これが「横磁場イジング」の名前の由来で、また「量子性」と言っているのはこの非可換性のことにほかなりません。(例えばベルの不等式とかの「量子性」も究極的にはこの非可換性に由来していると思えます。非局所性が量子論の本質なのだー的言説にぼくも一時期影響されていましたが、まあなんのことはない話でした。というか本質厨は怖いですねぇ…。宗教家みたいです。反省。)

実際どうやるか

実際にはHamiltonianを

$$ H(t) \equiv \frac tT H_0 + \left( 1 - \frac tT \right) H_1 $$

だと思って、「ゆっくりさ」は$T$の大きさでコントロールすると思ったほうが実応用上も単純かと思われます。元資料の4章の収束条件のところは、そもそも$\Gamma(0)$も対応する古典アニーリングの温度$T(0)$もどちらも$\mathcal O(N^2)$でないと十分大きいとみなせないので、時刻$0$でどちらもなんか小さいのはまあ間違いというか、結局でも漸近的な振る舞いだけでいいので間違いとまでは言えませんが、ただちょっとミスリーディングな書き方なんだと思います。

(しかしそうするとこれとかinitialで$\Gamma=\mathcal O(1)$においてるけどだいじょぶなんだろーか)

次回、実装の理論編?

Comments

comments powered by Disqus