# Why do we use the quantum superposition for a period instead of factors in Shor's algorithm?

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).

• why should the QFT applied to such a superposition give the correct factor? – glS Feb 16 '19 at 16:15
• I suppose I'm asking how we can increase the probability of finding the correct period with a QFT but can't set up a superposition of possible factors and use QFT to give the correct one? – Matthew Giles Feb 16 '19 at 16:21

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.