CODEWITHSUNDEEP
encryptionquantum-computing
Bibhu Lamichhane
Bibhu Lamichhane

Reputation: 31

Why is shor's algorithm only effective in quantum computer?

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.

Upvotes: 3

Views: 657

Answers (1)

Ricoter
Ricoter

Reputation: 763

In short, Shor's algorithm to factor N consists of:

  1. Make a (bad) random guess g of a number that could have a common factor with N
  2. Find an even number p such that g^p = m*N+1
  3. Then g^(p/2)±1 is 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.

Upvotes: 2

Related Questions