Quantum Computation

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

Course description: This is a three-term course covering quantum information, quantum algorithms, quantum error correction, and quantum cryptography.

Class meetings: Monday and Wednesday 1:00-2:30 in 269 Lauritsen, beginning 29 September 2008

Note: There will be no lecture on May 27. The last lecture of the year is on June 1.

John Preskill , 448 Lauritsen, X-6691, email:

Teaching assistant:

Prabha Mandayam, 449 Lauritsen, X-6595, email:

Lectures and references:
The primary reference for most of the lectures will be these lecture notes (JP). Other useful references are Quantum Computation and Quantum Information by Nielsen and Chuang (NC), and Classical and Quantum Computation by Kitaev, Shen, and Vyalyi (KSV). NC and KSV are available in the bookstore.

Sep. 29, Oct. 1: Introduction. Quantum information, entanglement, quantum algorithms, quantum error correction, physical implementation of quantum computing (JP, Chapter 1)
Oct. 6, 8, 13: Density operators. Open systems, Bloch sphere, convexity, Schmidt decomposition, HJW theorem. (JP, Chapter 2)
Oct. 15, 20, 22, 27: Quantum operations. Generalized measurements, completely positive maps, Kraus operators, decoherence. (JP, Chapter 3)
Oct. 29, Nov. 3, 5: Quantum nonlocality, Bell inequalities. (JP, Chapter 4, revised 2001 version)
Supplementary handwritten notes (scanned 3.6 MB pdf file)
Nov. 10, 12: Superdense coding, quantum teleportation. (JP, Chapter 4, revised 2001 version)
Nov. 17, Nov. 19:  Classical circuits, universal gates, complexity classes P, NP, and co-NP. Randomized computation, BPP and MA. (JP, Chapter 6)
Nov. 24, Nov. 26: Reversible classical circuits, quantum circuits. BQP, QMA, accuracy requirements (JP, Chapter 6)
Dec. 1, Dec. 8: Universality of two-qubit gates, Solovay-Kitaev Theorem. (JP, Chapter 6, and quant-ph/0505030)

Jan. 5, Jan. 7: Quantum algorithms. Deutsch and Deutsch-Jozsa problems, Simon’s problem, period finding. (JP, 6.3 and 6.9)
Jan. 21, Jan. 26: Factoring algorithm, public key cryptosystems, eigenvalue estimation (JP, 6.10, 6.11)
Jan. 28, Feb. 2: Hidden subgroup problem for finitely generated abelian groups (handwritten notes, 2.5 MB)
Feb. 9: Nonabelian subgroup problem (handwritten notes), Feb. 11: Quantum searching (handwritten notes)
Feb. 18, Feb. 23: Lower bounds on quantum query complexity (updated handwritten notes)
Feb. 25, Mar. 2: Simulating quantum evolution, estimating energy eigenvalues (updated handwritten notes)
Mar. 4, 9, 11: Complexity of estimating ground state energy of classical and quantum Hamiltonians. (KSV Chap. 14, handwritten notes)

The reference for the first five lectures of the second term is JP, Chapter 7 (“Quantum error correction”), Sec. 1-10, 14, 15.1.
Mar. 30: Concept of a quantum error-correcting code and the error correction criteria.
Apr. 1, 6: Classical binary linear codes, quantum CSS codes, stabilizer codes.
Apr. 8: The five-qubit code, existence of good stabilizer codes.
Apr. 13: Concatenated quantum codes, toric code (reference: quant-ph/0110143, Sec. III, IV.C, and V).
A good reference for the next few lectures is this recent review.
Apr. 15, 20: Toric code recovery, fault-tolerant recovery (updated handwritten notes)
Apr. 22, 25: Fault-tolerant quantum gates (handwritten notes)
Apr. 29: Quantum accuracy threshold theorem (arXiv:0904.2557, Sec. 5)

The reference for the next few lectures is JP, Chapter 5 (Quantum Information Theory).
May 4, 6:  Shannon entropy, compression of classical messages, mutual information, noisy channel coding theorem (Sec. 5.1).
May 11, 13: Von Neumann entropy, Schumacher compression, entanglement cost and distillable entanglement for bipartite pure states (Sec. 5.2, 5.3, 5.5).
May 18, 20: Strong subadditivity, accessible information, capacities of quantum channels (updated handwritten notes)
June 1: Mother and father protocols and their children (handwritten notes)
Other references for June 1 lecture: quant-ph/0308044, quant-ph/0505062, quant-ph/0606225

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 Prabha Mandayam’s mailbox, outside 452 Lauritsen.

Problem Set 1 [PDF] (posted Tuesday 14 October 2008; due Wednesday 29 October 2008). Solution: [PDF]
Problem Set 2 [PDF] (posted Tuesday 28 October 2008; due Wednesday 12 November 2008). Solution: [PDF]
Problem Set 3 [PDF] (posted Tuesday 11 November 2008; due Wednesday 26 November 2008). Solution: [PDF]

Problem Set 4 [PDF] (posted Tuesday 9 January 2009; Prob. 4.4c corrected 20 January; due Wednesday 28 January 2009). Solution: [PDF]
Problem Set 5 [PDF] (posted Monday 2 February 2009; due Wednesday 11 February 2009). Solution: [PDF]
Problem Set 6 [PDF] (posted Tuesday 17 February 2009; due Wednesday 4 March 2009). Solution: [PDF]

Problem Set 7 [PDF] (posted Tuesday 14 April 2009; due Wednesday 29 April 2009). Solution: [PDF]
Problem Set 8 [PDF] (posted Thursday 30 April 2009; due Wednesday 13 May 2009). Solution: [PDF]
Problem Set 9 [PDF] (posted Sunday 17 May 2009; due Monday 1 June 2009). Solution: [PDF]