More than 3 years have passed since last update.

GLEAP

量子アニーリング (Quantum Anneling)

Last updated at 2020-02-28Posted at 2020-02-28

この記事に関して

ここでは量子アニーリングについて説明します。
イジングモデルから読むとわかりやすいです。

ここではイジングハミルトニアンの固有値を最小化させます。
求めるハミルトニアンは以下とします。

古典

E_0 = \sum_{i < j}^{}J_{ij}\sigma_i\sigma_j \ \ ( \sigma_i \in \{\pm 1\} )

量子

H_0 = \sum_{i < j}^{}J_{ij}Z_i Z_j \ , \ H_1 = \sum_{i}^{}X_i

$X$, $Z$ はそれぞれ、$X$, $Z$ ゲートです。

SA (Simulated Anneling)

量子アニーリングの原型であるSA法について説明します。
基本的にSAもQAもハミルトニアンの最小値を求めるアルゴリズムです。

まずはイジングモデルを考えます。
このときある配置 $\sigma_t$ をとる確率 $p(\sigma_t)$ は

p(\sigma_t) = \frac{ e^{-\beta E(\sigma_t)} }{Z}

また、ここから次の配置 $\sigma_{t+1}$ を考えるとすると、この配置をとる確率は

p(\sigma_{t+1}) = \frac{ e^{-\beta E(\sigma_{t+1})} }{Z}

と置くことができます。
このことから、配置 $\sigma_t$ から配置 $\sigma_{t+1}$ に移る確率は

\frac{p(\sigma_t)}{p(\sigma_{t+1})} = e^{-\beta\{ E(\sigma_t)-E(\sigma_{t+1}) \}}

と考えられることができます。

メトロポリス法

更新方法は色々あるのですが、今回はメトロポリス法と言う方式を使います。
上に述べた遷移する確率から、 $E(\sigma_t)-E(\sigma_{t+1})$ について考えます。

$E(\sigma_t)-E(\sigma_{t+1}) < 0$ なら

e^{-\beta\{ E(\sigma_t)-E(\sigma_{t+1}) \}} > 1

から、必ず $\sigma_{t+1}$ 遷移すると考えます。

$E(\sigma_t)-E(\sigma_{t+1}) > 0$ なら

e^{-\beta\{ E(\sigma_t)-E(\sigma_{t+1}) \}} < 1

から、確率的に $\sigma_{t+1}$ に遷移すると考えます。

アルゴリズム

メトロポリス法よりアルゴリズムは以下のようになります。

$t$ 番目の配置 $\sigma_t$ の近傍から $\sigma'$ を選ぶ。
$E(\sigma') < E(\sigma_t)$ ならば $\sigma_{t+1} = \sigma'$ とする。
$E(\sigma') > E(\sigma_t)$ ならば確率 $e^{-\beta(E(\sigma_t)-E(\sigma'))}$ で $\sigma_{t+1} = \sigma'$ とする。
$T$ を少し小さくする。

以上の繰り返し処理をモンテカルロステップ(Monte Carlo Step) と言います。

QA (Quantum Anneling)

量子アニーリング法を説明します。
量子アニーリングはSA法を量子の性質を使って応用させたアルゴリズムです。

求めるハミルトニアン $H_0$ に横磁場と呼ばれるハミルトニアン $H_1$ を加えた $H(t)$ を考えます。

H(t) = H_0 + \Gamma(t)H_1 \ \ (t > 0)\\

ここで $\Gamma$ は以下を満たします。

\lim_{t \to +0}\Gamma(t) = \infty \ , \ \lim_{t \to \infty}\Gamma(t) = 0

また初期状態を $\left|\phi(0)\right> = \left|+\right>^{\otimes n}$ とします。
これを用いるためにまず時間発展を説明します。

時間発展

量子状態が時間によって変化することを時間発展と言います。

シュレディンガー方程式

ハミルトニアンを $H$ とすると量子状態は以下の式にしたがって変化します。

