QAOA 定式化不等式問題 (Problems with Inequalities)

制約が等式ではなく不等式を含む問題です。スピン数の拡張により、等式のみを含む制約として書き直すことができます。

分割問題と同様に、これらのハミルトニアンでは、多数のスピンが必要であることがわかります。これにより、現在のハードウェアでの使用が制限される可能性があります。

集合被覆問題 (Set Cover)

下記の式を満たす集合 $U={1, \ldots, n}$ $V_{i} \subseteq U(i=1, \ldots, N)$ を考えます。

$$
U=\bigcup_{i=1}^{N} V_{\alpha}
$$

集合被覆問題は、その和集合が $U$ となる集合 $V{_i}s$ の最小数を求める問題です。$\alpha \in U$ が、複数回 $V_i$ に表れてもいいとする、厳密被覆問題を一般化したものです。

$x_i$ を、集合 $i$ が含まれていたら $1$、含まれていないなら $0$ のバイナリ変数とします。$x_{\alpha,m}$ を、もし、要素 $\alpha$ を含む $V_is$ の数が、$m \geq 1$ なら、$1$ そうでないなら、$0$ となるバイナリ変数とします。$H=H_{A}+H_{B}$ とします。

$U$ の要素は固定回含まれてなければならないことと、$\alpha$ が含まれていると主張した回数は、実際には $\alpha$ を要素として含めた $V_i$ の数と同じだという制約から、$H_A$ は、以下のようになります。

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

そして、含まれる $V_\alpha s$ を最小化します。

$$
H_{B}=B \sum_{i=1}^{N} x_{i}
$$

$0<B<A$ であることが、制約条件 $H_A$ を満たすために必要です。

$M \leq N$ を与えられた $U$ の要素を含む集合の最大値とすると、$N x_iS$ のスピンと $x{\alpha,m}$にたいして $n\lfloor 1+\log M\rfloor$ のスピンが必要です。合計のスピン数は、 $N+n\lfloor 1+\log M\rfloor$ となります。

$⌊　⌋$ は、床関数です。

整数重みのナップザック問題

ナップザック問題というのは、以下のような問題です。

$\alpha$ でラベル付けされ、重さが$w_\alpha$ 、価値が $c_\alpha$ である $N$ 個の物があり、合計の重さが $W$ だけを運べるのナップザックを持っているとします。 $x_\alpha$ を、ナップザックに入れる（１）かいれないか（０）を表すバイナリ変数とすると、ナップザックに入れられる重さは、以下のようになります。

$$
\mathcal{W}=\sum_{\alpha=1}^{N} w_{\alpha} x_{\alpha}
$$

そして、合計の価値は、以下のようになります。

$$
\mathcal{C}=\sum_{\alpha=1}^{N} c_{\alpha} x_{\alpha}
$$

$\mathcal{W} \leq W$ を満たす $\mathcal{C}$ の最大値を求めるという問題です。経済やファイナンスの分野でいろいろな応用が可能です。

$1 \leq n \leq W$ にたいする $y_n$ を、最終的な重さが $n$ であるときに、$1$ 、そうでないときに、$0$ となるバイナリ変数とします。$H=H_{A}+H_{B}$として、

$$
H_{A}=A\left(1-\sum_{n=1}^{W} y_{n}\right)^{2}+A\left(\sum_{n=1}^{W} n y_{n}-\sum_{\alpha} w_{\alpha} x_{\alpha}\right)^{2}
$$

は、重量が 1 つの値のみを取ることができ、ナップザック内の物のの重量を選んだ物の重量にするという制約条件です。

$H_B$ は、以下のようになります。

$$
H_{B}=-B \sum_{\alpha} c_{\alpha} x_{\alpha}
$$

$H_B$ が負になりすぎると、$H_A$ の制約を弱く破る解をみつけることが不可能になるため、$0<B \max \left(c_{\alpha}\right)<A$ であることが必要です。一つで、最大重量を越える物を入れることはできません。必要なスピン数は、$N+\lfloor 1+\log W\rfloor$ となります。