書籍 p.114 に謎の式が出てくる。
\begin{align*}
H^{\otimes n} \ket{x} = \frac{1}{\sqrt{2}^n} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\ket{y}
\tag{1}
\end{align*}
が気になるので確認してみよう。ここで $\ket{x}$ は $n$ 量子ビットのテンソル積であることに注意する。また以下の計算で明らかであるが、$x \cdot y$ はこのコンテキストでは内積ではないものとして扱っている。・・・のだが、ニールセン&チャン I p.49 によるなら、そのままビットごとの内積と見ても良さそうだ。実際 Qiskit (19) - らんだむな記憶 で見るように、内積と見ても、2 を法とする内積として見ても式の結果は同じになる。
$\otimes$ について書籍では XOR と書いてあるが、ニールセン&チャンでは 2 を法とする和と書かれている。どちらでも計算としては同じことだが、状況に応じて読み替えられると良いのだろう。
$n=1$ の時:
\begin{align*}
\frac{1}{\sqrt{2}} \sum_{y=0}^{1} (-1)^{x\cdot y}\ket{y} = \frac{1}{\sqrt{2}}((-1)^{x\cdot 0} \ket{0} + (-1)^{x\cdot 1} \ket{1})
\end{align*}
となる。$x = x_1 x_2 \cdots x_k$ とする時、$y = 0$ は $y = 000\cdots 0$ であり、$x\cdot 0 = (x_1 \cdot 0) \oplus \cdots \oplus (x_k \cdot 0) = 0 \oplus \cdots \oplus 0 = 0$ で、$y=1$ は $100\cdots 0$ なので $x\cdot 1 = x_1 \oplus 0 \oplus 0 \cdots 0 \oplus 0 = x_1$ である。よって、
\begin{align*}
\frac{1}{\sqrt{2}} \sum_{y=0}^{1} (-1)^{x\cdot y}\ket{y} = \frac{1}{\sqrt{2}}(\ket{0} + (-1)^{x_0} \ket{1})
\end{align*}
を得る。$x$ は 1 量子ビットであるので、$x = \ket{0}$ 或いは $x = \ket{1}$ であり、いずれのケースでも、$\frac{1}{\sqrt{2}}(\ket{0} + (-1)^{x_1} \ket{1}) = H \ket{x}$ である。以上から、$H \ket{x} = \frac{1}{\sqrt{2}} \sum_{y=0}^{1} (-1)^{x\cdot y}\ket{y}$ が成立している。
$n$ で成立するとする:
$\ket{x}$ を $n$ 量子ビットのテンソル積とし、$\ket{x^\prime} = \ket{x_1\cdots x_n x_{n+1}} = \ket{x}\ket{x_{n+1}}$ とする。同様に、$\ket{y}$ を $n$ 量子ビットのテンソル積とし、$\ket{y^\prime} = \ket{y_1\cdots y_n y_{n+1}} = \ket{y}\ket{y_{n+1}}$ とする。
仮定より、
\begin{align*}
H^{\otimes n+1} \ket{x^\prime} &= H^{\otimes n}\ket{x_1\cdots x_n}H\ket{x_{n+1}} \\
&= \frac{1}{\sqrt{2}^n} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\ket{y} H\ket{x_{n+1}}
\end{align*}
となる。
- $x_{n+1} = 0$ とする。
$H\ket{x_{n+1}} = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1})$ であるので、
\begin{align*}
H^{\otimes n+1} \ket{x^\prime} &= \frac{1}{\sqrt{2}^n} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\ket{y} \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) \\
& = \frac{1}{\sqrt{2}^{n+1}} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\ket{y} (\ket{0} + \ket{1})
\tag{2}
\end{align*}
である。$\ket{y} \ket{0} = \ket{y_1 y_2 \cdots y_n 0}$ であり、$\ket{y} \ket{1} = \ket{y_1 y_2 \cdots y_n 1}$ である。この新しい最下位ビットを $y_{n+1}$ と書くことにする。この時、$\oplus_{i=1}^n x_i y_i = \oplus_{i=1}^n x_i y_i \oplus 0\cdot y_{n+1} = \oplus_{i=1}^{n+1} x_i y_i$ が成立する。これを (2) 式に代入して、$n+1$ 量子ビットの式として
\begin{align*}
H^{\otimes n+1} \ket{x^\prime} & = \frac{1}{\sqrt{2}^{n+1}} \left( \underbrace{\sum_{y^\prime=0}^{2^n-1} (-1)^{x^\prime\cdot y^\prime}\ket{y^\prime}}_{y_{n+1} = 0} + \underbrace{\sum_{y^\prime=2^n}^{2^{n+1}-1} (-1)^{x^\prime\cdot y^\prime}\ket{y^\prime}}_{y_{n+1} = 1} \right)
\tag{3}
\end{align*}
を得る。
- $x_{n+1} = 1$ とする。
$H\ket{x_{n+1}} = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$ であるので、
\begin{align*}
H^{\otimes n+1} \ket{x^\prime} &= \frac{1}{\sqrt{2}^n} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\ket{y} \frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) \\
& = \frac{1}{\sqrt{2}^{n+1}} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\ket{y} (\ket{0} - \ket{1})
\tag{4}
\end{align*}
である。$\ket{y} \ket{0} = \ket{y_1 y_2 \cdots y_n 0}$ であり、$\ket{y} \ket{1} = \ket{y_1 y_2 \cdots y_n 1}$ である。この新しい最下位ビットを $y_{n+1}$ と書くことにする。
$y_{n+1} = 0$ の時、$\oplus_{i=1}^n x_i y_i = \oplus_{i=1}^n x_i y_i \oplus 1\cdot 0 = \oplus_{i=1}^{n+1} x_i y_i$ が成立する。この時、
\begin{align*}
\frac{1}{\sqrt{2}^{n+1}} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\ket{y}\ket{0} = \frac{1}{\sqrt{2}^{n+1}} \sum_{y^\prime=0}^{2^n-1} (-1)^{x^\prime\cdot y^\prime}\ket{y^\prime}
\tag{5}
\end{align*}
を得る。
$y_{n+1} = 1$ の時、$\oplus_{i=1}^{n+1} x_i y_i = \oplus_{i=1}^n x_i y_i \oplus 1\cdot 1 = \oplus_{i=1}^n x_i y_i \oplus 1$ が成立する。この時、$(-1)^{\oplus_{i=1}^{n+1} x_i y_i} = -(-1)^{\oplus_{i=1}^n x_i y_i}$ となる。($\oplus_{i=1}^n x_i y_i$ が 0 の場合と 1 の場合で見れば良い)
この時、
\begin{align*}
\frac{1}{\sqrt{2}^{n+1}} \sum_{y=0}^{2^n-1}(-1)^{x\cdot y}\ket{y} \ket{1} = - \frac{1}{\sqrt{2}^{n+1}} \sum_{y^\prime=2^n}^{2^{n+1}-1} (-1)^{x^\prime\cdot y^\prime}\ket{y^\prime}
\tag{6}
\end{align*}
を得る。(5) 式と (6) 式を (4) 式に代入して (3) 式を得る。帰納法により、(1) 式が一般の $n$ に対して成立することが分かった。