-i\frac{\partial }{\partial t}\left|\psi(t)\right> = H\left|\psi(t)\right>

ハミルトニアンが時間に依存しない場合

あるハミルトニアン $H$ について初期状態を $\left|\psi(0)\right>$ とします。
このとき $t$ 時間発展させた状態 $\left|\psi(t)\right>$ はシュレディンガー方程式から以下のようになります。

\left|\psi(t)\right> = e^{-iH(t)}\left|\psi(0)\right>

ハミルトニアンが時間に依存する場合

あるハミルトニアン $H(t)$ について初期状態を $\left|\psi(0)\right>$ とします。
このとき $t$ 時間発展させた状態 $\left|\psi(t)\right>$ はシュレディンガー方程式から以下のようになります。

\left|\psi(t)\right> = U(t)\left|\psi(0)\right>

$U(t)$ は適当なユニタリ行列です。

今回は $\left|\phi(0)\right> = \left|+\right>^{\otimes n}$ の $H(t)$ による時間発展を $\left|\phi(t)\right>$ とします。

断熱定理

$H(t)$ の固有値を $E_i(t)$、固有ベクトルを $\left|\psi_i(t)\right>$ とする。$(E_0(t) ≦ E_1(t) ≦ \cdots ≦ E_n(t))$
また $H_1$ の固有ベクトルを $\left|\phi_i(t)\right>$ とします。

H(t)\left|\psi_i(t)\right> = E_i(t)\left|\psi_i(t)\right>

このとき $\left|\phi_i(t)\right>$ を $\left|\phi_i(\Delta t)\right>$ に微小時間発展させた場合以下の式が成り立ちます。

\left|\phi_i(\Delta t)\right> \approx \left|\psi_i(\Delta t)\right>

参考：https://aichi-pu.repo.nii.ac.jp/?action=repository_uri&item_id=3641&file_id=22&file_no=1

このことから $H(t)$ の状態は常に始めの固有状態(固有ベクトル)を取りながら動きます。

アルゴリズム

QA では初期状態 $\left|\phi(0)\right> = \left|+\right>^{\otimes n}$ の時間発展を行います。

ここで上で述べた、断熱定理より

\left|\psi_0(\Delta t)\right> \approx \left|\phi(\Delta t)\right>

\lim_{t \to \infty}\left|\psi_0(t)\right> \approx
\lim_{t \to \infty}\left|\phi(t)\right>

したがって $t→\infty$ で $H(t)→H_0$ から $H_0$ の固有ベクトルに収束していくことがわかるので、

\left<\phi(t)\right|H(t)\left|\phi(t)\right> \xrightarrow{t \to \infty}
\left<\psi_0(t)\right|H_0\left|\psi_0(t)\right>

$H_0$ の最小固有値となり解が求まります。

断熱計算

一般的に量子アニーリングは以下の式を用います。

H(t) = \frac{t}{\tau}H_0 + \left(1-\frac{t}{\tau}\right)H_1

これを用いて上と同じことを行います。

各係数について

\lim_{t \to +0} \frac{t}{\tau} = 0 \ , \ \lim_{t \to \tau} \frac{t}{\tau} = 1

\lim_{t \to +0} H(t) = H_1 \ , \ \lim_{t \to \tau} H(t) = H_0

よって $H(t)$ は始めと同じように考えることができ、
断熱定理より、$H_0$ の固有ベクトルが求められることがわかります。

この方法の場合、$t$ を有限値で考えることができます。

QAとSAの違い(古典的解釈)

ここではQAがなぜSAからきていると解釈できるのかを考えます。
方法としては量子アニーリングを量子モンテカルロ法を用いて古典的に解釈してSAと比較します。

量子モンテカルロ法

分配関数 $Z$ を考えます。

Z = \sum_{i}^{}e^{-\beta E_i(t)} =
\sum_{i}^{}\left<i\right|e^{-\beta H(t)}\left|i\right> =
\sum_{i}^{}\left<i\right|e^{-\beta (H_0 + \Gamma(t)H_1)}\left|i\right>

