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

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?

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.