Introduction: Quantum Speed-Ups
Quantum computers need special algorithms to exploit their power. Two landmark algorithms showed what's possible: Shor's algorithm for factoring and Grover's algorithm for search.
Shor's Algorithm (1994)
Factoring an \(n\)-bit number:
- Classical: \(O(e^{n^{1/3}})\) — exponential time
- Quantum: \(O(n^3)\) — polynomial time!
This breaks RSA encryption. Key insight: factoring reduces to period-finding, which quantum computers do efficiently via quantum Fourier transform.
Grover's Algorithm (1996)
Searching an unstructured database of \(N\) items:
- Classical: \(O(N)\) — must check each item
- Quantum: \(O(\sqrt{N})\) — quadratic speed-up
Uses amplitude amplification: the target state's amplitude grows with each iteration while others shrink.
Other Quantum Applications
- Quantum simulation of molecules and materials
- Optimization problems (quantum annealing)
- Machine learning (quantum neural networks)
The Quantum Connection
Shor's algorithm is what made governments and companies invest billions in quantum computing—the ability to break modern cryptography. Grover's algorithm proves quadratic speed-ups are possible for generic problems. These algorithms represent a new paradigm of computation based on quantum physics.