Quantum Algorithms

What quantum computers are good for

An interactive lesson with 7 steps, about 6 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Quantum speed-ups come from interference, and only for special problems.
• Grover: search in about $\frac{\pi}{4}\sqrt N$ steps (quadratic speed-up).
• Shor: efficient factoring, which threatens RSA and motivates post-quantum cryptography.

Steps

1. A common myth
2. Grover’s search
3. Grover’s rotation
4. Grover, bar by bar
5. Grover against a key
6. What breaks?
7. Shor’s algorithm