ここで $\left|i\right>$ は $i$ 番目のみ $\left|1\right>$ でそれ以外は $\left|0\right>$ とします。
これを古典に書き直していきます。

Lie – Trotter 積公式

通常の指数関数は $e^{x+y} = e^x e^y$ と分解できるが
指数行列の場合は $AB - BA \neq 0$ のように行列で非可換な場合は上のように分解できません。

ただこれを近似的に分解することはできます。
この式を Lie – Trotter 積公式と言い、以下のようになります。

e^{A+B} = \lim_{n \to \infty} \left(e^{\frac{A}{n}}e^{\frac{B}{n}}\right)^{n}

この $n$ を有限値 $m$ で止めると、

e^{A+B} = \left(e^{\frac{A}{m}}e^{\frac{B}{m}}\right)^{m} + O\left(\frac{1}{m}\right) \approx \left(e^{\frac{A}{m}}e^{\frac{B}{m}}\right)^{m}

と近似的に表せます。

続き

$Z$ に Lie – Trotter 積公式を考えると

Z = \sum_{i}^{}\left<i\right|e^{-\beta (H_0 + \Gamma(t)H_1)}\left|i\right> \approx 
\sum_{i}^{}\left<i\right|
\left(e^{-\frac{\beta}{m} H_0} e^{-\frac{\beta \Gamma(t)}{m} H_1}\right)^m
\left|i\right>

= \sum_{i}^{}\left<i\right|
\left(e^{-\frac{\beta}{m} H_0} e^{-\frac{\beta \Gamma(t)}{m} H_1}\right)
\left(e^{-\frac{\beta}{m} H_0} e^{-\frac{\beta \Gamma(t)}{m} H_1}\right)
\cdots
\left(e^{-\frac{\beta}{m} H_0} e^{-\frac{\beta \Gamma(t)}{m} H_1}\right)
\left|i\right>

この $m$ をトロッター数と言います。
またベクトル $\left|i\right>$ について以下のことが成り立ちます。

\sum_{i}^{}\left|i\right>\left<i\right| = I

このベクトルの組を完全正規直交系と言います。
これを各指数写像の間に入れます。

Z \approx \sum_{i_0,\cdots i_{2m-1}}^{}\left<i_0\right|
e^{-\frac{\beta}{m} H_0} \left|i_1\right>\left<i_1\right|
e^{-\frac{\beta \Gamma(t)}{m} H_1} \left|i_2\right>
\cdots
\left<i_{2m-1}\right|
e^{-\frac{\beta \Gamma(t)}{m} H_1}\left|i_0\right>

これをさらに詳しく書くと、$H_0$ に関して

\left<i_k\right|
e^{-\frac{\beta}{m} H_0} \left|i_{k+1}\right> =
\left<i_k\right|
\exp \left(-\frac{\beta}{m} \sum_{p<q}^{}J_{pq}Z_p Z_q \right) \left|i_{k+1}\right>

(イジングモデルは $i, j$ にすると添字が変わるので $p, q$ で置きました。)
$Z_p$ の $\left|i_k\right>$ に関する固有値を $\sigma_{i_k}^{p}$ とすると

Z_p \left|i_k\right> =
\sigma_{i_k}^{p} \left|i_k\right> \ , \ 
\left(\sigma_{i_k}^{p} \in \{\pm 1\} \right)

と考えることができます。

$Z_p$ は対角行列なので、$e^{Z_p}$ の $\left|i_k\right>$ に関する固有値は $e^{\sigma_{i_k}^{p}}$ となります。
また $Z_p Z_q = Z_q Z_p$ より $e^{Z_p Z_q} = e^{Z_p} e^{Z_q}$ とできます。
よって

