# Grover's Algorithm - Diffusion Matrix [closed]

In the Grover's Algorithm, the diffusion matrix $$D$$ is defined as:

$$\begin{cases} D_{ij}=\frac{2}{N} \quad \text{ if } i \neq j \\ D_{ii}=-1+\frac{2}{N} \end{cases}$$

And then it goes on to say "$$D$$ can be implemented as $$D = FRF$$", where

$$\begin{cases} R_{ij}= 0 \quad \text{ if } i \neq j \\ R_{ii}=1 \quad \text{ if } i=0 \quad \text{ & } \quad R_{ii} = -1 \quad \text{ if } i \neq 0 \end{cases}$$

and

$$F_{ij} = 2^{-\frac{n}{2}} \cdot (-1)^{\bar{i} \cdot \bar{j}}$$ where $$\bar{i}$$ is the binary representation of $$i$$, and $$\bar{i} \cdot \bar{j}$$ is the bitwise dot product of the two $$n$$ bit strings $$\bar{i}$$ and $$\bar{j}$$.

I have a few questions in relation to this set up, and they are all more or less connected:

1. $$D$$, based on its definition, seems very easy to implement. Why does the paper say it can be implemented as $$FRF$$? Most probably I am overlooking something.
2. For the definition of $$R$$, we have the case for $$i = 0$$. Just to clarify, does the paper use a zero-based array indexing?
3. In the definition of $$F$$, we have an exponent of $$-\frac{n}{2}$$. What happens if $$n$$ is odd? I am basically trying to make sure that $$-\frac{n}{2}$$ may not be an integer.
4. How is the bitwise dot product computed? As an example, if i = 111 and j = 011 (here i and j are already in the binary form), then is i.j = 011? Do we compute it back as an integer base 10 and compute $$(-1)^3=-1$$?

1. "seems very easy to implement". It might look quite a simple form, but the way to specify how to implement it is to give a quantum circuit for it. That is what $$FRF$$ sets you on the road to doing.
3. Nothing special happens of $$n$$ is odd. There's no reason that $$2^{-n/2}$$ needs to be an integer. Indeed the simplest possible case ($$n=1$$) is the (hopefully) familiar Hadamard gate.
4. You should think of the $$i$$ and $$j$$ like vectors that you're doing an inner product between $$i\cdot j=(1,1,1)\cdot(0,1,1)=1\times 0+1\times 1+1\times 1=2$$