I am learning about Shor's algorithm, a way to find factors of large numbers using a quantum computer. One of the main steps of this algorithm relies of the Quantum Fourier Transform (QFT) - a quantum version of Discrete Fourier Transform (DFT) - and its use in period finding. It seems to go that you take a periodic signal of length $M$ that has period $r$, and then the QFT will output a function that has period $\frac{M}{r}$. Here is an example - The function in the time domain and after the QFT
Can someone please explain why this happens? I am concentrating in DSP for undergrad, and I understand that any signal in the time domain is periodic with a DFT, due to the fact that it can be viewed as multiplied with an impulse train. However, I don't understand/remember learning why the DFT of a multiple periods of a periodic signal results in this period finding. Even further, in Shor's algo, ideally the periods are the only non-zero value. I would really appreciate if someone could give an intuitive approach to why period finding happens. Thanks!