In Preskill's notes on quantum information, he includes a section on the quantum Fourier transform (QFT) for period finding. Starting from the classical Fast FT over bitstrings, we can express any ket $|x\rangle \in |\{0,1\}^n\rangle$ as it's binary expansion $$x = \sum_i 2^i x_i\equiv (x_{n-1}x_{n-2}\cdots x_0.);\\ i \in \{0, ..., n-1\}$$

Then, the FFT phase factor, $xy/N$ where $N\equiv 2^n$. We define $[N]\equiv\{0,...,N-1\}$ and evaluate the phase factor as: $$ \frac{xy}{N} =\frac{1}{N}\big(\sum_{i\in[n]}2^ix_i\big) y \\ =\big(\sum_{i\in[n]}\frac{1}{2^n}2^i x_i\big) y \\ =\big(\sum_{i\in[n]}2^{(i-n)} x_i \big) y \\ =\frac{1}{2^n}x_0y + \frac{1}{2^{n-1}}x_1 y +\cdots+\frac{1}{2}x_{n-1}y \\ =x_0 (.y_{n-1}\cdots y_{0}) + x_1 (y_{n-1}.y_{n-2}\cdots y_0) +\cdots+x_{n-1}(y_{n-1}y_{n-2}\cdots y_1.y_0) $$

Then, Preskill (and others) make the claim that the terms in the product $\frac{xy}{N}$ when exponentiated are equivalent to: $$ =x_0 (.y_{n-1}\cdots y_{0}) + x_1 (.y_{n-2}\cdots y_0) +\cdots+x_{n-1}(.y_0) $$ Basically saying the terms in front of the decimal make no contribution to $\exp(2\pi i x y/N)/N$.

This is not at all obvious to me and I don't see anywhere that motivates this. It must be the result of the periodicity of the exponential about powers of two but I don't see it worked out anywhere and the index hauling gets unwieldy quickly. What calculation do I need to perform in order to get to this result?


1 Answer 1


Recall that $\exp(2\pi i x y /N)$ is $N$-periodic:

$$\exp(2\pi i x y / N) = \exp(2 \pi i (x y + N)/N).$$

Preskill's notes uses $N = 2^n$ and so in the product of $xy$ you can freely discard the terms that are multiples of $2^n$. Try to carry out the calculation yourself given the expressions for $x$ and $y$ in (6.51).

If the case with general $n$ is getting messy just try $n = 3$ and observe the pattern.


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.