「量子アニーリング法を用いたクラスタ分析」メモ

古典系に対するsimulated annealing
H_cは対角化されているハミルトニアン

\mathcal{H_c} : \text{Hamitonian}

分配関数

Z = \text{Tr} e^{- \beta \mathcal{H_c}}
 = \sum_{\{\sigma_i\}} e^{-\beta E(\sigma_{i})}

ここで、

\sigma_i = \pm 1

simulated annealing

P(A|B) = \frac{P(A \cap B)}{P(B)}

なので

P(\tilde \sigma_{i}|\{\sigma\} \smallsetminus \tilde \sigma_i)=\frac{e^{-\beta E(\{ \sigma \})}}{\sum_{\tilde \sigma_i = \pm 1} e^{-\beta E(\{\sigma\}) }}

1 spinづつ、フリップさせて平衡状態を保ちつつ、温度をさげていく。
beta無限大で基底状態、ハミルトニアンの意味で最適解が得られる。。。はず。。。

quntum annealing

ハミルトニアン

\mathcal{H} = \mathcal{H_c} + \mathcal{H_q}

H_cは対角化されている。 H_cとH_qは非可換。
まあ、横磁場付きIsing model, transverse Ising model.

\mathcal{H} = \mathcal{H_c} + \mathcal{H_q} = \sum_{<ij>} J_{ij} \sigma^z_i\sigma^z_j + \Gamma \sum_i  \sigma^x_i 

\sigma^z_i = 
\left (
\begin{matrix}
1 & 0 \\
0 & -1 \\
\end{matrix}
\right ),
\sigma^x_i = 
\left (
\begin{matrix}
0 & 1 \\
1 & 0 \\
\end{matrix}
\right )

後で式のフォローするが、結論的には

• 横磁場Ising modelの量子スピン系で、鈴木-トロッター変換で、次元＋１の古典Ising modelに変換される。
• 古典Ising modelにして普通のGibbs sampling,モンテカルロを使う
• m 並列 SAとの違いは、相関が2方向である。
• 交換モンテカルロ的な