Question about theorem 5 of the Quantum Counting, Brassard et al. paper

Question

In this paper, when proving theorem 5, the authors let $f = \frac{P\theta}{\pi}$ and claim they "apply the Fourier transform on a sine (cosine) of period $f$". However, I just could not find where the sine of cosine is. It seems that the previously mentioned $\sin((2m+1)\theta)$ does not have a period $f$.

Furthermore, they later claim that when $f$ is an integer and $f > 0$, $|\Psi_3\rangle$ could be expressed as some $a|f\rangle + b|P-f\rangle$. Where does this come from? I just could not derive it according to the formula of Fourier transform. Any help would be really appreciated!

Answer 1

The state on which the Fourier transform is being performed is defined in the paper as $$|\Psi_2\rangle\propto \sum_{m=0}^{P-1}\sin[(2m+1)\theta]|m\rangle=\sum_{m=0}^{P-1}\sin\left[2\pi f\frac{m}{P}+\pi\frac{f}{P}\right]|m\rangle\equiv\sum_{m=0}^{P-1}x_m|m\rangle.$$

We can compare this to the definition of a discrete Fourier transform with period $f$: $$X_f=\sum_{m=0}^{P-1}x_m e^{-2\pi i f\frac{m}{P}}=\sum_{m=0}^{P-1}x_m \left[\cos \left(2\pi f\frac{m}{P}\right)-i\sin \left(2\pi f\frac{m}{P}\right)\right].$$

By comparing these two expressions, we see that $\pi f/P$ adds a constant phase shift to the transformation, and that otherwise the imaginary part of the variable $X_f$ transformed with period $f$ is exactly the result of a Fourier transform.

The main message is that the Fourier transform is being done using the period $f$ by construction in order to obtain information from $|\Psi_2\rangle$.