Simon のアルゴリズムに突入。サイモンのアルゴリズム も参考にしたい。
$s \in \{0,1\}^n$ に対し、$f_s: \{0,1\}^n \to \{0,1\}^n$ を考える。
オラクル $f_s$ に対するユニタリゲートは・・・書籍のは誤植っぽく見える書き方だが、ここまでの書き方に倣うと $x \in \{0,1\}^n$ に対し、$\ket{x}\ket{0}^{\otimes n} \xrightarrow{U_f} \ket{x}\ket{f_s (x)}$ と定義されるものとしたほうがやや読みやすい (Qiskit textbook での説明では量子レジスタに入る値として $\ket{0} = \ket{00\cdots 0}$ と見ているようだ)。このうち、q_0, ..., q_3 などで表されるレジスタ 1 に $\ket{x}$ が入り、q_4, ..., q_7 などで表されるレジスタ 2 に $\ket{0}^{\otimes n}$ が入ることになる。
なかなか数式で表現するのが難しいが、アダマールゲートのテンソル積は前半 $n$ 個の量子ビットに作用し、$U_f$ ゲートは全体に作用する形で式が進む。
$a,b,c \in \{0,1\}$ の時 $(a \oplus b)c = (ac) \oplus (bc)$ なる分配法則が成立することに注意し、Qiskit (19) - らんだむな記憶 を踏まえつつ、以下の式を $\mod 2$ での式とすると、
\begin{align*}
(x \oplus s)\cdot y \mod 2&= \sum_{i=1}^n (x_i \oplus s_i) y_i \mod 2\\
&= \sum_{i=1}^n (x_i y_i \oplus s_i y_i) \mod 2 \\
&= \bigoplus_{i=1}^n (x_i y_i \oplus s_i y_i) \\
&=(\bigoplus_{i=1}^n x_i y_i) \oplus (\bigoplus_{i=1}^n s_i y_i) \\
&=(\sum_{i=1}^n x_i y_i \mod 2) \oplus (\sum_{i=1}^n s_i y_i \mod 2) \\
&= (x\cdot y \mod 2) \oplus (s\cdot y \mod 2)
\end{align*}
を得る。よって
\begin{align*}
(-1)^{x\cdot y} + (-1)^{(x \oplus s)\cdot y} = (-1)^{x\cdot y} + (-1)^{(x\cdot y) \oplus (s\cdot y)}
\tag{1}
\end{align*}
と書ける。$x\cdot y \equiv 0 \mod 2$ の時、$s\cdot y \equiv 0 \mod 2$ で (1) 式の値は $2$ となり生き残る。$x\cdot y \equiv 1 \mod 2$ の時、$s\cdot y \equiv 0 \mod 2$ で (1) 式の値は $-2$ となり生き残る。
\begin{align*}
\alpha(y,x) = \frac{1}{2^n}[(-1)^{x\cdot y} + (-1)^{(x \oplus s)\cdot y}]
\end{align*}
と置くと、$s\cdot y \equiv 0 \mod 2$ の時のみ $\alpha(y,x)$ が生き残ることになり、このような条件を満たす $y$ が測定されることになる。
これで p.124 まで進んだ。
