4

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?

glS
  • 27,510
  • 7
  • 37
  • 125
Guangliang
  • 237
  • 1
  • 7

1 Answers1

2

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$.

Quantum Mechanic
  • 4,719
  • 5
  • 26