補遺: リバースアニーリング

通常の量子アニーリングでは、最初に強い横磁場をかけ、すべての古典配置を重ね合わせた簡単な基底状態から出発します。そこから横磁場を弱め、目的ハミルトニアンの基底状態へ近づけます。リバースアニーリングは、この向きを少しひねります。すでに手元にある古典的な候補解から始め、その近傍だけを量子ゆらぎで掘り直し、最後にまた古典状態として読み出します。

直観的には、広い野原を最初から全部探すのではなく、「このあたりが怪しい」と分かっている場所の周辺を掘る方法です。ただし、この直観だけでは危ないです。候補解がどれだけ真の解に近いか、途中で横磁場をどこまで戻すか、自由エネルギー地形の谷がどう変わるかを見ないと、うまくいく条件は分かりません。そこで、p-spin模型の平均場解析が役に立ちます。

1. 何を逆にするのか

通常の横磁場量子アニーリングは

$$\hat{H}(s)=s{\hat{H}}_0+(1-s){\hat{V}}_{\mathrm{T}\mathrm{F}},{\hat{V}}_{\mathrm{T}\mathrm{F}}=-\sum _i{\hat{\sigma }}_i^x$$

です。$s=0$ では横磁場だけ、$s=1$ では目的ハミルトニアン ${\hat{H}}_0$ だけになります。

リバースアニーリングでは、最初の古典候補解をハミルトニアンとして入れます。候補解を

$$\mathit{ϵ}=({ϵ}_1,\dots ,{ϵ}_N),{ϵ}_i=\pm 1$$

とし、この状態を基底状態に持つ初期ハミルトニアンを

$${\hat{H}}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}=-\sum _{i=1}^N{ϵ}_i{\hat{\sigma }}_i^z$$

と置きます。${ϵ}_i$ と同じ向きに ${\sigma }_i^z$ がそろうほどエネルギーが下がるので、$\mathit{ϵ}$ が初期状態として選ばれます。

adiabatic reverse annealingを平均場解析で書くと、典型的には

$$\hat{H}(s,\lambda )=s{\hat{H}}_0+(1-s)(1-\lambda ){\hat{H}}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}+(1-s)\lambda {\hat{V}}_{\mathrm{T}\mathrm{F}},0\le s,\lambda \le 1$$

です。$\lambda$ は、初期候補をどれだけ信じ、横磁場をどれだけ入れるかを決めるパラメータです。$\lambda =1$ なら初期ハミルトニアンが消え、通常の量子アニーリングになります。$\lambda =0$ では横磁場がなく、候補解を固定する縦方向のバイアスが残ります。最終的に $s=\lambda =1$ へ行けば、目的ハミルトニアンだけが残ります。

実機でしばしば使われる操作は、古典状態から始めてアニーリングパラメータをいったん戻し、途中で止め、また進めるという局所探索です。これは候補解を初期条件として入れる iterated reverse annealing と呼ばれることがあります。一方、式 (eq-ra-004) のように初期ハミルトニアンをハミルトニアンの一部として明示的に入れるものを adiabatic reverse annealing と呼ぶと、平均場解析がかなり見通しよくなります。

2. p-spin模型で候補解の近さを見る

目的ハミルトニアンを、講義本文で使った強磁性p-spin模型にします。

$${\hat{H}}_0=-N{\left(\frac{1}{N}\sum _i{\hat{\sigma }}_i^z\right)}^p$$

奇数の $p$ を考えると、基底状態は全スピンが上向きの状態です。初期候補解 $\mathit{ϵ}$ がこの正解にどれだけ近いかを、上向きスピンの割合

$$c=\frac{1}{N}\sum _{i=1}^N{\delta }_{{ϵ}_i,1}$$

で表します。$c=1$ なら正解そのもの、$c=1/2$ ならランダムな候補と同じ程度です。

Suzuki--Trotter分解を行い、各スライスに磁化

