QAOA 定式化 分割問題
QAOAの応用（問題の定式化）では、何例かの定式化を紹介しました。ここでは、Andrew Lucas “Ising formulations ofmanyNPproblems” arXiv:1302.5843 を元に、他の定式化についてまとめてみます。
分割問題
数の分割 (Number Partitining)
$N$個の正の数 $S=\left\{n_{1}, \ldots, n_{N}\right\}$ を、要素の合計が同じになる素集合 $R$ と $S-R$ に分割できるかという問題です。例えば、$l_{1}, \ldots, n_{N}$ の価値を持つ資産を、二人に公平に分けることができるかという問題です。
$n_{i}(i=1, \ldots, N=|S|)$ 、$s_{i}=\pm 1$ として、
$$
H=A\left(\sum_{i=1}^{N} n_{i} s_{i}\right)^{2}
$$
を、エネルギー関数とします。$A>0$ は、正の定数です。
$H = 0$ となる解があるなら、+1 スピンの $n_i$ の合計と、-1 スピンの $n_i$ の合計は、同じになります。
グラフの分割 (Graph Partitioning)
偶数の頂点 $N=|V|$ を持つ無向グラフ $G=(V, E)$ を考えて、頂点を二分割し、分割した頂点の間を結ぶ辺の数を最小化するという問題です。
例えば、頂点は、$V={0,1,2,3}$ 、辺は、 $E={(0,1),(0,2),(1,2),(3,2)}$ といったグラフです。
イジング・スピン $s_i$ を、各頂点に配置し、+1 と -1 を、どちらの集合に属するかを表すものとします。
エネルギー関数は、2つからなり、
$$
H=H_{A}+H_{B}
$$
$$
H_{A}=A\left(\sum_{n=1}^{N} s_{i}\right)^{2}
$$
は、＋集合とー集合を同じにするとう成約条件です。
$$
H_{B}=B \sum_{(u v) \in E} \frac{1-s_{u} s_{v}}{2}
$$
は、異なった集合に属する頂点を結ぶ辺があったときに、Bだけエネルギーを与えるという条件です。もし、 $B>0$ なら、2つの集合のあいだの辺の数が最小化できます。$B<0$ なら最大化ができることになります。$\frac{1-s_{u} s_{v}}{2}$ は、頂点が同じ集合に属していれば、0 になり、異なっていれば、１ になるます。それを、各辺 $E$ の両側の頂点 ${(u v) \in E}$ について、合計を求めます。
$B<0$ を選択した場合、$B$ は、$H_A$ の制約条件を生かすために、十分小さな値にする必要があります。$B$ を大きくしすぎると、エネルギー関数は、$H_B$ だけで決まってしまうことになるからです。
$B$ の決め方は、$G$ の、最大次数（グラフの頂点に接合する辺の最大数）を、$\Delta$ として、以下のようになります。
$$
\frac{A}{B} \geq \frac{\min (2 \Delta, N)}{8}
$$
このように、定式化にあたって制約条件のハイパーパラメータの選択には、注意が必要です。
クリーク (Cliques)
無向グラフ 
https://ja.wikipedia.org/wiki/クリーク_(グラフ理論)
各頂点に配置したイジング・スピン $s_\alpha$ にたいして、バイナリ変数 $x_\alpha$ を以下のように定義します。つまり、ハミルトニアンではなくQUBO形式にするということです。
$$
x_{\alpha} \equiv \frac{s_{\alpha}+1}{2}
$$
$A, B>0$ として、QUBOは、以下のようになります。
$$
H=A\left(K-\sum_{v} x_{v}\right)^{2}+B\left[\frac{K(K-1)}{2}-\sum_{(u v) \in E} x_{u} x_{v}\right]
$$
大きさ $K$ のクリークが、存在すれば、$H=0$ となることは明らかです。しかし、その他の解に対して、 $H \neq 0$ となるとは限りません。もし、$n$ 個の $x_vs$ が１であったなら、$H$ の最小値は、以下のようになります。
$$
H_{\min }(n)=A(n-K)^{2}+B \frac{K(K-1)-n(n-1)}{2}=(n-K)\left[A(n-K)-B \frac{n+K-1}{2}\right]
$$
もっとも危険なのは、$n=1+K$ の場合です。$A \gt KB$ かつ $H_{min}(K+1)\gt 0$ の場合にそうなります。
グラフの中で、もっともおおきいクリークを探すには、上ののハミルトニアンに、 もっともおおきなクリークのサイズが $i$ であるときに、$1$ そうでないときは、$0$となる $y_{i}(i=2,\ldots, \Delta)$ という変数を追加して、
$$
H_{A}=A\left(1-\sum_{i=2}^{N} y_{i}\right)^{2}+A\left(\sum_{i=2}^{n} n y_{n}-\sum_{v} x_{v}\right)^{2}
$$
$$
H_{B}=B\left[\frac{1}{2}\left(\sum_{i=2}^{N} n y_{n}\right)\left(-1+\sum_{i=2}^{N} n y_{n}\right)-\sum_{(u v) \in E} x_{u} x_{v}\right]
$$
としたとき、 $H=H_{A}+H_{B}+H_{C}$ とします。
クリークは、$H_{A}=H_{B}=0$ でかつ基底状態となることから求められます。もし、$A/B$が十分大きくて、制約条件 $H_A=0$ が常時満たされるなら、上のハミルトニアンは、この条件を満たします。これは、$H_A$ の最初の項で $y_i = n$ の値を1つだけ選択するようにされ、2番目の項で$n$ 個の頂点を選択するように固定されていることに注意してください。次に、$H_B = 0$ は、クリークがあることを保証します。 上記の説明と同様に、負のエネルギー状態がない場合は $A> NB$ が必要であることがわかります。すべての基底状態がクリークであることがわかったので、もっとも $y_n$ が小さい状態を見つける必要があります。これは、$C>0$ である定数として、
$$
H_C=-C \sum_{v} x_{v}
$$
を選択することによって得られます。
$C$ が十分小さければ、基底状態のエネルギーは、$K$ をグラフの最大のクリークのサイズとして、 $H=-CK$ となります。$C$ の上限値は、以下のようになります。
$$
C<A-n B
$$
追加するスピンを N から logN に減らす
上の問題で、追加する必要がある余分な $y_i$ スピンの数を劇的に減らす工夫があります。
整数 $M$ を、以下のように定義します。
$$
2^{M} \leq N<2^{M+1}
$$
あるいは $M=\lfloor\log N\rfloor$ とします。$\lfloor \rfloor$ は、床関数です。
こうした場合、$M+1$ しか変数の数が必要なだけとなります。
$$
\sum_{n=1}^{N} n y_{n} \rightarrow \sum_{n=0}^{M-1} 2^{n} y_{n}+\left(N+1-2^{M}\right) y_{M}
$$
この工夫を使うと、上の問題を解くには、$N+1+\lfloor\log \Delta\rfloor$ だけのスピンで十分になります。
参考資料
Andrew Lucas “Ising formulations ofmanyNPproblems” arXiv:1302.5843
