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: Wednesdays and Fridays 2:30-4:00 in 269 Lauritsen.

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

Teaching assistant:

Panos Aliferis, 453 Lauritsen, X-6650 email:

Lectures and references:
Good general references for the course are Quantum Computation and Quantum Information by Nielsen and Chuang (which is available in the bookstore) and my lecture notes. Another excellent text (more technical and less comprehensive than Nielsen and Chuang) is Classical and Quantum Computation by Kitaev, Shen, and Vyalyi, which is based in part on Kitaev’s lectures for this course.

Part I. Overview
Lecture 1 (9/28): Quantum vs. classical information, intrinsic randomness, information/disturbance tradeoff, tensor product and entanglement.
Lecture 2 (9/30): Quantum circuit model, quantum parallelism, quantum error correction, quantum information processing with trapped ions.

Part II. Foundations
Lecture 3 (10/5): Axioms for a closed quantum system, the qubit, open systems and density operators, Gleason’s theorem.
Lecture 4 (10/7): Schmidt decomposition, convexity of the set of density operators, ensemble interpretation and the HJW theorem.
Lecture 5 (10/12): Generalized measurements, quantum operations, completely positive maps.
Lecture 6 (10/14): Complete positivity and the Kraus representation of CP maps, depolarizing channel.
Lecture 7 (10/19): Phase damping and amplitude damping, Heisenberg picture and unital maps, master equation.
Lecture 8 (10/21): Damped harmonic oscillator, stochastic Schroedinger equation.

Part III. Entanglement
Lecture 9 (10/26): Quantum entanglement and nonlocality, Bell inequalities.
Lecture 10 (10/28): Geometry of the classical polytope, CHSH inequality and its maximal violation.
Reference for Lecture 10: quant-ph/0102024 .
Lecture 11 (11/2): Bell inequality experiments and loopholes, dense coding
Lecture 12 (11/4): Teleportation, violation of local realism with GHZ states
Lecture 13 (11/9): The n-party Bell polytope and maximal violation of local realism.

Part IV. Quantum Information Theory
Lecture 13 (11/9): Compression of classical messages, Shannon entropy.
Lecture 14 (11/11): Conditional entropy and mutual information, noisy channel coding theorem.
Lecture 15 (11/16): Von Neumann entropy, Schumacher compression.
Lecture 16 (11/18): Compression continued. Entanglement cost and distillable entanglement for bipartite pure states.
Lecture 17 (11/23): Quantum mutual information, strong subadditivity, accessible information, Holevo bound.
Lecture 18 (11/30): Optimal measurements, classical and quantum capacities of quantum channels.
Lecture 19 (12/2): Coherent information, mother and father protocols, state merging and interpretation of negative conditional entropy.
References for Lecture 19: quant-ph/0308044 and quant-ph/0505062 .
Lecture 20 (1/4): Rerun of Lecture 19.
Lecture 21 (1/6): Proof sketches for mother and father resource inequalities.

Part V. Classical and Quantum Circuits
Lecture 21 (1/6): Boolean circuits, universal classical gates.
Lecture 22 (1/11): Classical circuits and complexity: P, NP, NPC, BPP.
Lecture 23 (1/13): Landauer’s principle, reversible computation, reversible universal gates.
Lecture 24 (1/18): Quantum circuits and complexity: BQP, QMA. Simulating BQP in PSPACE, required accuracy of approximate gates.
Lecture 25 (1/20): Universality of two-qubit quantum gates.
Lecture 26 (1/25): Solovay-Kitaev theorem. Reference: quant-ph/0505030 .

Part VI. Quantum Algorithms
Lecture 26 (1/25): Classical and quantum black boxes.
Lecture 27 (1/27): Deutsch and Deutsch-Jozsa problems, Simon’s problem.
Lecture 28 (2/1): Period finding and the quantum Fourier transform.
Lecture 29 (2/3): Factoring as period finding.
Lecture 30 (2/8): Public key cryptography and RSA, phase estimation.
Lecture 31 (2/10): Discrete logarithms, the hidden subgroup problem for finitely generated abelian groups.
Lecture 32 (2/15): Abelian hidden subgroup problem continued, nonabelian hidden subgroup problem and the dihedral group.
Reference for Lecture 32: quant-ph/9807029
Lecture 33 (2/17): Quantum searching and Grover’s algorithm.
Lecture 34 (2/22): Lower bounds on quantum query complexity.
Lecture 35 (2/24): Lower bounds continued; simulating time evolution governed by a local Hamiltonian.
Reference for Lecture 35: quant-ph/9802049
Lecture 36 (3/1): Estimating energy eigenvalues of a local Hamiltonian; efficient classical simulation of slightly entangled quantum computations.
References for Lecture 36: quant-ph/0301063 , cond-mat/0404706 
Lecture 37 (3/3): QMA completeness of the local Hamiltonian problem. Reference: quant-ph/0210077
Class will not meet on March 8 and 10.

Homework assignments: 
Problem Set 1 [PS] [PDF] (posted Tuesday 11 October 2005; due Wednesday 26 October 2005). Solution [PS] [PDF]
Problem Set 2 [PS] [PDF] (posted Sunday 30 October 2005; due Wednesday 16 November 2005). Solution [PS] [PDF]
Problem Set 3 [PS] [PDF] (posted Thursday 17 November 2005; due Friday 2 December 2005). Solution [PS] [PDF]

Problem Set 4 [PS] [PDF] (posted Thursday 8 December 2005; due Wednesday 18 January 2006). Solution [PS] [PDF]
Problem Set 5 [PS] [PDF] (posted Tuesday 24 January 2006; due Friday 3 February 2006). Solution [PS] [PDF]
Problem Set 6 [PS] [PDF] (posted Monday 6 February 2006; due Wednesday 22 February 2006). Solution [PS] [PDF]
Problem Set 7 [PS] [PDF] (posted Tuesday 21 February 2006; due Friday 10 March 2006). Solution [PS] [PDF]