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
Instructors:
John Preskill
, 448 Lauritsen, X-6691, email: preskill@theory.caltech.edu
Alexei
Kitaev , 280 Jorgensen, X-8760, email: kitaev@cs.caltech.edu
Teaching assistant:
Hui Khoon Ng , 445 Lauritsen, X-2633, email: nghk@caltech.edu , 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,
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)
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
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