# What is the fastest classical "period-finding" algorithm that can replace the Quantum Fourier Transform in Shor's algorithm?

Shor's algorithm uses the Quantum Fourier Transform to find the period the function a^x mod N with "a" being a constant integer less than N and N being a semiprime. This function is periodic and has both a domain and image of all integers from 2 to N.

What is the fastest classical algorithm that could be used in place of the Quantum Fourier Transform in Shor's algorithm?

• Can we assume the function is periodic?, What is the domain and the image of the function? Aug 10, 2021 at 5:59
• Yes, the function is periodic and both the domain and image are integers from 2 to N. Specifically in Shor's algorithm the function is: a^x mod N with "a" being a constant integer less than N and N being a semiprime. Aug 10, 2021 at 13:14

It depends on what preconditions you know about the function, as pointed out by @nir shahir in the comments.

You might be interested in the Sparse Fourier Transform, which works when the periodic portion of the signal accounts for a significant portion of the total signal power.

The paper that broke this field open is:

A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. J. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, Proc. of the 2002 ACM Symposium on Theory of Computing (STOC-2002):152--161.

There's a more recent survey paper of later developments that looks like it might be a good starting point:

Anna C. Gilbert, Piotr Indyk, Mark Iwen, Ludwig Schmidt, “Recent Developments in the Sparse Fourier Transform: A compressed Fourier transform for big data”, IEEE Signal Process. Mag., 31(5): 91-100, 2014.

The question was originally about finding the period of arbitrary functions. OP later clarified that they mainly care about the function a^x mod N, which is not sufficiently sparse that you could use the Sparse Fourier Transform. (At least, you wouldn't get anything useful out of the Sparse Fourier Transform with only $$O((\log N)^k)$$ samples.) For a^x mod N the way N is defined in Shor's algorithm, you end up with a signal with $$O(\sqrt N)$$ harmonics, each of which contributes only approximately $$O(1/\sqrt N$$ of the total power.