$$m_t=\frac{1}{N}\sum _i{\sigma }_{i,t}^z$$

を入れます。デルタ関数の挿入は

$$1=\int d{m}_{t}d{\tilde{m}}_t\exp [-{\tilde{m}}_t(N{m}_t-\sum _i{\sigma }_{i,t}^z)]$$

です。これにより、$N{m}_t^p$ の全結合相互作用は補助場を通して一スピン問題に分かれます。静的近似 $m_t\to m$ を置くと、一スピンが見る縦方向の有効場は

$$A_i=sp{m}^{p-1}+(1-s)(1-\lambda ){ϵ}_i$$

です。有限温度の自由エネルギーは

$$f(\beta ,s,\lambda ;m)=s(p-1)m^p-\frac{1}{\beta }{[\log 2\cosh \beta \sqrt{A_i^2+(1-s{)}^2{\lambda }^2}]}_i$$

となります。角括弧 $[\cdots {]}_i$ は、初期候補に含まれるサイトの平均です。$cN$ 個のサイトでは ${ϵ}_i=1$、$(1-c)N$ 個のサイトでは ${ϵ}_i=-1$ なので、零温極限では

$$\begin{array}{rl}f(s,\lambda ;m)& =s(p-1)m^p\\ & -c\sqrt{\{sp{m}^{p-1}+(1-s)(1-\lambda ){\}}^2+(1-s{)}^2{\lambda }^2}\\ & -(1-c)\sqrt{\{sp{m}^{p-1}-(1-s)(1-\lambda ){\}}^2+(1-s{)}^2{\lambda }^2}\end{array}$$

です。対応する鞍点方程式は

$$\begin{array}{rl}m& =c\frac{sp{m}^{p-1}+(1-s)(1-\lambda )}{\sqrt{\{sp{m}^{p-1}+(1-s)(1-\lambda ){\}}^2+(1-s{)}^2{\lambda }^2}}\\ & +(1-c)\frac{sp{m}^{p-1}-(1-s)(1-\lambda )}{\sqrt{\{sp{m}^{p-1}-(1-s)(1-\lambda ){\}}^2+(1-s{)}^2{\lambda }^2}}\end{array}$$

になります。

この式の読み方は、かなり気持ちがよいです。$sp{m}^{p-1}$ は目的ハミルトニアンから来る自己無撞着な強磁性場です。$(1-s)(1-\lambda ){ϵ}_i$ は、初期候補解が各サイトへ与える縦方向の助言です。$(1-s)\lambda$ は横磁場です。正しい向きの助言を受けたサイトと、間違った向きの助言を受けたサイトが、それぞれ一スピン問題として足し合わされています。

通常の量子アニーリング、つまり $\lambda =1$ では、候補解の情報は消えます。このときp-spin模型は $p\ge 3$ で一次相転移を持ちます。ところが $c$ が十分大きく、候補解が正解に近いと、$(1-s)(1-\lambda ){ϵ}_i$ が自由エネルギー地形を傾け、一次転移線に切れ目ができます。その切れ目を通る経路を選ぶと、量子常磁性相から強磁性相へ、不連続なジャンプを横切らずに進めます。

候補解がそこまで良くない場合でも、意味がなくなるわけではありません。一次転移で二つの局所最小が残っていても、その間の磁化のジャンプ

$$\mathrm{\Delta }m=|m_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}-m_{\mathrm{l}\mathrm{o}\mathrm{w}}|$$

が小さくなる場合があります。自由エネルギーの二つの谷の距離が小さくなれば、トンネルの壁は薄くなります。断熱定理だけでなく、有限時間の量子ダイナミクスを考えると、この「壁を薄くする」効果は重要です。

3. ランダム場がある場合

実際の推定問題や最適化問題では、全サイトが完全に同じではありません。そこで、目的ハミルトニアンに縦方向のランダム場を入れた

