# Prove that the Quantum Fourier Transform satisfies $F_N(\sum_x |xr \rangle) \simeq \sum_y |y N/r \rangle$ when $r$ divides $N$

Before I start, this is a homework question, but I have spent the last 7 hours on it and gotten nowhere. I will mention what I've tried and noticed, but it's not much. At this point, I'm wondering if there isn't a typo somewhere...

The QFT (Quantum Fourier Transform) for $$n$$ qubits can be expressed in matrix form as (where $$N = 2^n$$):

$$\begin{pmatrix} \omega_N^{0 \cdot 0} & \cdots & \omega_N^{0 \cdot (N-1)} \\ \vdots & & \vdots \\ \omega_N^{(N-1) \cdot 0} & \cdots & \omega_N^{(N-1) \cdot (N-1)} \end{pmatrix}$$

The $$\omega_N = e^{i\frac{2 \pi}{N}}$$ denotes the $$N$$-th complex root of $$1$$.

I have to show the following relation, where $$r$$ divides $$N$$:

$$F_N\left(\sqrt{\frac{r}{N}} \sum_{x=0}^{\frac{N}{r} - 1} |xr \rangle\right) = \sqrt{\frac{1}{r}} \sum_{x=0}^{r-1} |x \frac{N}{r} \rangle$$

My two main ways of approaching this have been to rewrite the sum to come as close as possible to the expression on the right and then apply the QFT; and to directly apply the QFT to the terms in the sum. I know that $$|x\rangle$$ can be written as a column vector with a $$1$$ in the $$x+1$$ position, and I can see that we if we write $$N = \lambda r$$, then instead of having a $$1$$ every $$r$$ positions we get an $$r$$ every $$\lambda$$ positions in the RHS.

I've also drawn the unit circle in Argand's plane (the complex plane) and tried to see how the roots may interact between them, but once again to no avail, although I have obtained some neat formulas from that.

If $$F$$ denotes the QFT operation, then by definition $$\sqrt N F|j\rangle=\sum_k \omega^{jk}|k\rangle$$.
By linearity, you therefore have $$F\left(\sum_{x=0}^{N/r-1}|xr\rangle\right)= \sum_{x=0}^{N/r-1}F|xr\rangle =\frac{1}{\sqrt N}\sum_{y=0}^{N-1}\left(\sum_{x=0}^{N/r-1}\omega_N^{xyr}\right)|y\rangle.$$ Now by assumption $$r\mid N$$, and thus $$m\equiv N/r\in\mathbb N$$. Using the usual formulas for the geometric series we see that $$\sum_{x=0}^{m-1}\omega_N^{xyr}= \sum_{x=0}^{m-1}\exp\left(\frac{2\pi i}{m}xy\right)= %\frac{e^{2\pi i y}-1}{e^{2\pi i y/m}-1}, m \delta_{y\in m\mathbb Z},$$ and thus $$F\left(\sum_{x=0}^{N/r-1}|xr\rangle\right) =\frac{m}{\sqrt N}\sum_{y=0}^{N-1} \delta_{y\in m\mathbb Z}|y\rangle =\frac{m}{\sqrt N}\sum_{k=0}^{r-1} |kN/r\rangle.$$ Multiplying by $$\sqrt{1/m}$$ the above expression you get the result.