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

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.

• Which book? Which erratum? Where do you think is an additional error? Maybe normalizations don't matter? – Norbert Schuch May 19 at 19:51
• I'm voting to close this question as off-topic because it belongs on the quantum computing stack exchange. See quantumcomputing.stackexchange.com – John Duffield May 25 at 7:50

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.