$${\hat{H}}_0=-N{\left(\frac{1}{N}\sum _i{\hat{\sigma }}_i^z\right)}^p-\sum _i{h}_i{\hat{\sigma }}_i^z$$

も考えます。このとき一スピンが感じる縦場は

$$h_{\mathrm{e}\mathrm{f}\mathrm{f}}(h_i,{ϵ}_i)=sp{m}^{p-1}+s{h}_i+(1-s)(1-\lambda ){ϵ}_i$$

となり、零温の自由エネルギーは

$$f(s,\lambda ;m)=s(p-1)m^p-{\left[\sqrt{h_{\mathrm{e}\mathrm{f}\mathrm{f}}(h_i,{ϵ}_i{)}^2+(1-s{)}^2{\lambda }^2}\right]}_{h,ϵ}$$

です。ランダム場が二値分布なら平均は有限個の和になり、ガウス分布なら積分になります。式の形は変わりません。違いは、局所場 $h_i$ が自由エネルギーの谷を場所ごとに少しずつ傾けることです。

Ohkuwa--Nishimori--Lidarの解析では、ランダム場を入れても、候補解が十分近ければ一次転移線に切れ目ができること、切れ目ができない場合にも $\mathrm{\Delta }m$ が小さくなり得ることが示されます。つまりリバースアニーリングの肝は、単に「逆向きに動かす」ことではありません。初期情報をハミルトニアンの中へ入れ、自由エネルギー地形の谷の配置そのものを変えることにあります。

4. non-stoquastic項と組み合わせる

反強磁性XX項を加えたリバースアニーリングも、同じ表記で書けます。たとえば

$$\hat{H}(s,\lambda ,\nu )=s\nu {\hat{H}}_0+(1-s)(1-\lambda ){\hat{H}}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}+(1-s)\lambda {\hat{V}}_{\mathrm{T}\mathrm{F}}+s(1-\nu ){\hat{V}}_{\mathrm{X}\mathrm{X}}$$

とします。$\nu$ が小さいほど、反強磁性XX項の割合が大きくなります。縦磁化 $m^z$ と横磁化 $m^x$ を置くと、有効場は

$$\begin{array}{rl}{h}_z(h_i,{ϵ}_i)& =ps\nu (m^z{)}^{p-1}+s\nu h_i+(1-s)(1-\lambda ){ϵ}_i,\\ h_x& =(1-s)\lambda -2s(1-\nu )m^x\end{array}$$

となります。零温の自由エネルギーは

$$\begin{array}{rl}f& =s\nu (p-1)(m^z{)}^p-s(1-\nu )(m^x{)}^2\\ & -{\left[\sqrt{h_z(h_i,{ϵ}_i{)}^2+h_x^2}\right]}_{h,ϵ}\end{array}$$

と書けます。ここでも、反強磁性XX項は横方向の有効場を $h_x=(1-s)\lambda -2s(1-\nu )m^x$ へ変えます。初期候補の縦方向バイアスと、non-stoquasticな横方向バイアスが、別々の方向から自由エネルギー地形を変えるわけです。

ただし、二つの工夫を足せば必ず良くなる、という話ではありません。反強磁性XX項だけですでに一次転移が二次転移へ変わる領域では、リバースアニーリングの役割は小さくなることがあります。逆に、non-stoquastic性が強すぎると、リバースアニーリングで開くはずの切れ目の位置が変わり、通常の量子アニーリングの方が自然な経路になる場合もあります。ここでも判断基準は、相図と自由エネルギーの谷です。

5. 動力学で見るリバースアニーリング

平均場の自由エネルギーは、平衡状態の地図です。では、実際に時間発展させたときにもその地図どおりに動くのでしょうか。Yamashiro--Ohkuwa--Nishimori--Lidarは、全結合p-spin模型についてユニタリ時間発展を数値的に解き、平衡統計力学の予測と動力学を比較しました。

