“Quantum information and quantum computation”: quantum period finding algorithm

Question

The procedure for a quantum period-finding algorithm is described on page 236 of "Quantum Computation and Quantum Information" by Isaac Chuang and Michael Nielsen. In step 3 of the procedure, authors introduce state $|\hat f(l)> = \frac{1}{r} \sum_{x=0}^{r-1} \exp(-2 \pi i lx /r) |f(x)>$. In excercise 5.20 we are asked to relate that result to canonical form of Fourier transform of descrite function $ \hat f(l) = \frac{1}{N} \sum_{x=0}^{N-1} \exp (- 2 \pi l x /N)$. This is fairly easy since we are given a hint that $$ \sum_{k \in \{ 0,r,2r,\dots,N-r \}} \exp(2 \pi ikl/N) = \sqrt \frac{N}{r} $$ if $l$ is an integer multiple of $N/r$.

But this is clearly not true and that is even stated in errata* list for that book. There should be no square root in that last equation.

Does it mean that there is also a mistake in step 3 of that algorithm? I doubt that authors wouldn't include that in errata if that was a case, but there is something clearly missing in reasoning presented by the authors.

*http://www.michaelnielsen.org/qcqi/errata/errata/errata.html

Answer 1

To answer my own question: step three and forth of the quantum period-finding algorithm are correct. In step three we do following approximation: $$\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x>|f(x)> \approx \frac{1}{\sqrt{r N}}\sum_{l=0}^{r-1}\sum_{x=0}^{N-1} \exp(2 \pi i lx/r) |x>|\hat f (l)) > $$ If we use $|\hat f(l)> = \frac{1}{\sqrt r} \sum_{x=0}^{r-1} \exp(-2 \pi i lx /r) |f(x)>$ we get: $$\frac{1}{\sqrt{r N}}\sum_{l=0}^{r-1}\sum_{x=0}^{N-1} \exp(2 \pi i lx/r) |x>(\frac{1}{\sqrt r} \sum_{y=0}^{r-1} \exp(-2 \pi i ly /r) |f(y)>) = \\ = \frac{1}{r\sqrt{N}}\sum_{x=0}^{N-1}\sum_{y=0}^{r-1}[\sum_{l=0}^{r-1}\exp( \frac{2 \pi i l}{r}(x-y))]|x>|f(y)>$$ $$\frac{1}{r\sqrt{N}}\sum_{x=0}^{N-1}\sum_{y=0}^{r-1}[\sum_{l=0}^{r-1}\exp( \frac{2 \pi i l}{r}(x-y))]|x>|f(y)> = \frac{1}{r\sqrt{N}}\sum_{x=0}^{N-1}\sum_{y=0}^{r-1}r \delta_{x,y}^{\mod(r)}|x>|f(y)>$$ Which reduces to $\frac{1}{\sqrt{N}} \sum_{x=0}^{N} |x>|f(x)>$, as it should.

In a fourth step we do an inverse fourier transform : $$\frac{1}{\sqrt{r N}}\sum_{l=0}^{r-1}\sum_{x=0}^{N-1} \exp(2 \pi lx/r) |x>|\hat f (l)) > \rightarrow \frac{1}{2^t \sqrt{r }}\sum_{l=0}^{r-1}\sum_{x=0}^{N-1} \exp(2 \pi i \frac{lx}{r}) (\sum_{y=0}^{N-1} \exp(- 2 \pi i \frac{xy}{N-1}) |y>)|\hat f (l)) >$$ $$\frac{1}{N \sqrt{r }}\sum_{l=0}^{r-1} \sum_{y=0}^{N} (\sum_{x=0}^{N} \exp( \frac{2 \pi i x}{N}(\frac{Nl}{r} -y)) |y>|\hat f (l)) > = \frac{1}{N \sqrt{r }}\sum_{l=0}^{r-1} \sum_{y=0}^{N} N \delta_{NL/r,y} |y>|\hat f (l)) > \\=\frac{1}{ \sqrt{r }}\sum_{l=0}^{r-1} |NL/r>|\hat f (l)) > $$ Which is also correct.

Apparently, the formula I was referring to in my question isn't used. And simply $$|\hat f(l)> = \frac{1}{\sqrt r} \sum_{x=0}^{r-1} \exp(-2 \pi i lx /r) |f(x)>$$. $$| \hat f(l)> = \frac{1}{\sqrt N} \sum_{x=0}^{N-1} \exp (- 2 \pi l x /N)| f(x)>$$ These two equation aren't equivalent. Which was source of my confusion.