QAOA 定式化整数計画問題

整数計画問題（Integer Linear Programming）は、整数計画問題は、与えられた線形制約式に整数条件がついた変数に対して，線形目的関数の値を最小化／最大化する問題です。

ベクトル $\mathbf{x}$ を構成する$N$個のバイナリ変数を、$x_{1}, \ldots, x_{N}$ とたときに、ベクトル $\mathbf{c}$ に対して、以下の制約条件を満たす $\mathbf{c} \cdot \mathbf{x}$ の最大値を求めるという問題です。

$$
\mathrm{Sx}=\mathrm{b}
$$

ここで、$S$ は、$m \times N$ 行列、$\mathbf{b}$ は、$m$ 個の要素を持つベクトルです。

与えられた制約条件のものとで利益を最大化するなど、多くの問題を扱うことができます。

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

$$
H_{A}=A \sum_{j=1}^{m}\left[b_{j}-\sum_{i=1}^{N} S_{j i} x_{i}\right]^{2}
$$

ここで、$A\gt0$ は定数です。

基底状態 $H_{A}=0$ は、制約条件 $\mathrm{Sx}=\mathbf{b}$ を満たすように作用します。

そして、$H_{B}$ を以下の通りとします。

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

$B \ll A$ は、もう一つの定数です。

$A/B$の制約を求めるために、$\mathrm{Sx}=\mathrm{b}$ を満たすある選択$\mathrm{x}$ があったとします。そのような選択にたいして、$-\Delta H_{B}$ 最大値は、原則として、$C$ を以下のとおりとして、$BC$ となります。

$$
\mathcal{C}=\sum_{i=1}^{N} \max \left(c_{i}, 0\right)
$$

$\Delta H_{A}$の最小値は、$S$ の特性に関係し、一つの制約条件を満たさず、できる限り小さく制約条件を満たさないときに、次の式で与えられます。

$$
\mathcal{S} \equiv \min_{\sigma{i} \in{0,1}, j}\left(\max \left[1, \frac{1}{2} \sum_{i}(-1)^{\sigma_{i}} S_{j i}\right]\right) .
$$

限界は、もっと、$S$、$b$の特性がわかれば決定でき、$ c_{i} $ と$S_{i j}$ が、$\mathrm{O}(1) $ 整数であるとき、$\mathcal{C} \leq N \max \left(c_{i}\right)$ かつ$\mathcal{S} \geq 1$ なら$\
A / B \gtrsim N$ となりますから、以下のようになります。

$$
\frac{A}{B} \geq \frac{\mathcal{C}}{\mathcal{S}}
$$

ハミルトニアンとしては、単純なものですが、$A/B$の制約条件については、十分注意しないといけません。