ここで重要になる区別は、adiabatic reverse annealing と iterated reverse annealing です。前者は式 (eq-ra-004) のように初期ハミルトニアンを入れ、断熱経路として設計します。後者は、古典候補状態を初期条件として用意し、D-Wave型のスケジュールで戻して進める局所探索に近いです。p-spin模型では、断熱的に設計したリバースアニーリングでは指数的な改善を示す平衡解析と整合する一方、単純なiterated reverse annealingは同じ模型では効きにくいことが報告されています。

この差は、実機でのリバースアニーリングを読むときにも大切です。実機の操作は、断熱定理のきれいな理想形だけで動いているわけではありません。熱浴、緩和、ポーズ、読み出し、制御誤差が入ります。だからこそ、平衡相図で「なぜ効く可能性があるか」を見てから、動力学で「どこまで実際に効くか」を見る必要があります。

6. CDMA多ユーザ検出への応用

リバースアニーリングの見方は、推定問題にも使えます。Arai--Ohzeki--Tanakaが扱ったCDMA多ユーザ検出では、送信された二値信号 $\mathit{\xi }$ を、拡散符号 ${\eta }_i^{\mu }$ と受信信号 $\mathit{y}$ から推定します。受信信号を

$$y^{\mu }=\frac{1}{\sqrt{N}}\sum _{i=1}^N{\eta }_i^{\mu }{\xi }_i+{\omega }^{\mu }$$

と書くと、${\omega }^{\mu }$ は通信路のノイズです。推定したい信号を $\mathit{\sigma }$ とすると、尤度は

$$P(\mathit{y}\mid \mathit{\sigma })\propto \exp [-\frac{\beta }{2}{\Vert \mathit{y}-\frac{\eta \mathit{\sigma }}{\sqrt{N}}\Vert }^2]$$

です。したがって事後分布はGibbs分布として読めます。

$$P(\mathit{\sigma }\mid \mathit{y})=\frac{1}{Z}\exp [-\beta H(\mathit{\sigma })]$$

対応する古典ハミルトニアンは

$$H(\mathit{\sigma })=\frac{1}{2N}\sum _{i,j}\sum _{\mu =1}^K{\eta }_i^{\mu }{\eta }_j^{\mu }{\sigma }_i{\sigma }_j-\frac{1}{\sqrt{N}}\sum _i\sum _{\mu =1}^K{\eta }_i^{\mu }{y}^{\mu }{\sigma }_i$$

です。これはランダムな二体相互作用とランダム場を持つIsing模型です。推定問題の難しさが、スピングラス的な自由エネルギー地形として現れます。

量子ゆらぎを入れると

$$\hat{H}=s{\hat{H}}_0+(1-s){\hat{H}}_{\mathrm{T}\mathrm{F}},{\hat{H}}_{\mathrm{T}\mathrm{F}}=-\sum _i{\hat{\sigma }}_i^x$$

です。リバースアニーリングでは、初期候補 ${\tau }_i$ を

$${\hat{H}}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}=-\sum _i{\tau }_i{\hat{\sigma }}_i^z$$

として加えます。

$$\hat{H}=s{\hat{H}}_0+(1-s)(1-\lambda ){\hat{H}}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}+(1-s)\lambda {\hat{H}}_{\mathrm{T}\mathrm{F}}$$

初期候補が真の信号と一致する割合を

$$c=\frac{1}{N}\sum _i{\delta }_{{\tau }_i,{\xi }_i}$$

で表します。p-spin模型の $c$ と同じ役割です。ただし、CDMAでは ${\tau }_i$ がどの情報から作られたかが非常に重要になります。

レプリカ法では、信号との重なり

$$m_a(t)=\frac{1}{N}\sum _i{\xi }_i{\sigma }_{ia}(t)$$

レプリカ間の重なり

$$q_{ab}(t,t^{\prime })=\frac{1}{N}\sum _i{\sigma }_{ia}(t){\sigma }_{ib}(t^{\prime })(a\ne b)$$

