Peter Shor's factoring algorithm, discovered in 1994, sparked both excitement and concern about quantum computing's potential to break RSA encryption. Now, over 30 years later, where do we stand?
The Promise
Shor's algorithm offers exponential speedup for integer factorization:
- Classical factoring: Takes exponential time for large numbers
- Shor's algorithm: Polynomial time on a quantum computer
- Impact: Would break RSA, DSA, and elliptic curve cryptography
- Timeline predicted: Many experts said 10-20 years in the 2000s
The Reality Check
Despite massive investment and progress, we're still far from cryptographically relevant quantum computers:
Current Capabilities
The largest numbers factored by quantum computers:
- 2019: 35 = 5 × 7 (using 20 qubits)
- 2021: 51 = 3 × 17 (using a different approach)
- 2025: Still stuck in double digits
What We Need
To break RSA-2048 (current standard), estimates suggest:
- Logical qubits needed: 4,000-8,000
- Physical qubits needed: Millions (due to error correction)
- Gate fidelity required: 99.9%+ consistently
- Coherence time: Hours to days of stable computation
The Engineering Challenges
Several fundamental obstacles remain:
Error Rates
Current quantum computers have error rates around 0.1-1% per operation. Shor's algorithm requires millions of operations, making error correction essential but expensive.
Scalability
Building quantum computers with millions of qubits involves unprecedented engineering challenges in cooling, control electronics, and quantum interconnects.
Algorithm Overhead
Real implementations of Shor's algorithm require significant overhead for:
- Quantum error correction codes
- Magic state distillation
- Fault-tolerant gate synthesis
- Classical pre- and post-processing
The Silver Lining
While cryptographically relevant quantum computers remain elusive, the threat has driven important developments:
- Post-quantum cryptography: New encryption methods resistant to quantum attacks
- Cryptographic agility: Systems designed to upgrade encryption algorithms
- Hybrid approaches: Combining classical and quantum-resistant methods
Looking Forward
Honest assessment suggests we're still decades away from quantum computers that can break modern cryptography. But this doesn't mean we should ignore the threat—the transition to post-quantum cryptography takes time, and better to be prepared.
Shor's algorithm remains one of quantum computing's greatest theoretical achievements. Whether it becomes a practical tool or remains an elegant proof of quantum advantage depends on solving some of the hardest engineering problems of our time.