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

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.

• – glS
Commented Apr 14, 2019 at 14:47
• also a very similar question asked on math.SE: math.stackexchange.com/q/3186357/173147
– glS
Commented Apr 14, 2019 at 15:38

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{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}

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.