Prove that the operator $H U_{0^\perp}H$ can be expressed as $2|\psi\rangle\langle\psi|-I$

Question

I'm trying to solve the following problem related to the mathematical explanation of Grover's algorithm. Let $$ \lvert\psi\rangle = \dfrac{1}{\sqrt{N}} \sum_{x=0}^{N-1}{\lvert x \rangle} \,\text{,} $$ then prove that the operator $HU_{0^{\perp}}H$ can be expressed as $\left( 2\lvert\psi\rangle\langle\psi\rvert-I \right)$, where the operator $U_{0^\perp}$ is defined as $$ U_{0^\perp}:\lvert x\rangle\mapsto-\lvert x\rangle \quad \forall\lvert x\rangle \ne \lvert 00...0 \rangle $$

However, I'm not able to see which steps should I follow. This problem is from the book An Introduction to Quantum Computing by Phillip Kaye, but it does not give any hint to solve it. I hope anyone can at least tell me where should I begin to get the answer.

Answer 1

You can start by checking the action of the operator $2|0\rangle\langle0|-I$ on your quantum state $|x\rangle$.

1. If $|x\rangle = |0\rangle$, then $(2|0\rangle\langle0|-I)|0\rangle = |0\rangle$.

2. If $|x\rangle \neq |0\rangle$, then $(2|0\rangle\langle0|-I)|x\rangle = -|x\rangle$

Thus, you can see that the operator $2|0\rangle\langle0|-I$ shifts the phase of $|x\rangle$ if $|x\rangle \neq |0\rangle$.

After that, you do the expression $H^{\otimes n}(2|0\rangle\langle0|-I)H^{\otimes n}$ by applying the mathematical expression from right to left (i.e first you apply $(2|0\rangle\langle0|-I)$ to $H^{\otimes n}$ and then $H^{\otimes n}$ to the result of that). That should give you the operator $2|\psi\rangle\langle\psi|-I$. Mathematically this goes as following:

\begin{equation} \begin{aligned} D &= H^{\otimes n}(2|0\rangle\langle0|-I)H^{\otimes n} \\ &= 2 (H^{\otimes n}|0^{\otimes n}\rangle)(\langle0^{\otimes n}|H^{\otimes n}) -H^{\otimes n}IH^{\otimes n} \\ &= 2 (H^{\otimes n}|0^{\otimes n}\rangle)(H^{\otimes n}|0^{\otimes n}\rangle)^{\dagger} - H^{\otimes n}H^{\otimes n} \\ &= 2|\psi\rangle\langle\psi|-I \end{aligned} \end{equation}

if you notice that $HH=I$ and $|\psi\rangle = H^{\otimes n}|0^{\otimes n}\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1} |x\rangle$.

This operator $D$ is called the diffusion operator and is essentially the operator that, when applied to your oracle $O$ gives you Grover's operator $G$.

Hope this helps.