Course description: The course covers quantum information, quantum algorithms, quantum error correction, and quantum cryptography.
Class meetings: Wednesdays and Fridays in 269 Lauritsen.
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.
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.
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,
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):
Lecture 12 (11/4): Teleportation, violation of local realism with GHZ states
Lecture 13 (11/9): The n-party
Part IV. Quantum Information Theory
Lecture 13 (11/9): Compression of classical messages,
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.
Problem Set 1 [PS] [PDF] (posted
Problem Set 2 [PS] [PDF] (posted
Problem Set 3 [PS] [PDF] (posted
Problem Set 4 [PS] [PDF]
Problem Set 5 [PS] [PDF] (posted
Problem Set 6 [PS] [PDF] (posted
Problem Set 7 [PS] [PDF] (posted