# DFT like operation in the third step of Period finding and Discrete Logarithm algorithm

In the third step of the algorithm for discrete logarithm, the state $$|\hat{f}(l_1,l_2)\rangle=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi il_2j/r}|{f}(0,j)\rangle$$ is introduced which is stated to be the Fourier transform of $$|{f}(x_1,x_2)\rangle$$ and can be proven to be equal to $$\frac{1}{r}\sum_{x_1=0}^{r-1}\sum_{x_2=0}^{r-1}e^{-2\pi i(l_1x_1+l_2x_2)/r}|{f}(x_1,x_2)\rangle$$ as,

How do I make sense of the fact that $$|\hat{f}(l_1,l_2)\rangle$$ is the Fourier transform of $$|{f}(x_1,x_2)\rangle$$ ?

Discrete Logarithm Algorithm Procedure

In a similar argument with the period finding problem,

in the step 3 we introduce the state $$|\hat{f}(l)\rangle=\frac{1}{\sqrt{r}}\sum_{x=0}^{r-1}e^{-2\pi ilx/r}|f(x)\rangle$$ which is stated to be the Fourier transform of $$|f(x)\rangle$$.

The quantum Fourier transform on the state $$|j\rangle$$ is, $$QFT|j\rangle=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}|k\rangle$$ where $$N$$ is the dimension of the orthonormal basis. In my understanding the QFT is just DFT beng applied to the amplitudes of the quantum state, $$y_k=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}x_ke^{2\pi ijk/N}$$.

Are we just defining the state as $$|\hat{f}(l)\rangle=\frac{1}{\sqrt{r}}\sum_{x=0}^{r-1}e^{-2\pi ilx/r}|f(x)\rangle$$ as if we are taking DFT on the state $$|f(x)\rangle$$, then use the fact that taking the inverse results in $$|{f}(x)\rangle=\frac{1}{\sqrt{r}}\sum_{x=0}^{r-1}e^{2\pi ilx/r}|\hat{f}(l)\rangle$$ ?

Period Finding Algorithm Procedure

Your first question about making sense of $$| \hat f(\ell_1, \ell_2)\rangle$$ is at best vague. It is not clear what you want to know.
We want to show the following holds, $$$$\tag{1} |f(x)\rangle = \frac{1}{\sqrt{r}} \sum^{r-1}_{\ell=0}e^{2\pi i \ell x/r} |\hat f(\ell)\rangle .$$$$ We expand $$|\hat f(\ell)\rangle$$ in (1). By the definition we have $$$$\tag{2} |\hat f(\ell)\rangle = \frac{1}{\sqrt{r}} \sum^{r-1}_{y=0}e^{-2\pi i \ell y/r} |f(y)\rangle.$$$$ Plugging (2) into (1) yields
\begin{align} &\frac{1}{\sqrt{r}} \sum^{r-1}_{\ell=0}e^{2\pi i \ell x/r} \frac{1}{\sqrt{r}} \sum^{r-1}_{y=0}e^{-2\pi i \ell y/r} |f(y)\rangle \\ &=\frac{1}{r} \sum^{r-1}_{y=0}\sum^{r-1}_{\ell=0}e^{2\pi i \ell (x-y)/r} |f(y)\rangle \\ &= \frac{1}{r} \sum^{r-1}_{y=0}\left[\sum^{r-1}_{\ell=0} e^{2\pi i \ell (x-y)/r} \right] |f(y)\rangle. \end{align} Now we consider the quantity in the square brackets. \begin{align} \sum^{r-1}_{\ell=0} e^{2\pi i \ell (x-y)/r} = \sum^{r-1}_{\ell=0} \left (e^{2\pi i (x-y)/r}\right)^{\ell} = \begin{cases} r & \textrm{if } \ x-y =0, \\ 0 & \textrm{otherwise}. \end{cases} \end{align} Therefore, we have \begin{align} \frac{1}{r} \sum^{r-1}_{y=0}\left[\sum^{r-1}_{\ell=0} e^{2\pi i \ell (x-y)/r} \right] |f(y)\rangle =\frac{1}{r} \sum^{r-1}_{y=0} \left \{ \begin{array}{1} r & \textrm{if } x=y \\ 0 & \textrm{otherwise} \end{array} \right\} |f(y)\rangle = | f(x) \rangle. \end{align}