I am following the 5.4.1 Period-Finding Algorithm in Nielsen and Chuang as shown below: enter image description here

My confusion lies with the second expression of point 3 in the procedure. Why is the second expression an approximation as opposed to just being equal to the first expression in point 3?

Nielsen and Chuang states on the next page that "the approximate equality in step 3 is required because $2^t$ may not be an integer multiple of r in general". But when I work through the following steps, I don't see exactly why $2^t$ must be an integer multiple of r for the equality to hold. Consider:

$$\frac{1}{\sqrt{r2^t}} \sum_{\ell=0}^{r-1}\sum_{x=0}^{2^t-1} e^{2\pi i \ell x/r} |x\rangle |\hat{f}(\ell)\rangle$$

We know by the definition of $|\hat{f}(\ell)\rangle$ in the image above,

$$|\hat{f}(\ell)\rangle = \frac{1}{\sqrt{r}}\sum_{s = 0}^{r-1} e^{-2\pi i\ell s/r} |f(s)\rangle$$ (I use $s$ as the index instead of $x$ because $x$ is already used as an index in the first expression.) Anyways, now plugging this in to the first expression, we get:

$$\frac{1}{r\sqrt{2^t}} \sum_{s=0}^{r-1}\sum_{x=0}^{2^t-1}\sum_{\ell=0}^{r-1} \left( e^{2\pi \ell(x-s)/r}\right) |x\rangle |f(s)\rangle$$

Now, we know that $g(x, s) = \sum_{\ell=0}^{r-1} e^{2\pi \ell(x-s)/r} = r$ if $r|(x-s)$ and $0$ otherwise. Also, let $x \equiv s_2 (mod \> r)$. So for every $x$ in the summation, there is an $s = s_2$ meaning that $g(x, s_2) = r$ and $g(x, s) = 0$ for every other $s \neq s_2$. This means that:

$$\frac{1}{r\sqrt{2^t}} \sum_{s=0}^{r-1}\sum_{x=0}^{2^t-1}\sum_{\ell=0}^{r-1} \left( e^{2\pi \ell(x-s)/r}\right) |x\rangle |f(s)\rangle = \frac{1}{2^t}\sum_{x=0}^{2^t-1} |x\rangle |f(x)\rangle$$

Regardless of whether $2^t$ is a multiple of $r$, this equality holds. However, Nielsen and Chuang is stating that its an approximation, being equal only if $r|2^t$. What exactly am I missing here? Perhaps I'm making some assumption that is not true in the work above?

  • 2
    $\begingroup$ I think this is just an unclear explanation/error in the textbook. The inverse fourier transform in step 4 will not produce exactly $|\ell/r\rangle$, only an approximation, unless $r$ divides $2^t$. I think step 3 is exactly correct and the approximation is between step 3 and step 4. $\endgroup$ – Sam Jaques May 8 at 16:13
  • $\begingroup$ also remember you are techincally working in a binary system when applying the inverse transform, so when moving real numbers encoded back into binary registers the accuracy is limited by the closest binary representation, so if $r|2^t$ you can get an exact binary representation of the number. $\endgroup$ – Sam Palmer May 15 at 14:24

Your Answer

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

Browse other questions tagged or ask your own question.