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
Instructor:
John Preskill
, 448 Lauritsen, X-6691, email: preskill@theory.caltech.edu
Teaching assistant:
Panos Aliferis, 453 Lauritsen, X-6650 email: panos@theory.caltech.edu
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.
Part
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.
Homework assignments:
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
Problem Set 6 [PS] [PDF]
(posted
Problem Set 7 [PS] [PDF]
(posted