Question Regarding Quantum Period-Finding Fourier Transform Approximation

Question

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

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?

Answer 1

I totally agree with the comments of Sam Jaques and Sam Palmer. I would just elaborate a little bit more on that.

The idea is that there is indeed no approximation in the step 3, but there is "some kind" of approximation between steps 3 and 4. To understand what kind of approximation it is and why $2^t$ should be an integer multiple of $r$, let's start from the step 3:

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

After rearrangement of the last expression and multiplication&division by $2^t$ in the power of the exponent, we get:

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

Now recall that the Fourier transform of the quantum state $|j\rangle$ is $\frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1} e^{2\pi i (j)\frac{x}{2^t}}|x\rangle$. Keep in mind that $(j)$ in the exponent's power is an integer, and $j$ in $|j\rangle$ is a binary representation of an integer $j$ by a quantum state (for instance, if $j=5$, then $|j\rangle = |1\rangle|0\rangle|1\rangle)$

Finally, notice that if $(l2^t/r)$ is integer (i.e. if $2^t$ is an integer multiple of $r$), then the expression inside round brackets from step 3 is exactly the Fourier transform of the state $|l2^t/r\rangle$:

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

In this case, there is no need for approximations at all, because moving from step 3 to step 4 we get

$$\frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\Big(FT (|l2^t/r\rangle)\Big)|\hat{f}(l)\rangle \rightarrow \frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}|l2^t/r\rangle|\hat{f}(l)\rangle$$

If you compare it with what is written in Nielsen and Chuang step 4, you will notice that $|\tilde{l/r}\rangle$ is exactly a quantum state $|l2^t/r\rangle$ for binary representation of integer $l2^t/r$.

But if $l2^t/r$ is not an integer (i.e. if $2^t$ is not an integer multiple of $r$), then

$$\frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1} e^{2\pi i (l2^t/r)\frac{x}{2^t}}|x\rangle \neq FT (|l2^t/r\rangle),$$

since for rational $l2^t/r$ there is no integer binary representation, and thus, no quantum state $|l2^t/r\rangle$. In this case, what we get from $|\tilde{l/r}\rangle$ in step 4 is only an approximation.

Additionally, you asked about period-finding specifically, but the same logic applies to the descriptions of order-finding algorithm and discrete logarithm algorithm in Nielsen and Chuang.