Quantum Computation

2005-06

**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

**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,

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