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}$$


$$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 Answer 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.

  2. Yes, it's 0-based indexing.

  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 $$


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