Shor’s Algorithm is arguably the most famous quantum algorithm. Discovered by Peter Shor in 1994, it solves a problem that forms the backbone of modern internet security: Prime Factorization.
If Deutsch-Jozsa was a "proof of concept," Shor’s Algorithm is the "killer app" that made governments and banks realize they needed to pay attention to quantum computing.
1. The Problem: Prime Factorization
Every number has a unique set of prime factors (e.g., $15 = 3 \times 5$).
For small numbers, this is easy.
For a number with 500+ digits, a classical supercomputer would take billions of years to find its factors.
Why does this matter? Most of our digital encryption (RSA) relies on the fact that multiplying two huge prime numbers is easy, but finding those primes from the result is nearly impossible. Shor’s Algorithm can find those primes in minutes.
2. How It Works (The "Period Finding" Trick)
Shor’s Algorithm doesn't just guess numbers. It turns the math problem into a geometry/wave problem. It uses a trick from number theory: finding the period (or frequency) of a specific mathematical function.
The Example: Let's factor 15.
Pick a random number ($a$): Let's pick $a = 7$.
Create a sequence: We calculate $(a^x \pmod{15})$ for $x = 1, 2, 3, 4, 5, 6...$
$7^1 \div 15$ leaves remainder 7
$7^2 (49) \div 15$ leaves remainder 4
$7^3 (343) \div 15$ leaves remainder 13
$7^4 (2401) \div 15$ leaves remainder 1 (The sequence starts over!)
$7^5 \dots$ leaves remainder 7
Find the Period ($r$): The remainders go $7, 4, 13, 1$. The sequence repeats every 4 steps. So, $r = 4$.
The Magic Formula: Once you have the period $r$, the factors are likely hidden in:
$$\gcd(a^{r/2} \pm 1, 15)$$$7^{4/2} - 1 = 49 - 1 = 48$
$7^{4/2} + 1 = 49 + 1 = 50$
Find the Greatest Common Divisor ($\gcd$):
$\gcd(48, 15) = \mathbf{3}$
$\gcd(50, 15) = \mathbf{5}$
Factors found: 3 and 5!
3. The Quantum Advantage
In the example above, finding the period ($r=4$) was easy. But for a 2048-bit number, the sequence is so long that a classical computer can't find the pattern before the sun burns out.
Quantum computers use the Quantum Fourier Transform (QFT):
They put all possible values of $x$ into superposition.
They pass them through the function simultaneously.
Like a prism splitting light into its constituent colors, the QFT highlights the frequency (the period $r$) of the sequence instantly through constructive interference.
4. Summary Table
| Feature | Classical Factorization | Shor’s Algorithm (Quantum) |
| Logic | Trial and error / Sieve methods | Period finding via interference |
| Time Complexity | Exponential (Too slow for RSA) | Polynomial (Very fast) |
| Impact | Secures the internet | Could "break" modern encryption |
5. Why haven't we broken Bitcoin/Banks yet?
Shor’s Algorithm requires perfect, error-corrected qubits. To break standard RSA-2048 encryption, we would need millions of physical qubits. Today’s best quantum computers only have a few hundred. We are likely a decade or more away from this being a real-world threat.
No comments:
Post a Comment
Note: only a member of this blog may post a comment.