Translation by $s \in G$ is diagonal in the Fourier basis

Question

Let $G$ be any finite abelian group and let $P_s$ be the map that sends $|x\rangle \to |x+s\rangle$. In the standard basis $\{|x\rangle : x \in G\}$, the matrix representation is a permutation matrix. I am having trouble showing $$F_GP_sF_G^{\dagger} = \sum_{\Psi \in \hat G} \Psi(s)|\Psi\rangle \langle\Psi|$$ Where $F_G$ is the QFT that maps $|x\rangle \to \frac{1}{\sqrt{|G|}}\sum_{\Psi \in \hat G} \Psi(x) |\Psi\rangle$.\

I'm assuming $G = \mathbb Z / N \mathbb Z$ and this is my computation this far: \begin{align*} F_GP_gF_G^* &= \frac{1}{N} \left (\sum_{x_1, y_1 \in \mathbb Z / N \mathbb Z} \omega_N^{x_1y_1} |x_1\rangle \langle y_1| \right ) \left (\sum_{x \in \mathbb Z / N \mathbb Z} |x+n\rangle \langle x| \right ) \left (\sum_{x_2, y_2 \in \mathbb Z / N\mathbb Z} \overline{\omega_N^{x_2y_2}} |x_2\rangle \langle y_2| \right )\\ &=\frac{1}{N} \left (\sum_{x_1, y_1 \in \mathbb Z / N\mathbb Z} \omega_N^{x_1y_1} |x_1\rangle \langle y_1| \right ) \left (\sum_{x_2, y_2 \in \mathbb Z / N\mathbb Z} \overline{\omega_N^{x_2y_2}} \left (\sum_{x \in \mathbb Z / N\mathbb Z} |x + n\rangle \langle x|\right ) |x_2\rangle \langle y_2|\right )\\ &=\frac{1}{N}\left (\sum_{x_1, y_1 \in \mathbb Z / N\mathbb Z} \omega_N^{x_1y_1} |x_1\rangle \langle y_1|\right ) \left (\sum_{x_2, y_2 \in \mathbb Z / N\mathbb Z} \overline{\omega_N^{x_2y_2}} |x_2 + n\rangle \langle y_2| \right )\\ &=\frac{1}{N}\left (\sum_{x_2, y_2 \in \mathbb Z / N \mathbb Z} \overline{\omega_N^{x_2y_2}} \left (\sum_{x_1, y_1 \in \mathbb Z / N\mathbb Z} \omega_N^{x_1y_1} |x_1\rangle \langle y_1| \right ) |x_2 + n\rangle \langle y_2|\right )\\ &=\frac{1}{N}\left (\sum_{x_2, y_2 \in \mathbb Z / N \mathbb Z} \overline{\omega_N^{x_2y_2}} \left (\sum_{x_1 \in \mathbb Z / N \mathbb Z} \omega_N^{x_1(x_2 + n)} |x_1\rangle \langle y_2|\right ) \right )\\ \end{align*} Where am I going wrong?

Answer 1

Your computation is correct but incomplete. You want to show that your last expression is diagonal so basically you want to "couple" the $x_1$ and $y_2$ indices. You do this by computing the $x_2$ sum. Using the property $\overline{\omega_N^{x_2y_2}} = \omega_N^{-x_2y_2}$ and switching the order of sums you can write $$\begin{multline} \frac{1}{N}\left (\sum_{x_2, y_2 \in \mathbb Z / N \mathbb Z} \overline{\omega_N^{x_2y_2}} \left (\sum_{x_1 \in \mathbb Z / N \mathbb Z} \omega_N^{x_1(x_2 + n)} |{x_1}\rangle \langle{y_2}|\right ) \right ) \\ = \frac{1}{N}\left (\sum_{y_2 \in \mathbb Z / N \mathbb Z} \sum_{x_1 \in \mathbb Z / N \mathbb Z} \omega_N^{x_1n}\sum_{x_2\in \mathbb Z / N \mathbb Z} \omega_N^{x_2(x_1-y_2)} |{x_1}\rangle \langle{y_2}| \right ) \end{multline}.$$ Now $\sum_{x_2\in \mathbb Z / N \mathbb Z} \omega_N^{x_2(x_1-y_2)} = \sum_{x_2\in \mathbb Z / N \mathbb Z} (\omega_N^{x_1-y_2})^{x_2}$ is a geometric sum of a root of unity. This equals $0$ if $\omega_N^{x_1-y_2} \neq 1$ (i.e. $x_1 \neq y_2$) and equals $N$ if $\omega_N^{x_1-y_2} = 1$ (i.e. $x_1 = y_2$) so $$\frac{1}{N}\left (\sum_{y_2 \in \mathbb Z / N \mathbb Z} \sum_{x_1 \in \mathbb Z / N \mathbb Z} \omega_N^{x_1n}\sum_{x_2\in \mathbb Z / N \mathbb Z} \omega_N^{x_2(x_1-y_2)} |{x_1}\rangle \langle{y_2}| \right ) = \sum_{x_1 \in \mathbb Z / N \mathbb Z} \omega_N^{x_1n} |{x_1}\rangle \langle{x_1}|$$ which is diagonal. For arbitrary finite abelian groups the computation is similar if you concretely identify $G$ as a direct product of cyclic groups using the structure theorem.