Why is quantum Fourier transform required in Shor's algorithm?

Question

I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem or period of modular exponentiation sequence of some random $x$ such that $1 < x < N$.

I have no problem regarding the idea of the algorithm. But I'm wondering if Shor’s algorithm creates such a sequence by repeated squaring (which is an efficient way classically). In my understanding, the term "efficient" means that the complexity of the algorithm is polynomial in time.

Given that there is an efficient way to create the sequence classically, can we not just add a little check for whether we have encountered $x^{r} = 1 \ \text{mod} N$? During the creation process, it should not increase complexity to exponential-time, right?

Why bother with quantum Fourier transform at all? Did I misunderstand it in some way?

Answer 1

The essential feature of this problem is that while both the quantum and classical algorithms can make use of the efficient classical function of calculating $a^k\text{ mod }N$, the issue is how many times does each have to evaluate the function.

For the classical algorithm you're suggesting, you'd calculate $a\text{ mod }N$, and $a^2\text{ mod }N$, and $a^3\text{ mod }N$, and so on, until you hit a repeating value. You have to perform $r$ evaluations, and $r$ could be quite large. Indeed, it could be $O(N)$. It's this large number of repetitions that kills this idea for the classical algorithm.

By comparison, the quantum algorithm only evaluates the order once. You then need the Quantum Fourier Transform in order to be able to compare all the simultaneously calculated values because you cannot access all of these values all at once. The QFT is what does all the magic.

Answer 2

Given that there is an efficient way to create the sequence classically, can we not just add a little check for whether we have encountered $x^{r} = 1 \ \text{mod} N$? During the creation process, it should not increase complexity to exponential-time, right?

Why bother with quantum Fourier transform at all? Did I misunderstand it in some way?

The answer to the above question is that there exists no known classical (non-quantum) algorithm that can find this period efficiently (in polynomial complexity). So that means there is no efficient classical algorithm to find the period of functions like $x = 2^r_{1} \ \text{mod} N$. That is not to say such a classical algorithm does not exist – just that no one knows such a classical algorithm.

The classical discrete Fourier transform has exponential complexity – however, the quantum version of that Fourier transform has polynomial complexity. So we do need to bother with the quantum Fourier transform.