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

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.

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