Links
Lecturers: Stefan Wolf, Lorenzo Laneve
Course overview
This course introduces quantum computation by first motivating quantum information operationally, then building the mathematical and physical model needed for quantum states, measurements, circuits, communication protocols, algorithms, and complexity classes. The summary keeps the computational viewpoint in focus while filling in the quantum-mechanical background needed to follow the algorithms.
Main topics
- what quantum informatics is: Stern-Gerlach experiment, quantum key distribution, Mach-Zehnder interferometer, quantum bits, and Aspect-Gisin-Zeilinger experiments
- information is physical: information theory, thermodynamics, Maxwell's demon, reversible computing, and the Toffoli gate
- from classical to quantum physics: black-body radiation, photoelectric effect, wave-particle dualism, and observables
- digression on operators: bounded and unbounded operators
- postulates of quantum mechanics: states, time evolution, observables, joint systems, trace, and density matrices
- qbits: one qbit, two qbits, CNOT, cloning, pseudo-cloning, pseudo-measurements, and n-qbit systems
- quantum communication: teleportation and superdense coding
- simple algorithms: reversible oracles, quantum parallelism, phase kickback, Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, and Simon
- pseudo-telepathy: Mermin's game, the Deutsch-Jozsa game, Kochen-Specker theorem, and pseudo-telepathy games
- Grover's algorithm: geometric picture and circuit
- Shor's algorithm: Quantum Fourier Transform, phase estimation, number theory, order finding, integer factoring, and discrete logarithms
- quantum complexity theory: classical complexity classes, bounded-error computation, BQP in PSPACE, extended Church-Turing thesis, QMA-style analogues of NP, and outlook