e^{Z_p Z_q}\left|i_k\right> = 
e^{Z_p} e^{Z_q}\left|i_k\right> = 
e^{\sigma_{i_k}^{q}} e^{Z_p} \left|i_k\right> = 
e^{\sigma_{i_k}^{p}} e^{\sigma_{i_k}^{q}} \left|i_k\right>

$H_0$ は $Z_p Z_q$ の線形和で書けるので

\left<i_k\right|
\exp \left(-\frac{\beta}{m} \sum_{p<q}^{}J_{pq}Z_p Z_q \right) \left|i_{k+1}\right> = 
\exp \left(-\frac{\beta}{m} \sum_{p<q}^{}J_{pq} \sigma_{i_{k+1}}^{p} \sigma_{i_{k+1}}^{q} \right)\left<i_k\right|\left|i_{k+1}\right>

$H_1$ に関しては

\left<i_k\right|
e^{-\frac{\beta \Gamma(t)}{m} H_1} \left|i_{k+1}\right> =
\left<i_k\right|
\exp \left(-\frac{\beta \Gamma(t)}{m} \sum_{l}^{}X_l \right) \left|i_{k+1}\right>

また $X_i X_j = X_j X_i$ より、指数行列を分解できて、

\left<i_k\right|\prod_{l}^{}
e^{-\frac{\beta \Gamma(t)}{m} X_l} \left|i_{k+1}\right>

$\left|i_k\right> = \left|i_k^0\right> \otimes \left|i_k^1\right> \otimes \cdots \left|i_k^N\right>$ と置くと ( $i_k \in 0, 1 $ )

\left<i_k\right|\prod_{l}^{N}
e^{-\frac{\beta \Gamma(t)}{m} X_l} \left|i_{k+1}\right> =
\prod_{l}^{N}\left<i_k^l\right|
e^{-\frac{\beta \Gamma(t)}{m} X_l} \left|i_{k+1}^l\right>

次に $e^{-\frac{\beta \Gamma(t)}{m} X_l}$ に関して、$X_l^2 = I$ からマクローリン展開より

e^{-\frac{\beta \Gamma(t)}{m} X_l} = 
\sum_{n=0}^{\infty}\frac{1}{n!}\left(-\frac{\beta \Gamma(t)}{m} X_l \right)^n=
\sum_{j=0}^{\infty}\frac{1}{(2j)!}\left(-\frac{\beta \Gamma(t)}{m} \right)^{2j} I +
\sum_{j=0}^{\infty}\frac{1}{(2j+1)!}\left(-\frac{\beta \Gamma(t)}{m} \right)^{2j+1} X_l

$\cosh x, \sinh x$ はマクローリン展開すると

\cosh x = \sum_{j=0}^{\infty}\frac{1}{(2j)!} x^{2j} \ , \ 
\sinh x = \sum_{j=0}^{\infty}\frac{1}{(2j+1)!} x^{2j+1}

より

e^{-\frac{\beta \Gamma(t)}{m} X_l} = 
I \cosh \left(-\frac{\beta \Gamma(t)}{m}\right) +
X_l \sinh \left(-\frac{\beta \Gamma(t)}{m}\right)

\left<i_k^l\right|
e^{-\frac{\beta \Gamma(t)}{N} X_l} \left|i_{k+1}^l\right> =
\cosh \left(-\frac{\beta \Gamma(t)}{m}\right)
\left<i_k^l\right|\left|i_{k+1}^l\right> +
\sinh \left(-\frac{\beta \Gamma(t)}{m}\right)
\left<i_k^l\right|X_l\left|i_{k+1}^l\right>

$\left< i_k^l\right|X_l\left|i_{k+1}^l\right>$ は

