15-859BB: Quantum Computation and Quantum Information 2018
Course bulletin board: Diderot
All course announcements, discussion, lecture notes, lecture videos, and homework will be on Diderot.
If you are not officially enrolled in the course but want to follow along, send email to cmuquantum2018@gmail.com, and we'll add you to Diderot.
Meetings time and place: Tuesday and Thursday, 1:30-2:50, GHC 4102 (entrance off The Helix)
First meeting: Tuesday September 4. Last meeting: Thursday December 6.
Instructor: Ryan O'Donnell
TA: Costin Bădescu
Office Hours: Ryan: Tuesdays 3pm-4:30pm (after class), GHC 7213. Costin: Mondays 3pm-4:30pm, location GHC 6207.
2015 version of the course
Weekly work
Lectures
- Lecture 1: 10500 Parallel Universes (pdf notes, video)
- Lecture 2: Rotate, Compute, Rotate (pdf notes, video)
- Lecture 3: Understanding and Measuring One Qubit (pdf notes, video)
- Lecture 4: Unitary Transformations and the Elitzur--Vaidman Bomb (pdf notes, video)
- Lecture 4.5: Discriminating Two Qubits (pdf notes, video)
- Lecture 5: Multi-Qubit Systems (pdf notes, video)
- Lecture 5.5: Multiplying by a Global Phase Doesn't Matter (pdf notes, video)
- Lecture 6: Partial Measurements and "Spooky Action at a Distance" (pdf notes, video)
- Lecture 7: The CHSH Game (pdf notes, video)
- Lecture 8: The No-Cloning Theorem, and Quantum Teleportation (pdf notes, video)
- Lecture 9: Quantum Money (pdf notes, video)
- Lecture 10: Basics of Quantum Computing (pdf notes, video)
- Lecture 11: Revealing XOR-patterns I (pdf notes, video)
- Lecture 12: Revealing XOR-patterns II (pdf notes, video)
- Lecture 13: Simon's Algorithm (pdf notes, video)
- Lecture 14: The Fourier Transform over Zn (pdf notes, video)
- Lecture 15: Period Finding (Simon's Algorithm over Zn) (pdf notes, video)
- Lecture 16: Shor's Factoring Algorithm (pdf notes, video)
- Lecture 17: The Hidden Subgroup Problem (pdf notes, video)
- Lecture 18: Grover's Algorithm (pdf notes, video)
- Lecture 19: Quantum Query Complexity (pdf notes, video)
- Lecture 20: The Adversary Method (pdf notes, video)
- Lecture 21: Mixed States and Density Matrices (pdf notes, video)
- Lecture 22: Quantum Probability (pdf notes, video)
- Lecture 23: Quantum Information Theory (pdf notes, video)
- Lecture 24: Quantum Complexity (pdf notes, video)
- Lecture 25: Quantum "Supremacy" (pdf notes, video)
Course description
This course will be an introduction to quantum computation and quantum information theory, from the perspective of theoretical computer science. Topics to be covered will likely include:
- Fundamental axioms of quantum mechanics
- Fun with a few qubits: quantum Zeno and anti-Zeno, Elitzur--Vaidman bomb, entanglement, teleportation, no-cloning
- Bell's inequality and the CHSH game
- Fun with many qubits: quantum money, quantum key distribution
- The quantum circuit model of computation; Fourier transform viewpoint
- Basic quantum algorithms: Deutsch--Josza, Bernstein--Vazirani, Simon
- Grover search algoritihm
- Shor's factoring algorithm
- The hidden subgroup problem
- Lower bounds for quantum query algorithms
- Quantum complexity theory
- Quantum probability, mixed states, POVMs, quantum channels
- Quantum tomography: Learning, testing, and discriminating quantum states
- Elements of quantum information theory
- Quantum error correction
- Quantum supremacy
Prerequisites
A strong undergraduate background in linear algebra (e.g., CMU's 21-341), discrete probability (e.g., CMU's 15-359), and theory of computation (e.g., CMU's 15-251). No background in physics is required. We anticipate the course will be of interest to students working in computer science, mathematics, or physics.
Suggested texts, notes, and videos to look at