イジング模型
イジング模型は、次のハミルトニアンで表されます。
\begin{equation}
H(\mathbf{\sigma}) ~:=~ – \sum_{i<j} J_{ij} \sigma _i \sigma _j ~ – \sum_{i}^{N} h_i \sigma _i
\end{equation}
[latex]\sigma_{i} \in\{-1,+1\}[/latex]はイジング変数です。[latex]J_{ij}[/latex]は2つのイジング変数間の相互作用パラメータ、[latex]h_i[/latex]は局所磁場を表すパラメータです。相互作用の係数が[latex]J_{ij}>0[/latex]のとき、これを強磁性的相互作用と言います。このとき、スピンがそれぞれ同じ方向を向くと、エネルギーは低くなります。また、[latex]J_{ij}<0[/latex]のとき、これを反強磁性的相互作用と言います。このとき、スピンがそれぞれ反対方向を向くと、エネルギーは低くなります。
QUBO
QUBO (Quadratic Unconstrained Binary Optimization) では、次のコスト関数を最小化を行います。
\begin{align}
f(\mathbf{x}) ~:=~& \sum_{i} \sum_{j} Q_{ij} x _i x _j \\
~=~& \mathbf{x}^T Q \mathbf{x}
\end{align}
[latex]x_{i} \in\{0,1\}[/latex]は二値変数です。[latex]Q[/latex]をQUBO行列と呼びます。[latex]\sigma=2x- 1[/latex]を満たすように変数変換を行うと、イジング模型とQUBOは等価に変換することができます。
有名な組合せ最適化問題の多くは、イジング模型やQUBOを用いて定式化が可能であることが知られています [Lucas, 2014]。
参考文献
- [Lucas, 2014] Lucas, A. Ising formulations of many NP problems. Front. Physics 2, 2014, 10.3389/fphy.2014.00005.