\left<i_k^l\right|X_l\left|i_{k+1}^l\right> = \left \{
\begin{array}{cc}
0 & \left(i_k^l = i_{k+1}^l\right) \\
1 & \left(i_k^l \neq i_{k+1}^l\right)
\end{array}\right.

から

\left<i_k^l\right|
e^{-\frac{\beta \Gamma(t)}{N} X_l} \left|i_{k+1}^l\right> = \left \{
\begin{array}{cc}
\cosh \left(-\frac{\beta \Gamma(t)}{m}\right) & \left(i_k^l = i_{k+1}^l\right) \\
\sinh \left(-\frac{\beta \Gamma(t)}{m}\right) & \left(i_k^l \neq i_{k+1}^l\right)
\end{array}\right.

計算できたのでこれをまた指数の形に戻します。( $H_0$ と合わせるため )

\cosh x = \left(\frac{1}{2} \sinh(2x)\right)^{1/2}e^{-\frac{1}{2}\log (\tanh x)} \ , \ 
\sinh x = \left(\frac{1}{2} \sinh(2x)\right)^{1/2}e^{\frac{1}{2}\log (\tanh x)}

と変形できます。( $\tanh x = \exp(\log(\tanh x))$ を使う。)

\left<i_k^l\right|
e^{-\frac{\beta \Gamma(t)}{m} X_l} \left|i_{k+1}^l\right> = \left \{
\begin{array}{cc}
\left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{1/2}e^{-\frac{1}{2}\log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) } & \left(i_k^l = i_{k+1}^l\right) \\
\left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{1/2}e^{\frac{1}{2}\log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) } & \left(i_k^l \neq i_{k+1}^l\right)
\end{array}\right.

次に $\sigma_{i_k}^l$ を $\sigma_{i_k}^l = 2 i_k^l -1$ で定義します。( $\sigma_k^l \in {\pm 1} $ )

\sigma_{i_k}^l \sigma_{i_{k+1}}^l =
\left \{
\begin{array}{cc}
1 & \left(i_k^l = i_{k+1}^l\right) \\
-1 & \left(i_k^l \neq i_{k+1}^l\right)
\end{array}\right.

これを用いると

\left<i_k^l\right|
e^{-\frac{\beta \Gamma(t)}{m} X_l} \left|i_{k+1}^l\right> = 
\left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{1/2}e^{\frac{1}{2} \sigma_{i_k}^l \sigma_{i_{k+1}}^l \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) }

以上から $H_1$ は

\left<i_k\right|
e^{-\frac{\beta \Gamma(t)}{m} H_1} \left|i_{k+1}\right> =
\prod_{l}^{N}\left<i_k^l\right|
e^{-\frac{\beta \Gamma(t)}{m} X_l} \left|i_{k+1}^l\right> =
\prod_{l}^{N}\left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{1/2}e^{\frac{1}{2} \sigma_{i_k}^l \sigma_{i_{k+1}}^l \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) }

= \left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{N/2}e^{\frac{1}{2} \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) \sum_{l}^{N}\sigma_{i_k}^l \sigma_{i_{k+1}}^l }

最終的に $Z$ は以下のようになります。

Z \approx \sum_{i_0,\cdots i_{2m-1}}^{N}\prod_{k=0}^{m-1}\left<i_{2k}\right|
e^{-\frac{\beta}{m} H_0} \left|i_{2k+1}\right>\left<i_{2k+1}\right|
e^{-\frac{\beta \Gamma(t)}{m} H_1} \left|i_{2k+2}\right> \ \ 
(i_{2m} := i_0)

= \sum_{i_0,\cdots i_{2m-1}}^{N}\prod_{k=0}^{m-1}
e^{ -\frac{\beta}{m} \sum_{p<q}^{}J_{pq} \sigma_{i_{2k+1}}^{p} \sigma_{i_{2k+1}}^{q} }
\left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{N/2}
e^{\frac{1}{2} \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) \sum_{l=0}^{N}\sigma_{i_{2k+1}}^l \sigma_{i_{2k+2}}^l }
\left<i_{2k}\right|\left|i_{2k+1}\right>

