# Fourier transform and grover search iteration

For https://library.uoh.edu.iq/admin/ebooks/22831-quantum_computer_science.pdf#page=115 , how is fourier transform being used to determine the number of iteration used in grover search ?

The number of solutions you are searching for $$m$$ can be calculated by using the Quantum Counting algorithm. It uses the Quantum Fourier Transform. This would be my guess, but as they do not tell us specifically it is hard to say.

The Grover iterator is a unitary transformation with eigenvalues that are related to $$\frac{M}{N}$$. Thus, if you use the Grover iterator as the unitary in a phase estimation protocol (the one where you do lots of controlled-$$U^{2^k}$$ operations, followed by a Fourier transform on the control register), this will estimate the eigenvalue for you, and hence the value of $$M$$.

• is this how we find the period (order-finding problem using phase estimation mechanism) of the data in frequency domain through fourier transform ? If yes, then the grover search with some supplementary help from fourier transform might end up with high compute complexity cost of O(N^3) ?? Jul 24, 2023 at 5:20
• Could you explain more on how these chain of unitary operations transform eigenvalues from M/N to an approximated value of M ? Jul 24, 2023 at 5:51
• The eigenvalues of the unitary are $e^{\pm i\theta}$ where $\sin\theta=\sqrt{\frac{M}{N}}$. The whole point of phase estimation on a $t$-bit register is that with high probability it will output the best $t$-bit approximation to $\theta/(2\pi)$. (I have little desire to run through all the technicalities of phase estimation in a post here when it is well explained in most textbooks. Of course, if there is some specific part you're not clear about, please ask a specific questions.) Jul 24, 2023 at 6:58
• I need to study the maths for both conventional and iterative versions of quantum phase estimation. Jul 27, 2023 at 4:19