Deutsch-Jozsa アルゴリズムの話。ドイチ-ジョサのアルゴリズム も参考にしたい。
$\ket{\psi_0} = \ket{0}^{\otimes n}\ket{1}$ として
\begin{align*}
\ket{\psi_1} &= H^{\otimes n + 1}\ket{\psi_0} \\
&= (H\ket{0})^{\otimes n} H\ket{1}
\end{align*}
を計算する。
\begin{align*}
\begin{cases}
H\ket{0} &= \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) \\
H\ket{1} &= \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})
\end{cases}
\end{align*}
であるので、
\begin{align*}
\ket{\psi_1} &= \frac{1}{\sqrt{2}^{n+1}}(\ket{0} + \ket{1})^{\otimes n} (\ket{0} - \ket{1}) \\
&= \frac{1}{\sqrt{2}^{n+1}} \left( (\ket{0} + \ket{1})^{\otimes n} \ket{0} - (\ket{0} + \ket{1})^{\otimes n} \ket{1} \right)
\tag{1}
\end{align*}
となる。
\begin{align*}
(\ket{0} + \ket{1})^{\otimes n} &= \sum_{i_1,\cdots, i_n \in \{0, 1\}} \ket{i_1\cdots i_n} \\
&= \overbrace{\ket{0\cdots 00} + \ket{0\cdots 01} + \ket{0\cdots 10} + \cdots + \ket{1\cdots 11}}^{2^n} \\
&= \sum_{x=0}^{2^n - 1} \ket{x}
\end{align*}
これを (1) 式に代入して
\begin{align*}
\ket{\psi_1} = \frac{1}{\sqrt{2}^{n+1}} \sum_{x=0}^{2^n - 1} \ket{x} (\ket{0} - \ket{1})
\end{align*}
を得る。
