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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.