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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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