Quantum Algorithms

Deutsch–Jozsa, Bernstein–Vazirani, Grover, the QFT and phase estimation, and what Shor adds.

5 lessons14 exercises64 min215 XP

1. 01Deutsch–Jozsa: one query instead of manyThe first algorithm with a provable gap: is a function constant or balanced?14 min · 45 XP
2. 02Bernstein–Vazirani: read a hidden stringSame circuit shape, more useful result: recover an n-bit secret with one query.10 min · 35 XP
3. 03Grover's searchAmplitude amplification: find a marked item in √N steps, and why you must stop at the right time.14 min · 45 XP
4. 04QFT and phase estimationThe Fourier transform on amplitudes, and the routine that reads eigenphases: the engine inside Shor.14 min · 45 XP
5. 05Shor's algorithm: the overviewFactoring reduces to period finding; period finding is phase estimation. What is quantum, what is classical, what it costs.12 min · 45 XP