I'm trying to learn about quantum computing and came across Shor's algorithm to find prime factors of a number. I understand the math behind shor's algorithm but can't understand why it can't be implemented in a classical computer as it just seems like a mathematical formula.
1 Answers
In short, Shor's algorithm to factor N consists of:
- Make a (bad) random guess
gof a number that could have a common factor withN - Find an even number
psuch thatg^p = m*N+1 - Then
g^(p/2)±1is a much better guess
Step 1 and 3 can be efficiently done on a classical computer using Euclid's algorithm. But for the second step, you need a quantum computer to be efficient (a classical computer would need to try every power p, one by one. So yes, it's just math, but this is not faster than any other classical factorizing algorithm).
Shor's algorithm exploits the superposition principle of states used by qbits. This gives the possibility to evolve a function of the superposition all at once. Practically this means it can try all powers of p simultaneously.
Related