I'm trying to solve the following problems that I have found in the book An Introduction to Quantum Computing by Phillip Kaye, but I don't know exactly where should I start. I would appreciate any help or extra hint.
Firstly, let me introduce you the notation used in the book. The operator that is the heart of the Grover's algorithm is $G = HU_{0^\perp}HU_f$, where $U_f$ is the operator that includes the function $f$ we are testing in the algorithm, but this is not relevant for the question. Let $U_{0^\perp}$ be defined as
$$ U_{0^\perp}:\left\{\begin{array}{l} \lvert x \rangle \mapsto -\lvert x \rangle , \quad x\ne 00...0\\ \lvert 00...0 \rangle \mapsto \lvert 00...0 \rangle \end{array}\right. $$
so if $V_0$ is the vector space spanned by $\lvert 00...0 \rangle$, $U_{0^\perp}$ applies a $-1$ phase shift to the vectors of the orthogonal vector space $V_{0^\perp}$.
Now, let
$$ \lvert\psi\rangle = H \lvert 00...0 \rangle , $$
therefore,
$$ HU_{0^\perp}H:\lvert\psi\rangle\mapsto\lvert\psi\rangle . $$
Let $V_{\psi^\perp}$ be the orthogonal vector space orthogonal to the one spanned by $\lvert\psi\rangle$, and then it is spanned from $H\lvert x \rangle$ for $x\ne00...0$. For such states, we have that
$$ HU_{0^\perp}H: H \lvert x \rangle \mapsto - H \lvert x \rangle , $$
and we can say that the operator $HU_{0^\perp}H$ applies a phase shift of $-1$ to vectors in $V_{\psi^\perp}$. If we define $U_{\psi^\perp} = HU_{0^\perp}H$, the Grover's algorithm is governed by $G = U_{\psi^\perp}U_f$.
Now that notation has been introduced, let's write the two problems I'm trying to solve:
- Problem 1
Let $\lvert \psi \rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N - 1}{\lvert x \rangle}$. Show that the operator $HU_{0^\perp}H$ can be written as $(2\lvert\psi\rangle\langle\psi\rvert - I)$.
- Problem 2
Prove that $U_{\psi^\perp}$ 'inverts about the mean'. More precisely, consider any superposition
$$ \lvert \phi \rangle = \sum_{x}{\alpha_x \lvert x \rangle} $$
where
$$ \mu = \dfrac{1}{N} \sum_{x}{\alpha_x} $$
is the mean of the amplitudes. Show that $U_{\psi^\perp}\lvert\phi\rangle = \sum_{x}{(\mu-\alpha_x)\lvert x \rangle}$.
Hint given in the book: Decompose $\lvert\phi\rangle = \alpha\lvert\psi\rangle + \beta\lvert\overline{\psi}\rangle$ where $\lvert\overline{\psi}\rangle$ is orthogonal to $\lvert\psi\rangle$.