1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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> $\endgroup$ Commented Mar 21 at 22:43

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you, I got it! $\endgroup$
    – aghin
    Commented Mar 22 at 18:53
  • $\begingroup$ 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? $\endgroup$
    – aghin
    Commented Mar 23 at 19:13
  • $\begingroup$ 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. $\endgroup$ Commented Mar 23 at 23:59
  • $\begingroup$ Oh, right! I forgot about the $\frac{1}{\sqrt{2}}$. Thank you! $\endgroup$
    – aghin
    Commented Mar 24 at 8:05

Your Answer

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

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