同一レプリカ内のTrotter相関

$$R_a(t,t^{\prime })=\frac{1}{N}\sum _i{\sigma }_{ia}(t){\sigma }_{ia}(t^{\prime })$$

を入れ、デルタ関数とフーリエ積分表示で制約します。レプリカ対称性と静的近似を置くと

$$m_a(t)=m,q_{ab}(t,t^{\prime })=q,R_a(t,t^{\prime })=R$$

となり、自由エネルギー密度は、秩序変数と共役変数に関する鞍点問題として書けます。変数の集合を

$$\mathcal{X}=(m,q,R,\tilde{m},\tilde{q},\tilde{R}),-\beta f_{\mathrm{R}\mathrm{S}}=\underset{\mathcal{X}}{\mathrm{extr}}\mathrm{\Phi }(\mathcal{X})$$

と置くと、汎関数 $\mathrm{\Phi }$ は

$$\begin{array}{rl}\mathrm{\Phi }(\mathcal{X})& =[\frac{\alpha }{2}\{-\log [1+\beta s(R-q)]\\ & +\beta s(R-1+\frac{1+{\beta }_0}{{\beta }_0}+\frac{2m-q-(1+{\beta }_0^{-1})}{1+\beta s(R-q)})\}\\ & -m\tilde{m}-R\tilde{R}+\frac{1}{2}q\tilde{q}\\ & +\sum _{a=\pm 1}{c}_a\int Dz\log \int Dy2\cosh \sqrt{g_a^2+[\beta (1-s)\lambda {]}^2}]\end{array}$$

ここで

$$g_a=\tilde{m}+a\beta (1-\lambda )(1-s)+\sqrt{\tilde{q}}z+\sqrt{2\tilde{R}-\tilde{q}}y,c_{+}=c,c_{-}=1-c$$

です。$\alpha =K/N$ は測定数とユーザ数の比で、${\beta }_0$ は真のノイズ強度を表します。式は長いですが、構造はp-spinの式と同じです。初期候補は $a=\pm 1$ の二つのグループとして入り、横磁場は $\beta (1-s)\lambda$ として入ります。乱れの平均は $Dz,Dy$ のガウス積分へ押し込まれます。

この解析から分かることは、かなり繊細です。初期候補が「真の信号に対して独立に、割合 $c$ だけ正しい」というoracle型の設定では、$c$ が十分大きいと一次転移を避けたり、少なくとも磁化ジャンプを小さくしたりできます。ところが、AMPなどの実用アルゴリズムで作った候補解は、受信信号や拡散符号と強く相関しています。同じ $c$ を持っていても、oracle型の候補と同じ情報を持つわけではありません。そのため、単純な $c$ だけの理論では一次転移回避を予測しても、実際の候補では自由エネルギー地形が期待通りに変わらない場合があります。

この点は、リバースアニーリングを研究道具として見る上で大事です。「良い初期解を入れればよい」では終わりません。その初期解が、目的関数にすでに含まれている情報の焼き直しなのか、それとも目的関数の外から来た本当に新しい情報なのでしょうか。平均場解析は、その違いを自由エネルギー地形の違いとして問い直します。

参考文献: [1], [2], [3]。

参考文献

1. Masaki Ohkuwa, Hidetoshi Nishimori, Daniel A. Lidar, “Reverse annealing for the fully connected p -spin model,” Physical Review A 98, 022314 (2018). 出典

2. Yu Yamashiro, Masaki Ohkuwa, Hidetoshi Nishimori, Daniel A. Lidar, “Dynamics of reverse annealing for the fully connected p -spin model,” Physical Review A 100, 052321 (2019). 出典

3. Shunta Arai, Masayuki Ohzeki, Kazuyuki Tanaka, “Mean field analysis of reverse annealing for code-division multiple-access multiuser detection,” Physical Review Research 3, 033006 (2021). 出典