Quantum Computation

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

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

Class meetings: Monday and Wednesday 2:30-3:55 in 269 Lauritsen.
Note: Class will not meet at the regularly scheduled time the last two weeks of the term. (No class on March 3, 5, 10, 12.) The last two make-up lectures will be Thursday March 6 and Thursday March 13 at 7:00-8:30 pm in 269 Lauritsen.


John Preskill , 206 Annenberg, X-6691, email:

Teaching assistant:

Alex Kubica, 235 Annenberg, email: akubica(at)caltech(dot)edu
Michael Beverland, 235 Annenberg, email: mbeverla(at)caltech(dot)edu
Alex and Michael are available to meet with students Mondays at 7 pm in 107 Annenberg on weeks when homework is due, and also every Wednesday 4:00-5:00 pm in 235 Annenberg; if those times don’t work, you can make an appointment by email.

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, and Quantum Information Theory by Wilde.

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

Course outline for fall term:

Lecture 1 (Oct. 7): Introduction (JP Chapter 1). See also: Quantum computing and the entanglement frontier , and Can we exploit the weirdness of quantum mechanics?
Lecture 2 (Oct. 9): Density operators (JP Chapter 2)
Lecture 3 (Oct. 10): HJW theorem, generalized measurements, channels (JP Chapter 2 and 3)

Lecture notes for Lectures 2-3: Revised Chapter 2.

Lecture 4 (Oct. 14): Operations, Choi-Jamiolkowski isomorphism (JP Chapter 3)
Lecture 5 (Oct. 16): Qubit channels (JP Chapter 3)
Lecture 6 (Oct. 17): Master equation, Bell inequalities (JP Chapter 3 and 4)
Lecture 7 (Oct. 21): CHSH game, Local hidden variables, Bell polytope and its dual. Reference: quant-ph/0102024
Lecture 8 (Oct. 23): Quantum versus classical models, Bell inequality experiments and loopholes
Lecture 9 (Oct. 28): Quantum entanglement, teleportation, classical circuits
Lecture 10 (Oct. 30): Complexity classes P, NP, BPP, MA. NP-completeness, Landauer’s principle (JP Chapter 6)
Lecture 11 (Nov. 4): Reversible computing, quantum circuits
Lecture 12 (Nov. 6): Universal quantum gates
Lecture 13 (Nov. 11): Solovay-Kitaev theorem. Reference: quant-ph/0505030

Lecture notes for Lectures 10-13: Revised Chapter 5.

Lecture 14 (Nov. 13): Black Box model, Deutsch-Jozsa problem, Simon’s problem (JP Chapter 6)
Lecture 15 (Nov. 18): Period finding
Lecture 16 (Nov. 20): Factoring, public key cryptography, phase estimation
Lecture 17 (Nov. 25): Abelian hidden subgroup problem, discrete logarithm (handwritten notes – see also notes on non-abelian HSP)
Lecture 18 (Nov. 27): Quantum searching (handwritten notes – see also notes on quantum lower bounds)
Lecture 19 (Dec. 2): Quantum simulation (handwritten notes)
Lecture 20 (Dec. 4): Local Hamiltonian problem (KSV Chapter 14, handwritten notes)

Course outline for winter term:

A good reference on quantum error correction is this review by Gottesman. See also JP Chapter 7.
Lecture 1 (Jan. 13): Quantum error-correcting codes
Lecture 2 (Jan. 14): Classical linear codes, quantum CSS codes
Lecture 3 (Jan. 15): Quantum stabilizer codes
Lecture 4 (Jan. 22): Stabilizer codes continued
Lecture 5 (Jan. 27): Existence of good codes, upper bounds on code rate.
Lecture 6 (Jan. 29): Concatenated codes, toric code.

Handwritten lecture notes on toric code recovery, fault-tolerant recovery, fault-tolerant gates

Lectures 7-8: Fault-tolerant quantum memory and computation.
Lectures 9-10: Quantum accuracy threshold theorem.

For more details on information theory, see Wilde (also available in an arXiv version).
Handwritten lecture notes on strong subadditivity of Von Neumann entropy, Holevo bound, capacities of quantum channels

Lectures 11-12: Shannon entropy and compression, Von Neumann entropy and quantum compression.
Lectures 13-14: Strong subadditivity, accessible information, noisy-channel coding.
Lectures 15-17: Capacities of quantum channels.

Homework assignments: 
All students taking the course for credit are required to do the homework, which will be assigned several times each term.  You can hand in the homework in class on the due date, or leave it in the mailbox of Alex Kubica or Michael Beverland, on the 3rd floor of Annenberg.

Problem Set 1. States and measurements. Due Wednesday 23 October 2013. Solutions.
Problem Set 2. Quantum channels and entanglement. Due Wednesday 6 November 2013. Solutions.
Problem Set 3. Quantum circuits. Due Wednesday 20 November 2013. Solutions.
Problem Set 4. Quantum algorithms. Due Wednesday 4 December 2013. Solutions.

Problem Set 5. Quantum error-correcting codes. Due Wednesday 5 February 2014. Solutions.
Problem Set 6. Fault-tolerant quantum computing. Due Wednesday 19 February 2014. Solutions.
Problem Set 7. Entropy and entanglement. Due Wednesday 12 March 2014. Solutions.