イジングモデルのハミルトニアンからQUBOを導出

カナダのベンチャー企業D-Wave社は，D-Wave 2000Qという量子アニーリング専用ハードウェアを開発しました．

組合せ最適化問題を量子アニーリングで解く際は，問題をイジングモデルにマッピングする必要があります．

QUBO (Quadratic Unconstrained Binary Optimization)は，様々なアニーリングマシンで扱える統一フレームワークとして考案されました．

イジング形式とQUBO形式は簡単に変換することができますので，問題をQUBOに定式化しておくと非常に便利です．

イジングモデルのハミルトニアン

イジングモデル上にマッピングされたノードは，スピン変数として$\sigma_i \in \{+1,-1\}$どちらかの配位状態を持ちます．

また，ノード$i$自身には$h_i$の磁場係数，ノード$i$とノード$j$の間には$J_{ij}$の相互作用係数が存在します．

このモデルのハミルトニアンは，式(1)で表されます．

$$H=\sum_{i<j} J_{ij} \sigma_i \sigma_j + \sum_i h_i \sigma_i \tag{1}$$

QUBOへの変換

$N$ビット変数によるハミルトニアンの最適化を行うには，$N \times N$上三角行列に係数を定義したQUBO行列を生成することになります．

イジングモデルのハミルトニアンからQUBOを求めるために，$\sigma_i \in \{+1,-1\}$に対して，$q_i = \frac{\sigma_i +1}{2}$を作用させます．

これにより，スピン変数$\sigma_i \in \{+1,-1\}$は，バイナリ変数$q_i \in \{0,1\}$に変換されます．

さらに，バイナリ変数については$q_i = q_i^2$が成立し，これらを式(1)に作用させることで，式(2)が成り立ちます．

$$H’=\sum_{i<j} a_{ij} q_i q_j + \sum_i b_i q_i^2 \tag{2}$$

式(2)はすべての項が，2つのバイナリ変数積で表されます．

よって式(2)は，式(3)のように行列-ベクトル積で表すことができます．

$$H’=(q_0, q_1, \cdots, q_{N-1}) \left( \begin{array}{cccc} b_{0} & a_{01} & \ldots & a_{0N} \\ 0 & b_{1} & \ldots & a_{1N} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & b_{N-1} \end{array} \right) \left( \begin{array}{c} q_1 \\ q_2 \\ \vdots \\ q_{N-1} \end{array} \right) \tag{3}$$

式(3)に表れる上三角行列がQUBO行列です．

実用上は，アニーリングマシンにこの行列を送るだけで済むので非常に便利です．

MASA

My favorite food is Sushi and Yakiniku.