QAOA 定式化 被覆・パッキング問題

厳密被覆問題 (Exact Cover)

以下のような関係にある集合 $U={1, \ldots, n}$ と、部分集合 $V_{i} \subseteq U(i=1, \ldots, N)$ に対して

$$
U=\bigcup_{i} V_{i}
$$

部分集合の族 $\{V_i\}$ を $R$ としたとき、$R$ の要素が素集合であり、$R$の要素の和集合が$U$であるようなものがあるかどうかという問題です。
ハミルトニアンは、以下のようになります。

$$
H_{A}=A \sum_{\alpha=1}^{n}\left(1-\sum_{i: \alpha \in V_{i}} x_{i}\right)^{2}
$$

ここで、$\alpha$ は、$U$ の要素、$i$ は、部分集合 $V_i$ を示します。$H_A=0$ は、すべての要素が一度だけ含まれる、すなわち要素が粗集合であるということになります。基底エネルギー状態 $H=0$ が存在することは、exact cover 問題の解が存在することに対応します。もし、基底状態が縮退しているなら、複数の解が存在し、$N$ 個のスピンが必要になります。

これを拡張し、最小の exact cover を見つけることは簡単で、下の $H_B$ を、$H_A$ に追加し、$H=H_A+H_B$ とします。

$$
H_{B}=B \sum_{i} x_{i}
$$

このモデルの基底状態は、$m$ を必要な最小の部分集合の数として、$mB$となります。最悪のシナリオは、その和集合が $U$ である単一の共通要素を持つ少数の部分集合がある場合です。これが起こらないようにするには、 $A> nB$ とします。

集合パッキング問題 (Set Packing)

厳密被覆問題と同じ設定で、すべてが素集合である部分集合 $V_i$ の最大数を問題にします。

$H=H_{A}+H_{B}$ というハミルトニアンを用います。

$$
H_{A}=A \sum_{i, j: V_{i} \cap V_{j} \neq \emptyset} x_{i} x_{j}
$$

これは、部分集合がすべて素集合である場合に最低になります。

$$
H_{B}=-B \sum_{i} x_{i}
$$

これは単純に含む集合の数です。$B<A$ とすれば、$H_A$ の制約条件が破られません。

頂点被覆問題 (Vertex Cover)

与えられた無向グラフ $G=(V, E)$ に対して、すべての辺が色付きの頂点に接合するように「色付き」にできる頂点の最小数はいくつかとう問題です。

頂点被覆の例

$x_v$ を頂点にたいして定めたバイナリ変数で、１なら色をつけ、０ならつけないとします。ハミルトニアン $H=H_{A}+H_{B}$ とします。

すべての辺がすくなくとも色付きの頂点を持つ制約条件は、以下の通りになります。

$$
H_{A}=A \sum_{u v \in E}\left(1-x_{u}\right)\left(1-x_{v}\right)
$$

そして、色付きの頂点を最小化する条件は、以下のとおりとなります。

$$
H_{B}=B \sum_{v} x_{v}
$$

$B<A$ となるように定数を選択します。少なくとも1つの辺が色付きの頂点に接続するようにするためです。

参考資料

Andrew Lucas “Ising formulations ofmanyNPproblems” arXiv:1302.5843