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

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!

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$$.
• Thank you very much for your help. It seems that the coefficient before $|m\rangle$ corresponds to the imaginary part of a period-$f$ fourier transform. However, in the paper, a period $P$ fourier transform is performed on $|\Psi_2\rangle$. I really don't have an idea on the connection between these two things. Could you please offer me some hints? Jun 1 at 1:41
• The paper says they do a Fourier transform of period $f$ "In Step 4, we apply the Fourier transform on a sine (cosine) of period $f$ and phase shift $\theta$" - this is what you asked in your question, I believe. Jun 1 at 14:12