3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Can we assume the function is periodic?, What is the domain and the image of the function? $\endgroup$
    – nir shahar
    Aug 10, 2021 at 5:59
  • $\begingroup$ 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. $\endgroup$ Aug 10, 2021 at 13:14

1 Answer 1

3
$\begingroup$

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.

Edited To Add:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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