別に困らないから誤魔化されてきたやつ
量子アニーリングを行う際は、イジングモデルとQUBOが対応していることを利用して、イジングモデルよりも考えやすいQUBOを使うことが多いと思います。
D-Wave社のマシンでも、MDR社のWildqatライブラリでも、QUBOで書くことができるので、「一対一で対応する」ということだけを覚えていて、具体的にどう変換するのかは知らない方も多いと思います。
そして、私がググった限りでは、QUBOのビットとイジングモデルのスピンの対応関係までは示されていても、それをどのように変換したら、どのように対応するのかを明確に書いている記事は見つかりませんでした。
正直に告白すると、私も以前に書いた記事では、「イジング模型への変換は、これでできるらしいです」という極めて雑な記述をしています。
誤魔化しではなく、自明だから省略されていたのではないか
その可能性はあります。ところで、どういう式になるかご存知でしょうか。
QUBO
$$
H = \sum_{i,j} Q_{ij}q_i q_j
$$
を、イジングモデル
$$
H = \sum_{i<j} J_{ij}s_i s_j + \sum_{i} h_i s_i
$$
に変換すると、Jおよびhは
$$
\begin{eqnarray}
J_{ij} & = & Q_{ij} + Q_{ji} \\
h_i & = & -\sum_{k}(Q_{ik} + Q_{ki})
\end{eqnarray}
$$
となります。Jはともかく、hも自明でしょうか?
やっていきましょう
QUBOのビットとイジングモデルのスピンの向きの対応
まず、QUBOのビット$q_i \in \lbrace 0, 1\rbrace$をイジングモデルのスピンの向き$s_i \in \lbrace \pm 1 \rbrace$に対応させます。
この際、本記事では、0を+1に、1を-1に対応させます。
逆に対応させている記事も多く、どちらにするかは趣味の問題なのですが、特に量子アニーリングでは、イジングモデルのスピンは、±1ではなく$\sigma_z$で表されることも多いです。この場合、ブロッホ球の|0>, |1>に$\sigma_z$をかけると、$\sigma_z |0> = |0>$, $\sigma_z |1> = -|1>$ となり、スピンが$\sigma_z$の固有値と一致して綺麗なので、このようにします。
$q_i$が0のときに$s_i$は1, $q_i$が1のときに$s_i$は-1になる簡単な式を考えると、次のようになります。
$$q_i = \frac{1-s_i}{2}$$
QUBOのQを三角行列に変換する
QUBOのQは、最初から三角行列とされている場合もありますが、そうじゃない流儀もあるようです。
厄介なので、三角行列に変換してしまいましょう。
$$
\begin{eqnarray}
Q_{ij}' =
\begin{cases}
Q_{ij} + Q_{ji} & (i < j) \\
Q_{ij} & (i = j) \\
0 & (i > j)
\end{cases}
\end{eqnarray}
$$
$Q_{ij}q_i q_j + Q_{ji} q_j q_i = Q_{ij}' q_i q_j + Q_{ji}' q_j q_i$なので、QをQ'に変換しても$\sum_{i,j} Q_{ij} q_i q_j = \sum_{i, j} Q_{ij}' q_i q_j$ と、最適化を行いたい式は変わらないことが分かります。
なお、$s_i$の代わりにパウリ行列$\sigma_z^{(i)}$で考えた場合も、$[\sigma_z^{(i)}, \sigma_z^{(j)}] = 0$なので、同様にこの変換は成り立ちます。
QUBOの式にスピンの対応を代入する
先程作った、Q'のQUBOの式に、$q_i = \frac{1-s_i}{2}$の式を代入します。
$$
\begin{eqnarray}
H & = & \sum_{i, j} Q_{ij}' q_i q_j \\
& = & \sum_{i, j} Q_{ij}' \frac{1-s_i}{2} \frac{1-s_j}{2} \\
& = & \frac{1}{4}\sum_{i, j} Q_{ij}' (1-s_i)(1-s_j) \\
& = & \frac{1}{4}\sum_{i, j} Q_{ij}' (1 -s_i-s_j+s_i s_j) \\
\end{eqnarray}
$$
第4項について考えてみましょう。
$$
\begin{eqnarray}
\sum_{i,j}Q_{ij}' s_i s_j & = & \sum_{i<j}Q_{ij}' s_i s_j + \sum_{i=j}Q_{ij}' s_i s_j + \sum_{i>j}Q_{ij}' s_i s_j \\
&=& \sum_{i<j}Q_{ij}' s_i s_j + \sum_{i} Q_{ii}' s_i^2 \\
&=& \sum_{i<j}Q_{ij}' s_i s_j + \sum_{i} Q_{ii}'
\end{eqnarray}
$$
最後の式変換は$s_i = \pm 1$なので、$s_i^2 = 1$を使っています。パウリ行列$\sigma_z^{(i)}$で考えた場合も$\sigma_z^{(i)} \sigma_z^{(i)} = I$が成り立つので、同様の式変形ができます。
続いて、第2項と第3項ですが、
第2項:
$$
\begin{eqnarray}
-\sum_{i, j} Q_{ij}' s_i & = & -\sum_i \sum_j Q_{ij}' s_i\\
& = & -\sum_{i} \sum_{k} Q_{ik}' s_i
\end{eqnarray}
$$
最後の行は、ただ、jをkに置き換えました。
第3項:
$$
\begin{eqnarray}
-\sum_{i, j} Q_{ij}' s_j & = & -\sum_j \sum_i Q_{ij}' s_j \\
& = & -\sum_j \sum_k Q_{kj}' s_j \\
& = & -\sum_i \sum_k Q_{ki}' s_i
\end{eqnarray}
$$
ややトリッキーですが、iをkに置き換えた後、jをiに置き換えなおしてます。
iやjが出てくるのは、Σの中だけの話なので、Σの中でこういった置き換えをしても問題ありません。
これより、第2項と第3項はまとめることができて、
(第2項)+(第3項):
$$
\begin{eqnarray}
-\sum_{i, j} Q_{ij}' s_i-\sum_{i, j} Q_{ij}' s_j & = & -\sum_{i} \sum_{k} Q_{ik}' s_i-\sum_i \sum_k Q_{ki}' s_i \\
&=& -\sum_i \sum_k (Q_{ik}' + Q_{ki}') s_i
\end{eqnarray}
$$
これらの項を元の式に代入すると
$$
\begin{eqnarray}
H & = & \frac{1}{4}\sum_{i, j} Q_{ij}' (1 -s_i-s_j+s_i s_j) \\
& = & \frac{1}{4} \lbrack \sum_{i, j} Q_{ij}' -\sum_i \sum_k (Q_{ik}' + Q_{ki}') s_i + \sum_{i<j}Q_{ij}' s_i s_j + \sum_{i} Q_{ii}' \rbrack
\end{eqnarray}
$$
ここで、第1項と第4項は$s_i$に依存しない定数項です。最小値を与える$s_i$を求める上では影響を及ぼさないので、無視します。また、全体にかかっている$\frac{1}{4}$も同様に無視できます。
一応、無視すると等式ではなくなるので、H'と表すことにします。
すると、
$$
\begin{eqnarray}
H' &=& -\sum_i \sum_k (Q_{ik}' + Q_{ki}') s_i + \sum_{i<j}Q_{ij}' s_i s_j\\
&=& -\sum_i \sum_k (Q_{ik} + Q_{ki}) s_i + \sum_{i<j} (Q_{ij} + Q_{ji}) s_i s_j
\end{eqnarray}
$$
となりました。(Q'の定義を思い出してください)
最後に、イジングモデルの式
$$
H = \sum_{i<j} J_{ij}s_i s_j + \sum_{i} h_i s_i
$$
と対応させると、
$$
\begin{eqnarray}
J_{ij} &= &Q_{ij} + Q_{ji} \\
h_i &=& -\sum_k (Q_{ik} + Q_{ki})
\end{eqnarray}
$$
であることが分かりました。