Quantum Computation

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

Course description: The course covers quantum information, quantum algorithms, quantum error correction, and quantum cryptography.

Class meetings: Tuesdays and Fridays 1:00-2:30 in 269 Lauritsen, beginning 26 September.

John Preskill , 448 Lauritsen, X-6691, email:
Alexei Kitaev , 280 Jorgensen, X-8760, email:

Teaching assistant:

Hui Khoon Ng , 445 Lauritsen, X-2633, email: , office hours: Wednesdays 4-5pm

Lectures and references:
Preskill will lecture the first half of the first term, covering roughly the material in the first four chapters of his lecture notes. Kitaev will lecture the second half of the first term, covering classical and quantum algorithms and complexity; the primary reference for this portion of the course will be Classical and Quantum Computation by Kitaev, Shen, and Vyalyi (KSV). Another useful general reference is Quantum Computation and Quantum Information by Nielsen and Chuang (NC).  KSV and NC are available in the bookstore. The material covered during the second term will include quantum error-correcting codes and fault-tolerant quantum computation.

Week 1 (Sep. 26, 29): Introduction. Quantum information, entanglement, quantum algorithms, quantum error correction.
Week 2 (Oct. 3, 6): Density operators. Open systems, Bloch sphere, Schmidt decomposition, HJW theorem.
Week 3 (Oct. 10, 13): Quantum operations. Generalized measurements, completely positive maps, Kraus operators, decoherence.
Week 4 (Oct. 17, 20, 24): Quantum nonlocality. Hidden variables, Bell inequalities.
Oct. 27: Discussion of computational complexity. Simulating quantum mechanics requires exponential time but only linear space.
Oct 31, Nov. 3: Turing machines and Boolean circuits. Uniform and nonuniform computational problems; P vs. P/poly. Circuit size and depth; log-depth circuits for addition and multiplication.
Nov. 7: Energy cost of bit erasure. Reversible classical circuits. Garbage removal.
Nov. 10: Examples of quantum gates and circuits. Two-qubit gates are universal.
(Supplementary material:
Nov.14: Approximate realization of unitary operators. Solovay-Kitaev theorem.
Nov. 17: Standard gate sets. Grover's algorithm.
Nov. 20: The optimality of Grover's algorithm. Abelian hidden subgroup problem.
Nov. 27: Simon's algorithm. Quantum Fourier transform.
Dec. 1: Factoring and period finding. Shor's algorithm.

The reference for the first couple of weeks of the second term is Chapter 7 of Preskill’s lecture notes (“Quantum error correction”).
Jan. 5: Concept of a quantum error-correcting code and the error correction criteria.
Jan. 9, 12: Classical binary linear codes, quantum CSS codes, stabilizer codes.
Jan. 16: The five-qubit code, existence of good stabilizer codes.
Jan. 19: Concatenated quantum codes, toric code (reference: quant-ph/0110143).
References for the lectures on fault-tolerant quantum computing: quant-ph/0504218 (referred to as “AGP” below), and quant-ph/9712048 (referred to as “Pres97”).
Jan. 23: Fault-tolerant error correction (AGP Sec. 2 and Sec. 7; Pres97).
Jan. 26: Fault-tolerant Clifford group gates (quant-ph/9807006, quant-ph/9802007).
Jan. 30 : Fault-tolerant C_3 gates (quant-ph/0002039).
Feb. 2 : Quantum accuracy threshold theorem (AGP Sec. 4, Sec. 5, Sec. 9)

Homework assignments: 
The course is graded pass/fail, and all students taking the course for credit are required to do the homework, which will be assigned several times each term.

Problem Set 1 [PS] [PDF] (posted Monday 9 October 2006; due Friday 20 October 2006). Solution: [PDF]
Problem Set 2 [PS] [PDF] (posted Monday 23 October 2006; due Friday 3 November 2006). Solution: [PDF]
Problem Set 3 [PS] [PDF] (posted Tuesday 7 November 2006; due Tuesday 21 November 2006). Solution: [PS] [PDF]
Problem Set 4 [PS] [PDF] (posted Monday 27 November 2006; due Thursday 7 December 2006).

Problem Set 5 [PS] [PDF] (posted Monday 22 January 2007; due Tuesday 6 February 2007). Solution: [PS] [PDF]
Problem Set 6 [PS] [PDF] (posted Monday 5 February 2007; due Friday 16 February 2007). Solution: [PS] [PDF]
Problem Set 7 [PS] [PDF] (posted Monday 5 March 2007; due Thursday 15 March 2007). Solution: [PS] [PDF]