まず最初に $C^{n-1}Z$ ゲートの意味について確認する。Toffoli ゲートを $CCX$ ゲートとも書いた。これと同様に $n-1$ 個の制御ビットが $\ket{1}$ の時に対象ビットに $Z$ ゲートが作用するものとする。つまり、$\ket{1}^{\otimes n}$ の時だけ値が変化し、$- \ket{1}^{\otimes n}$ を生成するようなゲートである。
Qiskit (42) —グローバーのアルゴリズム - らんだむな記憶 と同様に、すべての計算基底状態 $\ket{i_{n-1}\cdots i_0}\ (i_0,\cdots,i_{n-1} \in \{0,1\})$ に対して $U_s = 2 \ket{s}\bra{s} - I$ が成立することを確認する。
$H\ket{0} = \frac{\ket{0} + \ket{1}}{\sqrt{2}}$, $H\ket{1} = \frac{\ket{0} - \ket{1}}{\sqrt{2}}$ であるので、
$$
\begin{align*}
H^{\otimes n} \ket{i_{n-1}\cdots i_0} = \frac{1}{\sqrt{2^n}}(\ket{0}^{\otimes n} + \sum_{x=1}^{2^n-1} \alpha_x \ket{x}),\ \alpha_x \in \{-1,1\}
\end{align*}
$$
と書ける。また、$x \in \Z$ に対して、$\tilde{x}$ を $x$ の 2進展開におけるビットの反転、例えば、$010$ に対する $101$ と書くことにする時、
$$
\begin{align*}
X^{\otimes n} H^{\otimes n} \ket{i_{n-1}\cdots i_0} = \frac{1}{\sqrt{2^n}}(\ket{1}^{\otimes n} + \underbrace{\sum_{x=1}^{2^n-1} \alpha_x | \tilde{x} \rangle}_{\ket{1}^{\otimes n} は含まれない})
\end{align*}
$$
となる。よって、$C^{n-1}Z$ を適用した時、右辺第 1 項のみが影響を受け、第 2 項は変化しない。
以上を踏まえると、
$$
\begin{align*}
U_s \ket{i_{n-1}\cdots i_0} &= \frac{1}{\sqrt{2^n}} (H^{\otimes n} X^{\otimes n} \ket{1}^{\otimes n} - H^{\otimes n} X^{\otimes n} (\sum_{x=1}^{2^n-1} \alpha_x | \tilde{x} \rangle )) \\
&= \frac{1}{\sqrt{2^n}} \ket{s} - H^{\otimes n}\frac{1}{\sqrt{2^n}} \sum_{x=1}^{2^n-1} \alpha_x \ket{x} \\
&= \ket{s}\bra{s} \ket{i_{n-1}\cdots i_0} - H^{\otimes n} (H^{\otimes n} \ket{i_{n-1}\cdots i_0} - \frac{1}{\sqrt{2^n}} \ket{0}^{\otimes n}) \\
&= \ket{s}\bra{s} \ket{i_{n-1}\cdots i_0} - \ket{i_{n-1}\cdots i_0} + \ket{s}\bra{s} \ket{i_{n-1}\cdots i_0} \\
& = (2 \ket{s}\bra{s} - I) \ket{i_{n-1}\cdots i_0}
\end{align*}
$$
を得る。この関係が任意の計算基底状態について成立するので、$U_s = 2 \ket{s}\bra{s} - I$ が示された。
