Quantum Algorithms

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

5 lessons16 exercises64 min

1. 01Deutsch–Jozsa: one query instead of manyThe first algorithm with a provable gap: is a function constant or balanced?14 min
2. 02Bernstein–Vazirani: read a hidden stringSame circuit shape, more useful result: recover an n-bit secret with one query.10 min
3. 03Grover's searchAmplitude amplification: find a marked item in √N steps, and why you must stop at the right time.14 min
4. 04QFT and phase estimationThe Fourier transform on amplitudes, and the routine that reads eigenphases: the engine inside Shor.14 min
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