In Nielsen and Chuang's description of Quantum order-finding algorithm, the 3rd step of the procedure says $$\frac1{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle|x^j\mod N\rangle \approx \frac1{\sqrt{r2^t}}\sum_{s=0}^{r-1}\sum_{j=0}^{2^t-1}e^{2\pi isj/r}|j\rangle|u_s\rangle.$$

Why isn't this an equation but an approximation? In fact, the Exercise 5.13 of Nielsen and Chuang proved $$\frac1{\sqrt r}\sum_{s=0}^{r-1} e^{2\pi isk/r}|u_s\rangle = |x^k \mod N\rangle.$$ Did I miss something here?


1 Answer 1


This approximation is addressed in the text after the period-finding algorithm, where it says that the problem is that $2^t$ may not be an integer multiple of the period $r$. As addressed in this related answer, there is no approximation in step 3 per se, but there is definitely an approximation between steps 3 and 4 in that the inverse Fourier transform won't behave perfectly without $2^t$ being a multipole of $r$.

  • 1
    $\begingroup$ Thanks for pointing out the approximation in step 4. I missed that. $\endgroup$
    – Guangliang
    Mar 11, 2022 at 21:05

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.