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.
Instructor:
John Preskill
, 448 Lauritsen, X-6691, email: preskill@theory.caltech.edu
Teaching assistant:
Prabha Mandayam, 449 Lauritsen, X-6595, email: prabhamd@caltech.edu
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,
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:
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]