Solving combinatorial optimization problems using QAOA の書き方がなかなか難しい。特に Appendix の「Constructing Problem Hamiltonian」から大分悩む。
textbook の言う $[n]$ は $[n] = \{ \varnothing, \{1\}, \{2\}, \cdots, \{n\}, \{1, 2\}, \{2, 3\}, \cdots, \{1, 2, \cdots, n\} \}$ と考えられる。つまり具体例として $[3] = \{ \varnothing, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{2, 3\}, \{1, 3\}, \{1, 2, 3\} \}$ である。
$n = 3$ として、本から例として損失関数 $C(x) = 2 x_2 - x_3 - 4 x_1 x_2 + 3 x_2 x_3$ をとってきてみる。
ここで、$\prod_{i \in \varnothing} x_i = \prod_{i \in \varnothing} (1 - x_i) = 1$ と約束することにする。
この時、上で持ち出した $C(x)$ は
$$
\begin{align*}
C(x) = \sum_{Q \subset [3]} w_Q \prod_{i \in Q} x_i \prod_{j \in \varnothing} (1 - x_j) = \sum_{Q \subset [3]} w_Q \prod_{i \in Q} x_i
\end{align*}
$$
の形になっている。これをもとに、ハミルトニアン
$$
\begin{align*}
H = \sum_{x \in \{0, 1\}^n} C(x) \ket{x} \bra{x}
\end{align*}
$$
を計算すると:
$$
\begin{align*}
H = \sum_{x \in \{0, 1\}^n} C(x) \ket{x} \bra{x}
\end{align*}
$$
となる。ここで、若い添字の量子ビットを右にしている。具体的に書き下すと以下のようになる:
$$
\begin{align*}
H &= 2 \ket{010} \bra{010} -2 \ket{011} \bra{011} - \ket{100} \bra{100} - \ket{101} \bra{101} + 4 \ket{110} \bra{110} \\
&= \begin{pmatrix}
0 & & & & & & & \\
& 0 & & & & & & \\
& & 2 & & & & & \\
& & & -2 & & & & \\
& & & & -1 & & & \\
& & & & & -1 & & \\
& & & & & & 4 & \\
& & & & & & & 0
\end{pmatrix} \\
& = [0, 0, 2, -2, -1, -1, 4, 0]
\tag{1}
\end{align*}
$$
ここで、$[a, b, c] = \begin{pmatrix} a & 0 & 0 \\ 0 & b & 0 \\ 0 & 0 & c \end{pmatrix}$ のような対角行列を表すものとする。numpy.linalg の svd が返す特異値からなる対角行列にインスパイアされた。
損失関数 $C(x)$ の定義において、$x_i \to \frac{1 - Z_i}{2}$ と置くことで、ハミルトニアンを $Z$ ゲートを使った展開ができる:
$$
\begin{align*}
H = 2 \frac{1 - Z_2}{2} - \frac{1 - Z_3}{2} - 4 \frac{1 - Z_1}{2} \frac{1 - Z_2}{2} + 3 \frac{1 - Z_2}{2} \frac{1 - Z_3}{2}
\end{align*}
$$
ここで、$A \otimes B \otimes C = ABC$ という略記を行うことにする。若い添字の量子ビットを右にして量子状態を記述することにしていたので、ゲートもそれに合わせる。例えば、$Z_3 = Z \otimes I \otimes I = ZII$ と書く。これを用いると、
$$
\begin{align*}
\!\!\!\!\!\!\!\! H = 2 \frac{III \!-\! IZI}{2} \!-\! \frac{III \!-\! ZII}{2} \!-\! 4 \frac{III \!-\! IIZ}{2} \frac{III \!-\! IZI}{2} \!+\! 3 \frac{III \!-\! IZI}{2} \frac{III \!-\! ZII}{2}
\tag{2}
\end{align*}
$$
となる。
