Calcuate $\langle x | D | y \rangle$ for arbitrary $x,y \in \{0,1\}^n$

Question

We are considering Grover's algorithm with a search space of size $2^n$ for an arbitrary integer $n$ for arbitrary $n$, and a unique marked element $x_0$.

Question: Calculate $\langle x | D | y \rangle$ for arbitrary $x,y \in \{0,1\}^n$

Answer: Using the expression $D = -(I-2|+^n\rangle\langle+^n|)$, we have

$$\langle x | D | y \rangle = \begin{cases} \frac{2}{N}-1 &\quad\text{if x=y}\\ \frac{2}{N} &\quad\text{if x $\neq$ y} \end{cases} $$

How has the equality $D = -(I-2|+\rangle\langle+|)$ been derived? Its from these notes https://people.maths.bris.ac.uk/~csxam/teaching/qc2020/lecturenotes.pdf

How do derive the split function? I cannot see the route to start to evaluate this.

Answer 1

Grover's Diffusion Operator $D$ can be written as $H^{\otimes n}U_0H^{\otimes n}$ where $U_0$ is the following matrix $$\begin{bmatrix}-1 & 0 & 0 &... & 0 \\ 0 & 1 & 0 & ... &0 \\.& . & 1 & ... & . \\.& . & . & ... & . \\0& 0 & 0 & ... & 1 \end{bmatrix}$$ The unitary $U_0$ has the property that $U_0|0^n\rangle = -|0^n\rangle$ and $U_0|\psi\rangle = -|\psi\rangle$.
Thus unitary $U_0$ can also be written as $2|0^n\rangle\langle0^n|-I$ as its matrix form can be expressed as: $$ \begin{bmatrix}1 & 0 & 0 &... & 0 \\ 0 & -1 & 0 & ... &0 \\.& . & -1 & ... & . \\.& . & . & ... & . \\0& 0 & 0 & ... & -1 \end{bmatrix} = 2 \begin{bmatrix}1 & 0 & 0 &... & 0 \\ 0 & 0 & 0 & ... &0 \\.& . & 0 & ... & . \\.& . & . & ... & . \\0& 0 & 0 & ... & 0 \end{bmatrix} - \begin{bmatrix}1 & 0 & 0 &... & 0 \\ 0 & 1 & 0 & ... &0 \\.& . & 1 & ... & . \\.& . & . & ... & . \\0& 0 & 0 & ... & 1 \end{bmatrix} $$ Now $D$ can be expressed as $$D=H^{\otimes n}U_0H^{\otimes n}=H^{\otimes n}(2|0^n\rangle\langle0^n|-I)H^{\otimes n}\\ = 2H^{\otimes n}|0^n\rangle\langle0^n|H^{\otimes n}-H^{\otimes n}IH^{\otimes n} \\ = 2(H|0\rangle\langle0|H)^{\otimes n} - I \\ = 2(|+\rangle\langle+|)^{\otimes n} -I \\ = 2|+^n\rangle\langle+^n| -I \\ = -(I - 2|+^n\rangle\langle+^n|)$$

I hope this derivation helps.