はじめに
前回に引き続き疑似量子アニーリングを用いた問題解決を進めているが、実際の量子コンピュータで扱う問題の規模に近づいてくると、逐次実行ではシミュレーションの実行に時間がかかり現実的な時間で解けなくなってくる。
そこで今回は、GPUで動く大規模QUBOアニーリングのためのライブラリ Tytan SDK を使った並列実行で疑似量子アニーリングで古典的なMAX-CUT問題を解き、CPU実装と性能を比較してみた。
MAX-CUT問題とは
MAX-CUT問題は、グラフ理論における代表的な組合せ最適化問題の一つだ。
グラフ $G = (V, E)$ が与えられたとき、頂点集合 $V$ を2つの部分集合 $S$ と $\bar{S}$ に分割し、集合をまたぐエッジ$E$の数(=カット数)を最大化する問題である。
具体例
例えば、5つの頂点を持つグラフを考えてみる：
このグラフを2つのグループ（例：{1, 2, 4} と {0, 3}）に分割したとき、グループ間をつなぐエッジの数が最大になるような分割を見つけるのがMAX-CUT問題だ。
上図では頂点グループは{1, 2, 4} と {0, 3}に別れ、分割数5で最大になる
応用例
MAX-CUT問題は以下のような実世界の問題に応用できる。
- 回路設計: VLSI設計(数十億個ものトランジスタを1つの半導体チップ上に集積する回路設計)における配線最適化
- ネットワーク分割: ソーシャルネットワークのクラスタリング
- 画像処理: 画像のセグメンテーション
MAX-CUT問題の数式表現
QUBO形式への変換
量子アニーリングでMAX-CUT問題を解くために、問題をQUBO形式に変換する必要がある。
問題設定
各頂点 $i$ に対してバイナリ変数 $x_i \in {0, 1}$ を割り当てる。
- $x_i = 0$ なら頂点 $i$ は集合 $S$ に属する（グループA）
- $x_i = 1$ なら頂点 $i$ は集合 $\bar{S}$ に属する（グループB）
エッジ $(i, j)$ が「カットされる」とは、両端の頂点が異なるグループに属することを意味する。つまり、以下のように定義できる。
- $x_i = 0$ かつ $x_j = 1$ のとき、エッジ $(i, j)$ はカットされる
- $x_i = 1$ かつ $x_j = 0$ のとき、エッジ $(i, j)$ はカットされる
- $x_i = x_j$ のとき、エッジ $(i, j)$ はカットされない
XOR演算による表現
要はエッジがカットされる条件は「$x_i$ と $x_j$ の変数が異なる」ことなので、XOR演算の次式で表現できる。
$$
x_i \oplus x_j =
\begin{cases}
1 & (x_i \neq x_j \text{ のとき、カットされる}) \
0 & (x_i = x_j \text{ のとき、カットされない})
\end{cases}
$$
したがって、カットされたエッジの総数は次のようになる。
$$
\text{カット数} = \sum_{(i,j) \in E} (x_i \oplus x_j)
$$
MAX-CUT問題は、この値を最大化する問題である。
XOR演算の展開
ここからQUBOの形式に落とし込むため、XOR演算を算術式に展開する。
バイナリ変数 $x_i, x_j \in {0, 1}$ に対して、以下の恒等式が成り立つ。
$$
x_i \oplus x_j = x_i + x_j - 2x_ix_j
$$
全ての組み合わせ表を確認すると、これが成り立つことが分かる。
| $x_i$ | $x_j$ | $x_i \oplus x_j$ | $x_i + x_j$ | $2x_ix_j$ | $x_i + x_j - 2x_ix_j$ |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 2 | 2 | 0 |
最大化から最小化へ
量子アニーリングは通常、エネルギー関数を最小化する仕組みなので、最大化問題を最小化問題に変換する必要がある。
カット数は最大化したいので、エネルギー関数を以下のように符号反転する。
$$
E = -(\text{カット数}) = -\sum_{(i,j) \in E} (x_i \oplus x_j)
$$
マイナスをつけることで以下のように表現される。
- カット数が多い → $E$ が小さい（良い解）
- カット数が少ない → $E$ が大きい（悪い解）
つまり、$E$ を最小化すればカット数が最大化される。
QUBO形式への変換
先ほどのXOR展開式を代入する。
$$
E = -\sum_{(i,j) \in E} (x_i \oplus x_j) = -\sum_{(i,j) \in E} (x_i + x_j - 2x_ix_j)
$$
マイナスを分配すると
$$
E = \sum_{(i,j) \in E} (-x_i - x_j + 2x_ix_j)
$$
これを整理すると
$$
E = \sum_{(i,j) \in E} 2x_ix_j + \sum_{(i,j) \in E} (-x_i - x_j)
$$
さらに、線形項（$x_i$ の1次の項）をまとめる。
頂点 $i$ に接続されているエッジの本数を $\deg(i)$ とするとQUBOの形式になる。
$$
E = \sum_{(i,j) \in E} 2x_ix_j - \sum_{i \in V} \deg(i) \cdot x_i
$$
$$
E(x) = \sum_{i} Q_{ii}x_i + \sum_{i<j} Q_{ij}x_ix_j
$$
ここで、
-
線形項（対角項）: $Q_{ii} = -\deg(i)$
→ 各頂点の次数に比例した負の係数 -
二次項（非対角項）: $Q_{ij} = 2$
→ エッジ $(i,j)$ が存在する場合のみ
以上で、MAX-CUTの最大カット数を求める式をQUBOの形に持っていくことができた。
次回はこのQUBOをもとに実装したプログラムを動かし、結果を考察していきたい。