The quantum mechanical superposition principle enables a quantum computer to perform certain computations very much more efficiently than any classical computer. Thus it appears that a quantum computer could perform exponential computational work in one operation, which gives us a hint of the underlying power of the method. But, if we are instead interested in some joint property held by all the function values, such as the function s period, this quantity can be extracted by an additional efficient quantum procedure known as the quantum Fourier transform. Therefore, any problem that can be reduced to finding the period of some function is a candidate for efficient solution by quantum computer.
Integer factorization is such a problem.