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


Please Refer to Pages 236 and 239, Quantum Computation and Quantum Information by Nielsen and Chuang


1 Answer 1


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.

Your second question is also unclear. What inverse are you talking about? The inverse of DFT or QFT or both? The identity in (1) is just a straight-up calculation without any inverses. You can also check page 237 Eq5.64. There they hint why this identity holds. Below, I give more details on what is stated on page 237.

We want to show the following holds, \begin{equation} \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 . \end{equation} We expand $|\hat f(\ell)\rangle$ in (1). By the definition we have \begin{equation} \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. \end{equation} 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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.