Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I understand in Shor's algorithm we use quantum computers to find the period of a function which can then be used to find N, and we increase the probability of observing the state with the correct period with a Fourier transform. However, why can't we have a superposition of every possible factor and use a Fourier transform to increase the probability of observing the correct factor?
Hopefully someone can help answer (I'm trying to understand this for my EPQ).
A QFT can't arbitrarily raise the probability of any state you want to any value you want. Once you create a superposition, you need to find some way to make destructive interference occur between the states you don't want, and construct interference between the states you do want. Finding ways to do this is essentially the entire field of quantum algorithms.
If you don't find some way to use the structure of a specific problem, the best you can do is Grover's algorithm. For factoring, Grover's algorithm would run in time $O(N^{1/4})$ (for a number $N$) which is worse than the classical number field sieve! So you can use a superposition of factors, but a) you don't really need the QFT, and b) it's not efficient.
The QFT is well-suited to period finding for abelian groups because the phases it produces, $\{e^{2\pi i j/N}\}_{j=0}^{N-1}$, are themselves an abelian group. There is a perspective where the QFT is seen as an application of representation theory, transforming elements of a group into their representations. This is where I recommend you look if you want a deep understanding on why the QFT works well. Otherwise, I would just say that period-finding for abelian groups simply happens to be a problem for which it is relatively easy to create the necessary interference, and a QFT is an important component of that process.
