QAOA 定式化 彩色問題 (Coloring Problems)

グラフ彩色問題 (Graph Coloring)

無向グラフ $G = (V,E)$ を $n$ 種類の色で、同じ色の 2 つの頂点を結ぶ辺がないように、グラフの各頂点に特定の色を付けることは可能かという問題です。国境を共有する 2 つの国が同じ色を持たないように、地図の色付けに必要な色の数の問題の一般化と考えることができます。 もちろん、このケースでは、4色以上で、常に彩色が可能なことを証明できます。

各頂点 $v \in V$ と各色 $i \in [n]$ に対して、 頂点 $v$ が色 $i$ に塗られたとき$1$になり、そうでないとき$0$となるバイナリ変数を、$x_{v,i} \in \{ 0, 1\}$} とします。$A$ を正の定数として、エネルギー関数は以下のように表せます。

$$
H=A \sum_{v}\left(1-\sum_{i=1}^{n} x_{v, i}\right)^{2}+A \sum_{(u v) \in E} \sum_{i=1}^{n} x_{u, i} x_{v, i}
$$

第1項は、各頂点 が、一つの色のみが使われているという制約条件です。第２項は、各辺の両方の端点に同じ色が使われないという制約条件です。$H=$となる基底状態が存在していれば、$n$色塗り分け問題の解が存在します。たとえば、グラフ内の特定の頂点を色 1 に選択し、その隣接頂点の 1 つを色 2 に設定することで、色付けの間に置換対称性があるため、スピンの数をわずかに減らすことができます。 したがって、必要なスピンの総数は $nN$ です。

クリーク被覆問題 (Clique Cover)

無向グラフ $G = (V,E)$と$n$個の色が与えられたとき、各頂点に個別の色を割り当てます。
各色に対応する $V$ の部分集合を $W_1,\cdots,W_n$ とし、$Wi$ セット内の頂点間の辺の集合を、 $E_{W_1}\cdots E_{W_n}$とします。クリーク被覆問題は、$(W_i,E_{W_i})$ が各 $W_i$ の完全グラフであるかどうかという問題です。つまり、同じ色をつけた頂点の各集合はクリークを形成するかどうかという問題ということです。クリーク問題と同様の変数をもちいると、クリーク問題と似たハミルトニアンとなります。

$$
H=A \sum_{v}\left(1-\sum_{i=1}^{n} x_{v, i}\right)^{2}+B \sum_{i=1}^{n}\left[\frac{1}{2}\left(-1+\sum_{v} x_{v, i}\right) \sum_{v} x_{v, i}-\sum_{(u v) \in E} x_{u, i} x_{v, i}\right]
$$

最初の項は、頂点が厳密に 1 つの色を持つという制約条件です。2 番目の項は、$x_{v,i}$ の $v$ の合計が色 $i$ の頂点の合計なので、最初の合計は色$i$ である可能性のある辺の最大数になります。2 番目の合計は、実際にこの数のエッジが実際に存在するかどうかという条件です。
したがって、クリーク被覆問題が与えられた色付けによって解決される場合にのみ、$H = 0$ です。 $H = 0$ の基底状態が存在する場合、クリーク被覆問題の解けます。 正しい解を得るために必要な比率 A/B の条件は、クリーク問題と類似しています。 必要なスピンの総数は $nN$ です。

整数長ジョブスケジューリング問題 (Job Sequencing with Integer Lengths)

$m$個のコンピュータ・クラスタにたいして、$N$ 個のジョブがあるとし、おのおののジョブ $i$ の長さを、$L_i$ とします。クラスタ $\alpha$ のジョブの集合を、$V_\alpha$ とし、クラスタの長さを以下のように定義したときに、おのおのジョブを$\max \left(M_{\alpha}\right)$ を最小化するように、クラスタ内のコンピュータに割り当てるかという問題です。

$$
M_{\alpha} \equiv \sum_{i \in V_{\alpha}} L_{i}
$$

基本的に、これは、すべてのジョブを同時に実行すると、すべてのジョブが最短時間で実行を終了することを意味します。

$\alpha$ にたいする一般性をそこなわずに$M_{1} \geq M_{\alpha}$ と仮定できます。ジョブ $i$ がコンピュータ $\alpha$ に割り当てられたときに、$1$ となり、それ以外のときは、$0$ となる変数を $x_{i,\alpha}$ とします。$\alpha \neq 1$ $n \geq 0$ にたいして、$y_{n,\alpha}$ を、$M_1-M_\alpha=n$なら $1$ となる変数とします。

ハミルトニアンは、以下のようになり、

$$
H_{A}=A \sum_{i=1}^{N}\left(1-\sum_{\alpha} x_{i, \alpha}\right)^{2}+A \sum_{\alpha=1}^{m}\left(\sum_{n=1}^{\mathcal{M}} n y_{n, \alpha}+\sum_{i} L_{i}\left(x_{i, \alpha}-x_{i, 1}\right)\right)^{2}
$$

各ジョブは 1 台のコンピューターにのみ割り当てることができ、どのコンピューターもコンピューター 1 よりも長い合計の長さを持つことはできないようにしています。

\mathcal{M} はユーザーが選択する必要があり、$M_{1} \geq M_{\alpha}$という制約条件を満たすために必要な補助スピンの数に関連しています。最悪は、$N \max \left(L_{i}\right)$ で与えられます。$M_1$の最小最大長は、以下のようになります。

$$
H_{B}=B \sum_{i} L_{i} x_{i, 1}
$$

ナップザック問題の $a/B$ の制約と同じように、$0<B \max \left(L_{i}\right)<A$ とするが必要です。スピンの数は、$m N+(m-1)\lfloor 1+\log \mathcal{M}\rfloor$ です。

参考資料

Andrew Lucas “Ising formulations ofmanyNPproblems” arXiv:1302.5843