Quantum Computation

Go to home page for Ph219/CS219 in past years.

Course description: This two-term course covers quantum information theory, quantum algorithms, quantum error correction, quantum Shannon theory, and some special topics.

Class meetings: Monday and Wednesday 2:30-3:55 in 107 Downs, beginning 1 October 2018.


John Preskill, 206 Annenberg, X-6691, email: preskill(at)caltech(dot)edu

Teaching assistant:

Tian Wang, 232 Annenberg, email: twang3(at)caltech(dot)edu
Office hours: 4-5:30 pm Monday, in weeks when homework is due.
Course information posted by Tian can be accessed on Moodle.

Lectures and references:
The primary reference for most of the lectures will be these lecture notes (JP). Other useful books are Quantum Computation and Quantum Information by Nielsen and Chuang (NC), Classical and Quantum Computation by Kitaev, Shen, and Vyalyi (KSV), Quantum Computing Since Democritus by Aaronson, The Theory of Quantum Information by Watrous, and Quantum Information Theory by Wilde.

Other recommended lecture notes: John Watrous, Umesh Vazirani, Andrew Childs, Scott Aaronson

Course outline for fall term:
Topics covered in the tall will include density operators, quantum operations, quantum entanglement, quantum circuits, and quantum algorithms.

Lecture 1 (Oct 1): Introduction (JP Chapter 1).
See also: Quantum computing and the entanglement frontier, and Quantum computing in the NISQ era and beyond.
Video: Canadian Summer School on Quantum Information Lecture 1, Lecture 2.
Lecture 2 (Oct 3): Density operators (JP Chapter 2). Lecture by Victor Albert.
Lecture 3 (Oct 8): Convexity, HJW theorem, generalized measurements (JP Chapter 3)
Lecture 4 (Oct 10): Quantum channels, complete positivity (JP Chapter 3)
Lecture 5 (Oct 15): Channel state duality (JP Chapter 3)
Lecture 6 (Oct 17): Qubit channels, master equation (JP Chapter 3)
Lecture 7 (Oct 22): Bell inequalities, CHSH game (JP Chapter 4)
Lecture 8 (Oct 24): Bell polytope and its dual, quantum vs classical models
Reference: quant-ph/0102024
Lecture 9 (Oct 29): Superdense coding and quantum teleportation (JP Chapter 4)
Lecture 10 (Oct 31): Circuit complexity, P and NP, NP-completeness (JP Chapter 5)
Lecture 11 (Nov 5): BPP and MA, Reversible computing, BQP and QMA (JP Chapter 5)
Lecture 12 (Nov 7): Quantum circuits, universal gates (JP Chapter 5)
Lecture 13 (Nov 12): Universal gates continued, Solovay-Kitaev theorem (JP Chapter 5)
Lecture 14 (Nov. 14): Black Box model, Deutsch-Jozsa problem, Simon’s problem (JP Chapter 6, p.37 ff)
Lecture 15 (Nov. 19): Period finding
Lecture 16 (Nov. 21): Factoring, public key cryptography, phase estimation
Lecture 17 (Nov. 26): Abelian hidden subgroup problem, discrete logarithm (handwritten notes – see also notes on non-abelian HSP)
Lecture 18 (Nov. 28): Quantum searching (handwritten notes – see also notes on quantum lower bounds)
Lecture 19 (Dec. 3): Quantum simulation (handwritten notes)
Lecture 20 (Dec. 5): Local Hamiltonian problem (KSV Chapter 14, handwritten notes)


Homework assignments: 
All students taking the course for credit are required to do the homework.  Unless otherwise announced, homework will be due on Thursday at 5pm.

Homework should be handed into the box outside of the Ann 232 by the due date, or emailed to Tian <> if you type it up. Please use a large font or write legibly.

You may receive partial credit if you describe a thoughtful approach to the problem, even if you are unable to solve it completely.

If you have questions, you may post them on Moodle or email them to Tian. Problem solutions will be posted on Moodle.

Problem Set 1. States and measurements, due Thursday October 25.
Problem Set 2. Quantum channels and entanglement, due Thursday November 8,
Problem Set 3. Quantum circuits, due Wednesday November 21.
Problem Set 4. Quantum algorithms, due Thursday December 6.