最大カット問題とは
代表的な組合せ最適化問題の一つである最大カット問題について説明します。最大カット問題では、以下の図 1 に示すような、辺に重みのある無向グラフを考えます。
図 1 : 重み付き無向グラフの例
そして、以下の図 2 に示すように辺をカットすることにより、2 つの部分点集合に分けます。
図 2 : 図 1 のグラフに対するカットの一例
図 2 では、カットを灰色の線で示しています。このカットにより、$\{2\}$ と $\{1,3,4,5\}$ という部分集合に分けられます。このとき、カットされた辺 ( オレンジ色の辺 ) の重みを計算すると、$2+1+1=4$ となります。最大カット問題は、このようにカットされた辺の重みの合計が最大になるようなカットを求める問題です。図 2 のグラフにおける最大カットを以下の図 3 に示します。
図 3 : 図 1 のグラフに対する最大カット
図 3 において、カットされた辺の重みの合計は $2+1+2+1+1=7$ となり、このグラフでは最大の値です。このとき、頂点集合は $\{1,3,4\}$ と $\{2,5\}$ に分けられます。
最大カット問題の定式化
量子アニーリングは、以下の式 (1) で表されるイジングモデルの基底状態を探索するアルゴリズムです。
$\displaystyle\begin{equation}
\mathcal{H}_{\rm{Ising}}(s)=\frac{1}{2}\sum_{i\ne j}^{N}J_{ij}s_{i}s_{j}+\sum_{i=1}^{N}h_is_i \tag{1}
\end{equation}$
ここで、$s_i \in \{\pm 1\} \ (i=1,\dots,N)$ はスピン変数、$J_{ij}$ は相互作用、$h_i$ は外磁場です。イジングモデルの基底状態とは、式 (1) を最小にするようなスピン変数 $s_i$ の組み合わせのことです。したがって、量子アニーリングで何らかの組合せ最適化問題を解くためには、その組合せ最適化問題を式 (1) の最小化問題として定式化する必要があります。
ここでは、最大カット問題について、その定式化を行っていきます。結論から述べると、
$\displaystyle\begin{align*}
\mathcal{H}_{\rm{Ising}}(s)=\frac{1}{2}\sum_{i\ne j}J_{i j} s_{i} s_{j} \tag{2}
\end{align*}$
と置くことにより、$\mathcal{H}_{\rm{Ising}}(s)$ の最小化がカット構成の最大化に対応することになります。以下では、この表式を導出していきます。
まず、無向グラフ $\mathcal{G} = (\mathcal{V},\mathcal{E})$ で辺の重み $\{w_{ij}\}_{(ij)\in \mathcal{E}}$ が与えられたとします。そして、カットによって分けられた２つの部分点集合を $\mathcal{V}_{+}$ および $\mathcal{V}_{-}$ とします(すなわち $\mathcal{V}=\mathcal{V}_{+}\cup \mathcal{V}_{-}$ かつ $\mathcal{V}=\mathcal{V}_{+}\cup \mathcal{V}_{-}=\emptyset$ )。このとき、最大カット問題は、集合 $\mathcal{V}_{+}$ と集合 $\mathcal{V}_{-}$ を結ぶ $w_{ij}$ の和
$\displaystyle\begin{align*}
C\equiv \sum_{i\in \mathcal{V}_{+},j\in\mathcal{V}_{-},(ij)\in\mathcal{E}}w_{ij} \tag{3}
\displaystyle\end{align*}$
を最大化する頂点の分け方を求める問題とみなすことができます。式 (3) では、点 $i$ と点 $j$ がそれぞれ違う集合 ( $\mathcal{V}_{+}$ と $\mathcal{V}_{-}$ ) に属する場合にのみ辺 $(i,j)$ の重みを足しているため、カットされた辺の重みの合計を求めることに対応しています。
さらに、式 (3) はスピン変数 $s_i \in \{ \pm 1\}$ を用いることにより、
$\displaystyle\begin{align*}
C(s)=\frac{1}{2}\sum_{(ij)\in \mathcal{E}}w_{i j}(1-s_i s_j) \tag{4}
\displaystyle\end{align*}$
と書き換えることができます。ただし、$s_i = s_j$ ならば $i$ と $j$ は同じ集合に属し、$s_i \ne s_j$ ならば $i$ と $j$ は異なる集合に属するとします。ここで、$s_i \in \{ \pm 1 \} $ であるので、$s_i = s_j$ ならば $s_i s_j = +1$、$s_i \ne s_j$ ならば $s_i s_j = -1$ となります。したがって、$s_i = s_j$ のとき ( $i$ と $j$ が同じ集合に属するとき )、式 (4) において $(1-s_i s_j)=0$ となるので重み $w_{ij}$ は足されません。逆に、$s_i \ne s_j$ のとき ( $i$ と $j$ が異なる集合に属するとき ) 重み $w_{ij}$ が足されるため、式 (3) と等価になっています。
次に、$C(s)$ をイジングモデルのパラメータ ( $J_{ij},\ h_i $ ) を用いて表現します。すなわち、$J_{ij} = w_{ij} , h_i = 0$ と置くと、式(4)は
$\displaystyle\begin{align*}
C(s)=-\frac{1}{2}\sum_{i\ne j}J_{i j}s_i s_j+ \frac{1}{2}\sum_{i\ne j}J_{i j}\tag{5}
\end{align*}$
となります。このとき、第二項 $\frac{1}{2}\sum_{i\ne j}J_{i j}$ は定数なので、$C(s)$ の最大化には関係しません。したがって、$\mathcal{H}_{\rm{Ising}}(s)=\frac{1}{2}\sum_{i\ne j}J_{ij}s_{i}s_{j}$ と置くと、$\mathcal{H}_{\rm{Ising}}(s)$ の最小化により $C(s)$ は最大化されます。したがって、式 (2) の最小化がカット構成の最大化に対応することが分かります。[1]
参考文献
- Irie, H., Liang, H., Doi, T. et al. Hybrid quantum annealing via molecular dynamics. Sci Rep 11, 8426 (2021). https://doi.org/10.1038/s41598-021-87676-z