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

  • $\begingroup$ why should the QFT applied to such a superposition give the correct factor? $\endgroup$ – glS Feb 16 at 16:15
  • $\begingroup$ 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? $\endgroup$ – Matthew Giles Feb 16 at 16:21

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.