グローバー回転
===

次の3ステップによる量子回路をグローバー回転$G$と呼ぶ（『量子プログラミングの基礎』ではこれの最初に量子オラクル$O$を適用したものをグローバー回転と呼んでいる）．
1. アダマール変換$H^{\otimes n}$
2. 条件付き位相シフト$S_{\mathrm{cond}}$
3. アダマール変換$H^{\otimes n}$

但し，条件付き位相シフト$S_{\mathrm{cond}}$は次のようなユニタリ変換である．
\begin{align}
S_{\mathrm{cond}}\lvert 0\rangle &= \lvert 0\rangle \\
S_{\mathrm{cond}}\lvert x\rangle &= -\lvert x\rangle & (x \neq0)
\end{align}
ここで，$\lvert x\rangle$は計算基底$\{\lvert 0\rangle, \lvert 1\rangle, \dots, \lvert 2^n-1\rangle\}$を表す．

このように定められたグローバー回転$G$について，以下が成立する．
\begin{align}
G = 2\lvert\phi\rangle\langle\phi\rvert - I
\end{align}
但し，$\lvert\phi\rangle$は
\begin{align}
\lvert\phi\rangle = \frac{1}{\sqrt{2^n}}\sum_{x = 0}^{2^n - 1}\lvert x\rangle
\end{align}
という計算基底の等確率の混合である．
ここで，$\lvert\phi\rangle = H^{\otimes n}\lvert 0\rangle^{\otimes n}$と構成できることに注意する．

## 補題
### 条件付き位相シフト
条件付き位相シフト$S_{\mathrm{cond}}$は次のように表されることが簡単にわかる．
\begin{align}
S_{\mathrm{cond}} &= 2\lvert 0\rangle\langle 0\rvert - I_n
\end{align}
但し，$I_n$は恒等写像．

### アダマール変換
アダマール変換はユニタリかつエルミートである．
初めに，二次元ヒルベルト空間におけるアダマール変換$H$は
\begin{align}
H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}
\end{align}
なので，明らかにユニタリかつエルミートである．高次元においては，帰納的にユニタリかつエルミートであることが分かる．
これより，$H^2 = HH^\dagger = I$であることが分かる．

## 証明
\begin{align}
G &= H^{\otimes n} (2\lvert 0\rangle\langle 0\rvert - I) H^{\otimes n} \\
&= 2H^{\otimes n} \lvert 0\rangle\langle 0\rvert H^{\otimes n} - H^{\otimes n} I H^{\otimes n} \\
&= 2\lvert\phi\rangle\langle\phi\rvert - I.
\end{align}
最後の等号は$\lvert\phi\rangle = H^{\otimes n}\lvert 0\rangle^{\otimes n}$および$H^2 = I$であることから導かれる．