Bernstein-Vazirani アルゴリズムに突入。ベルンシュタイン・ヴァジラニ アルゴリズム も参考にしたい。ここでも $a \cdot x$ はそれぞれの 2 進表現 $\{a_i\}$, $\{x_i\}$ に関する 2 を法とする内積 $\sum_i a_i x_i \mod 2$ として考える。
数式類は Deutsch-Jozsa アルゴリズムで出てきたものを再利用できるので、ほとんどそのまま読める。新しい式は以下だろう:
\begin{align*}
\frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^{a\cdot x + x \cdot y} = \delta_{ay}
\tag{1}
\end{align*}
精神衛生上の問題もあるので、確認しておこう。
$n=1$ の場合:
$a, y \in \{0, 1\}$ とする。
\begin{align*}
\frac{1}{2} \sum_{x=0}^{1} (-1)^{a\cdot x + x \cdot y} = \frac{1}{2} (1 + (-1)^{a+y})
\end{align*}
であるので、$a=y=0$ か $a=y=1$ の場合のみ右辺は 1 であり、それ以外では 0 である。よって右辺は $\delta_{ay}$ に等しい。
$n$ で成立するとする:
$a (= a_1 \cdots a_n),x,y \in \{0, 1\}^n$ とし、$a^\prime (= a_1 \cdots a_n a_{n+1}),x^\prime,y^\prime \in \{0, 1\}^{n+1}$ とする。
$a^\prime \cdot x^\prime = a\cdot x + a_{n+1} x_{n+1}$, $x^\prime \cdot y^\prime = x\cdot y + x_{n+1} y_{n+1}$ に注意する。また、$x^\prime < 2^n$ の時は $x_{n+1} = 0$ であり、$2^n \leq x^\prime < 2^{n+1}$ では $x_{n+1} = 1$ であることに注意する。
\begin{align*}
\sum_{x^\prime=0}^{2^{n+1}-1} (-1)^{a^\prime\cdot x^\prime + x^\prime \cdot y^\prime} = \sum_{x^\prime=0}^{2^n-1} + \sum_{x^\prime=2^n}^{2^{n+1}-1} (-1)^{a^\prime\cdot x^\prime + x^\prime \cdot y^\prime}
\tag{2}
\end{align*}
であるので、右辺第 1 項は仮定より $2^n \delta_{ay}$ となる。右辺第 2 項を見る。$x_{n+1}=1$ に注意すると
\begin{align*}
\sum_{x^\prime=2^n}^{2^{n+1}-1} (-1)^{a^\prime\cdot x^\prime + x^\prime \cdot y^\prime} & = \sum_{x=0}^{2^n-1} (-1)^{a\cdot x + x\cdot y + a_{n+1} + y_{n+1}} \\
& = (-1)^{a_{n+1} + y_{n+1}} \sum_{x=0}^{2^n-1} (-1)^{a\cdot x + x\cdot y} \\
&= 2^n (-1)^{a_{n+1} + y_{n+1}} \delta_{ay}
\tag{3}
\end{align*}
を得る。
(3) 式を (2) 式に代入して、
\begin{align*}
\sum_{x^\prime=0}^{2^{n+1}-1} (-1)^{a^\prime\cdot x^\prime + x^\prime \cdot y^\prime} = 2^n (1 + (-1)^{a_{n+1} + y_{n+1}}) \delta_{ay}
\end{align*}
を得る。これは $a_{n+1} = y_{n+1} = 0$ 或いは $a_{n+1} = y_{n+1} = 1$ の時 $2^{n+1} \delta_{ay} = 2^{n+1} \delta_{a^\prime y^\prime}$ であり、それ以外では $0 (= 2^{n+1} \delta_{a^\prime y^\prime})$ である。つまり、(2) 式の右辺は $2^{n+1} \delta_{a^\prime y^\prime}$ に等しい。よって帰納法より (1) 式が一般の $n$ に対して成立することが分かった。
p.122 まで完了。
