Course description: The course covers quantum information, quantum algorithms, quantum error correction, and quantum cryptography.
Class meetings: Tuesdays and Fridays in 269 Lauritsen, beginning 26 September.
John Preskill , 448 Lauritsen, X-6691, email: firstname.lastname@example.org
Alexei Kitaev , 280 Jorgensen, X-8760, email: email@example.com
Hui Khoon Ng , 445 Lauritsen, X-2633, email: firstname.lastname@example.org , 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
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,
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: http://www.arxiv.org/pdf/quant-ph/9503016)
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)
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]
Problem Set 2 [PS] [PDF] (posted
Problem Set 3 [PS] [PDF] (posted
Problem Set 4 [PS] [PDF] (posted
Problem Set 5 [PS] [PDF]
(posted Monday 22 January 2007; due Tuesday 6 February 2007). Solution: [PS] [PDF]
Problem Set 6 [PS] [PDF] (posted
Problem Set 7 [PS] [PDF] (posted