# Understanding the diffusion operator in Grover's algorithm

I understand how Grover's algorithm works and its geometrical interpretation. However, I am struggling to understand the implementation of the diffusion operator. Whilst I know what the diffusion operator does, i.e. the reflection about the quantum state, I cannot see why we need to apply Hadamard gates before and after the actual reflection.

For example, if we want to realize the reflection (diffusion) about the state $$|++\rangle$$, we implement the operator in terms of $$H^{\otimes 2} (2|00\rangle \langle00| - I) H^{\otimes 2}$$. Why do we have to go from $$|+\rangle$$ to $$|0\rangle$$ to $$|+\rangle$$ again? In qiskit's textbook (Grover's algorithm - Chapter 2. Example) it is stated that "since this is a reflection about the state $$|s\rangle$$, where $$s$$ is our superposition state, we want to add a negative phase to every state orthogonal to $$|s\rangle$$". Why exactly are we interested to add the phase to the orthogonal states?, i.e. flip all the states except $$|00\rangle$$?

I've already searched a lot and while this question may seem that it was already asked before, I would like someone to give an explanation from both an intuition point of view and a mathematical one.

• The best intuition for Grover's search I've seen is at github.com/microsoft/QuantumKatas/blob/main/tutorials/… - it helps you view each iteration as a pair of reflections. After this, it's a matter of convincing yourself that the diffusion operator is a reflection about the mean, and Hadamards are the part that converts |00> to "the mean" (equal superposition of all states in the search space) and vice versa, and that 2|00><00| - I is reflection about |00> Commented Mar 21 at 22:43

## 1 Answer

In Grover's algorithm, and in general in amplitude amplification, diffusion is a reflection about the initial state $$|\psi_0\rangle$$. Which means that we can write the diffusion operator as $$D=2| \psi_0 \rangle \langle \psi_0 | - I$$

In Grover's algorithm we start with a uniform superposition of all basis states $$| \psi_0 \rangle = H^{\otimes n}|0\rangle$$ So, $$D=2H^{\otimes n}|0\rangle \langle 0 |H^{\otimes n} - I$$ But, $$H$$ is its inverse. That means, $$I=H^{\otimes n}H^{\otimes n}$$ And hence, $$D=H^{\otimes n}(2|0\rangle \langle 0 | - I)H^{\otimes n}$$

So, it is a reflection about $$|0\rangle$$ state sandwiched by two layers of Hadamard gates.

• Thank you, I got it! Commented Mar 22 at 18:53
• I was reading again the mathematical steps and I have one question. When we do $H^{\otimes n}H^{\otimes n}$ we get $nI_n$, where $I_n$ is the identity matrix of order $n$ and $n$ is a multiplicative factor that we get from the multiplication of the two Hadamards. So, why isn't that $n$ taken in consideration in the steps before factoring on the left side and right side the Hadamard gates? Commented Mar 23 at 19:13
• In quantum computing, we define Hadamard gate to be $\frac{1}{\sqrt{2}}\left( {\begin{array}{*{20}{c}} 1&1\\ 1&-1 \end{array}} \right)$ .See here for example. Commented Mar 23 at 23:59
• Oh, right! I forgot about the $\frac{1}{\sqrt{2}}$. Thank you! Commented Mar 24 at 8:05