5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Hi @Chuck. Welcome to QCSE. What do you mean "by brute force?" Do you mean keeping a large table and searching for such a $k$? Remember $N$ is meant to be very large. $\endgroup$
    – Mark Spinelli
    Commented Oct 19, 2020 at 18:44
  • $\begingroup$ Hi @ Mark S. By brute force, I mean starting with k=1 and doing the calculation. Then increment k by 1 and repeating until a^k mod N = 1. I realize that in practice N can be very large. But what if N is around 10,000? How would I use an FFT to solve that problem? $\endgroup$
    – Chuck
    Commented Oct 19, 2020 at 19:51
  • $\begingroup$ The quantum Fourier transform (QFT) is performed in quantum superposition. You may be able to classically envision such a superposition as a time-series of a lookup table that stores pairs $(k, a^k\bmod N)$, and then perform a (classical) Fourier transform (FFT) on the lookup table, to find the period $r$ of the table. If I were you, to get intuition on the QFT, I would build such a table without hunting for a particular $k$. This "building the table" in a blind manner is close to the idea of quantum superposition. $\endgroup$
    – Mark Spinelli
    Commented Oct 19, 2020 at 20:52

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\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.