How to understand intuitively the Grover diffusion operator?

Question

According to the tutorial https://qiskit.org/textbook/ch-algorithms/grover.html I understand the mathematical principle of diffusion operator:

$$ \begin{equation} \begin{split} U_s&=2\left|s\right\rangle\left\langle s\right|-I \\ &=H^{\otimes n}U_0H^{\otimes n} \\ &=H^{\otimes n}\left(2\left|0\right\rangle\left\langle 0\right|-I\right)H^{\otimes n} \\ &=H^{\otimes n}\begin{bmatrix}1 & & & \\ & -1 & & \\ & & \ddots & \\ & & & -1\end{bmatrix}H^{\otimes n} \end{split} \end{equation} $$

For example, for two qubits

$$\left|s\right\rangle=\frac{1}{2}\left(\left|00\right\rangle+\left|01\right\rangle-\left|10\right\rangle+\left|11\right\rangle\right)=\frac{1}{2} \begin{pmatrix}1 \\ 1 \\ -1 \\ 1 \end{pmatrix}$$

applying the diffusion operator and we got

$$H^{\otimes 2}U_0H^{\otimes 2}\frac{1}{2} \begin{pmatrix}1 \\ 1 \\ -1 \\ 1 \end{pmatrix}=\begin{pmatrix}0 \\ 0 \\ 1 \\ 0 \end{pmatrix}$$

where $$H^{\otimes 2}=\begin{bmatrix}1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\1 & -1 & -1 & 1 \end{bmatrix}$$

So far this transformation is working well, it reflected the states of $s$ as expected. But it is difficult for me to understand the role played by the Hadamard gate here. How to prove or explain the following equation?

$$2\left|s\right\rangle\left\langle s\right|-I=H^{\otimes n}\left(2\left|0\right\rangle\left\langle 0\right|-I\right)H^{\otimes n}$$

or

$$ \left|s\right\rangle\left\langle s\right|=H^{\otimes n}\left|0\right\rangle\left\langle 0\right|H^{\otimes n} $$

Answer 1

It is often described as flipping the number around the mean. Lets take example with real numbers (normally these are complex numbers). For example, we have an array of 4 elements and we want to find element 3. We will start in an equal superposition. We have : $$|\psi\rangle = [\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}]$$ When we apply $U_\omega$ we will flip ("add a minus") to the 3rd number : $$|\psi\rangle = [\frac{1}{2}, \frac{1}{2}, -\frac{1}{2}, \frac{1}{2}]$$ When we apply Grover's diffusion operator, we take the mean/average : $$a = \frac{3*\frac{1}{2}-\frac{1}{2}}{4}=\frac{1}{4}$$ When we do the inversion around the mean of a number $v$, we do $-v+2*a$ which gives us : $$-\frac{1}{2}+(2*\frac{1}{4})=0$$ and $$-(-\frac{1}{2})+(2*\frac{1}{4})=1$$. If we do this for every element, this gives us : $$|\psi\rangle = [0, 0, 1, 0]$$ As you can see, we just increased the probability to measure the correct element and decreased the probability of the incorrect elements. This of course is a very simple example, but it demonstrates the effect really well. This is the same example as in the section 6.4 of quantum computing for computer scientists. If you have any more questions, please write a coment !

Answer 2

Like @Jonathcraft mentioned, the diffusion operator inverts the probability amplitudes about their mean. What is equally important to note is that the inversion about the mean is the same as a reflection of the state-vector about the state $|u\rangle = \frac{1}{2^{n/2}}\sum_x\lvert x\rangle$, which is the equal superposition of all the basis states for an n-qubit system.

To understand this, consider the general state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$:

• Flipping the amplitudes about the mean ($\mu = \frac{\alpha+\beta}{2}$) would yield the state $|\psi\prime\rangle = \beta|0\rangle + \alpha|1\rangle$.
• To reflect about the state $|u\rangle = \frac{1}{\sqrt{2}}{|0\rangle}+\frac{1}{\sqrt{2}}{|1\rangle}$, you would first have to find the angle between $|\psi\rangle$ and $|u\rangle$, and then rotate $|\psi\rangle$ by twice that angle. You can verify using the general $2\times 2$ rotation matrix that this yields $|\psi\prime\rangle$.

Now, to answer your question about the presence of the Hadamard Gate -

When you want to reflect a given state about the equal superposition over all basis states $|u\rangle$, the easy way to think about it is using these 3 steps:

1. Transform $|u\rangle$ into $|0\rangle^n$ - This is achieved by applying the Hadamard Transform to all $n$ qubits.
2. Reflect your vector (which would also have been transformed by the application of the Hadamard transform) about $|0\rangle^n$. The matrix for this is $diag_n(1, -1, -1, ..., -1)$.
3. Transform $|0\rangle ^n$ back to $|u\rangle$ to reverse what you did in the first step. Since the Hadamard gate is its own inverse, this is equivalent to repeating Step 1.

Putting it all together, the diffusion operator is given by:

$$ H^{\otimes n} \begin{bmatrix}1 & & & \\ & -1 & & \\ & & \ddots & \\ & & & -1\end{bmatrix} H^{\otimes n} $$