On this page are some lecture notes that I created for courses I taught when I was a professor. They may be used and distributed freely, for individual study or by course instructors. They may not be sold.
Introduction to the theory of computing
This was a traditional undergraduate course on the theory of computing covering finite automata, context-free grammars, and Turing machines.
Lecture notes
All 20 lectures in one file (227 pages) [pdf]
- Course overview and mathematical foundations [pdf]
- Countability for languages; deterministic finite automata [pdf]
- Nondeterministic finite automata [pdf]
- Regular operations and regular expressions [pdf]
- Proving languages to be nonregular [pdf]
- Further discussion of regular languages [pdf]
- Context-free grammars and languages [pdf]
- Parse trees, ambiguity, and Chomsky normal form [pdf]
- Properties of context-free languages [pdf]
- Proving languages to be non-context free [pdf]
- Pushdown automata [pdf]
- Turing machines [pdf]
- Variants of Turing machines [pdf]
- Stack machines [pdf]
- Encodings; examples of decidable languages [pdf]
- Universal Turing machines and undecidable languages [pdf]
- More undecidable languages; reductions [pdf]
- Further discussion of computability [pdf]
- Time-bounded computations [pdf]
- NP, polynomial-time mapping reductions, and NP-completeness [pdf]
Latest update: October 19, 2020
©2020 John Watrous
Advanced topics in quantum information theory
This was an advanced graduate course on quantum information theory, including video lectures and notes, taught online (by necessity) in Spring 2020. The videos took a long time to create and I only managed to cover about half of the material I had intended for the course.
Lecture notes
All 8 lectures in one file (106 pages) [pdf]
- Conic programming [pdf]
- Max-relative entropy and conditional min-entropy [pdf]
- Smoothing and optimizing max-relative entropy [pdf]
- Regularization of the smoothed max-relative entropy [pdf]
- Min-relative entropy, conditional max-entropy, and hypothesis-testing relative entropy [pdf]
- Nonlocal games and Tsirelson’s theorem [pdf]
- A semidefinite program for the entangled bias of XOR games [pdf]
- The hierarchy of Navascues, Pironio, and Acin [pdf]
Latest update: March 14, 2021
©2021 John Watrous
Video lectures
- Conic programming [YouTube]
- Max-relative entropy and conditional min-entropy [YouTube]
- Smoothing and optimizing max-relative entropy [YouTube]
- Regularization of the smoothed max-relative entropy [YouTube]
- Min-relative entropy, conditional max-entropy, and hypothesis-testing relative entropy [YouTube]
- Nonlocal games and Tsirelson’s theorem [YouTube]
- A semidefinite program for the entangled bias of XOR games [YouTube]
- The hierarchy of Navascues, Pironio, and Acin [YouTube]
Theory of quantum information
This was an advanced graduate course on the theory of quantum information that I taught many times. Everything in these notes is done better in The Theory of Quantum Information, but here they are for old times’ sake.
All 22 lectures in one file (197 pages) [pdf]
Lectures
- Mathematical preliminaries (part 1) [pdf]
- Mathematical preliminaries (part 2) [pdf]
- States, measurements, and channels [pdf]
- Purifications and fidelity [pdf]
- Naimark’s theorem; characterizations of channels [pdf]
- Further remarks on measurements and channels [pdf]
- Semidefinite programming [pdf]
- Semidefinite programs for fidelity and optimal measurements [pdf]
- Entropy and compression [pdf]
- Continuity of von Neumann entropy; quantum relative entropy [pdf]
- Strong subadditivity of von Neumann entropy [pdf]
- Holevo’s theorem and Nayak’s bound [pdf]
- Majorization for real vectors and Hermitian operators [pdf]
- Separable operators [pdf]
- Separable mappings and the LOCC paradigm [pdf]
- Nielsen’s theorem on pure state entanglement transformation [pdf]
- Measures of entanglement [pdf]
- The partial transpose and its relationship to entanglement and distillation [pdf]
- LOCC and separable measurements [pdf]
- Channel distinguishability and the completely bounded trace norm [pdf]
- Alternate characterizations of the completely bounded trace norm [pdf]
- The finite quantum de Finetti theorem [pdf]
Latest update: December 1, 2011
©2011 John Watrous
Quantum computation
This was an introductory undergraduate course on quantum computing that I last taught in Spring 2006.
All 22 lectures in one file (139 pages) [pdf]
Lectures
- Overview of quantum information [pdf]
- Overview of quantum information (continued) [pdf]
- Superdense coding; quantum circuits, and partial measurements [pdf]
- Quantum teleportation; Deutsch’s algorithm [pdf]
- A simple searching algorithm; the Deutsch-Jozsa algorithm [pdf]
- Simon’s algorithm [pdf]
- Arithmetic/number-theoretic problems; reversible computation [pdf]
- Phase estimation [pdf]
- Phase estimation (continued); the quantum Fourier transform [pdf]
- Order finding [pdf]
- Order finding (continued); reducing factoring to order finding [pdf]
- Grover’s algorithm [pdf]
- Grover’s Algorithm (continued) [pdf]
- Quantum information revisited [pdf]
- Quantum information revisited (continued) [pdf]
- Quantum error correction [pdf]
- General quantum errors; CSS codes [pdf]
- Quantum key distribution [pdf]
- Impossibility of quantum bit commitment [pdf]
- Bell inequalities and nonlocality [pdf]
- Quantum communication complexity [pdf]
- Quantum computational complexity [pdf]
Latest update: April 11, 2006
©2006 John Watrous