6

For learning purposes, I would like to write a classical version of Shor's algorithm. From what I have read, what makes this algorithm fast is the quantum FFT, which is used to find the period of the function $a^k \bmod N$ with the ultimate goal of finding the k that solves $a^k \bmod N = 1$.

Acknowledging that it would be impractically slow, I would like to write a version that uses the classical FFT. Certainly such an algorithm could factor small numbers.

What confuses me is that when I calculate the values of $a^k \bmod N$ to feed into the FFT, it is not that much harder skip the FFT and just find $a^k \bmod N = 1$ by brute force (similar to this question).

What am I missing here? Alternatively, if I had a black box that could calculate FFTs instantaneously, how would this change Shor's algorithm?

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
Chuck
  • 163
  • 3

1 Answers1

3

In Shor's (quantum) algorithm, you compute the modular exponent only a small number of times—far smaller than $N$. The algorithm is probabilistic, and if you're lucky you may compute it only once.

After the modular exponentiation step, in principle the qubits encode the value of $a^k\text{ mod }N$ for every $k$, but you can't just search through the wave function for a value of $1$. If you could do that (sometimes called "postselection"), you could do far more impressive things than factoring numbers, such as solving Circuit SAT in linear time by postselecting on the circuit's output being $1$. The problem is that you don't get to choose the outcome of your measurement, and with overwhelming probability you'll get an outcome that you didn't want.

When you simulate Shor's algorithm (or my attempt at a Circuit SAT solver) classically, there is probably no dramatically more efficient way to do it than actually computing every term of the wave function in the computational basis. Since you're doing all that work, you can check for the output you wanted at the same time—but if you do that you're no longer simulating a quantum algorithm, since that operation isn't permitted by the rules of quantum computation (and isn't permitted by the laws of physics as far as we can tell).

benrg
  • 898
  • 5
  • 3