= \left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{mN/2}
\sum_{i_0,\cdots i_{2m-1}}^{N}\prod_{k=0}^{m-1}
\exp \left(
-\frac{\beta}{m} \sum_{p<q}^{}J_{pq} \sigma_{i_{2k+1}}^{p} \sigma_{i_{2k+1}}^{q} +
\frac{1}{2} \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) \sum_{l=0}^{N}\sigma_{i_{2k+1}}^l \sigma_{i_{2k+2}}^l
\right)
\left<i_{2k}\right|\left|i_{2k+1}\right>

ここで $\left< i_{2k}\right|\left|i_{2k+1}\right>$ より $i_{2k} = i_{2k+1}$ と置けて、

= \left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{mN/2}
\sum_{i_0,i_2 \cdots i_{2m-2}}^{N}\prod_{k=0}^{m-1}
\exp \left(
-\frac{\beta}{m} \sum_{p<q}^{}J_{pq} \sigma_{i_{2k}}^{p} \sigma_{i_{2k}}^{q} +
\frac{1}{2} \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) \sum_{l=0}^{N}\sigma_{i_{2k}}^l \sigma_{i_{2k+2}}^l
\right)

$i_{2k} = i_k$ と置き換えると

= \left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{mN/2}
\sum_{i_0,i_1 \cdots i_{m-1}}^{N}\prod_{k=0}^{m-1}
\exp \left(
-\frac{\beta}{m} \sum_{p<q}^{}J_{pq} \sigma_{i_k}^{p} \sigma_{i_k}^{q} +
\frac{1}{2} \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) \sum_{l=0}^{N}\sigma_{i_k}^l \sigma_{i_{k+1}}^l
\right)

= \left(\frac{1}{2} \sinh \left(-\frac{2\beta \Gamma(t)}{m} \right)\right)^{mN/2}
\sum_{i_0,i_1 \cdots i_{m-1}}^{N}
\exp \left(
-\frac{\beta}{m} \left(
\sum_{k=0}^{m-1}\sum_{p<q}^{}J_{pq} \sigma_{i_k}^{p} \sigma_{i_k}^{q} -
\frac{m}{2\beta} \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) \sum_{k=0}^{m-1}\sum_{l=0}^{N}\sigma_{i_k}^l \sigma_{i_{k+1}}^l
\right)\right)

このうち指数関数の部分について、各 $i_k$ を固定させて考えると

E' =
\sum_{k=0}^{m-1}\sum_{p<q}^{}J_{pq} \sigma_k^p \sigma_k^q -
\frac{m}{2\beta} \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) \sum_{k=0}^{m-1}\sum_{l=0}^{N}\sigma_k^l \sigma_{k+1}^l

と置けば第1項を見れば量子のハミルトニアンを古典に変換できたことがわかります。
また $k$ を固定させると

E'_k =
\sum_{p<q}^{}J_{pq} \sigma_k^p \sigma_k^q -
\frac{m}{2\beta} \log \tanh \left(-\frac{\beta \Gamma(t)}{m}\right) \sum_{l=0}^{N}\sigma_k^l \sigma_{k+1}^l

これをSAに適用させます。

アルゴリズム

各 $E'_k$ ごとに以下の操作を考えます。

$t$ 番目の配置 $\sigma_t$ の近傍から $\sigma'$ を選ぶ。
$E'(\sigma') < E'(\sigma_t)$ ならば $\sigma_{t+1} = \sigma'$ とする。
$E'(\sigma') > E'(\sigma_t)$ ならば確率 $e^{-\beta(E(\sigma_t)-E(\sigma'))}$ で $\sigma_{t+1} = \sigma'$ とする。
$T$ を少し小さくする。(ここまでは Monte Carlo Step)
$ \Gamma(t)$ を小さくして Monte Carlo Step を行う。

以上の繰り返し処理をアニーリングステップ (Anneling Step) と言います。
6. 各 $E'_k$ の中の第1項の最小値を求める。

以上のことから SA は一つの点のみ近傍探索を行うのに対し、
QA は各 $E'_k$ を同時に考えるので複数点を同時に近傍探索していることがわかります。