**COMP-761: Quantum Information Theory**

**Time:** Tuesday and Thursday from 4:00 to 5:30 (Winter 2009)

**Room:** McConnell 320

** **

**Instructor:** Patrick Hayden

Office: ENGMC 108N

Phone: 398-5491

Email: patrick@cs.mcgill.ca

Office hours: By appointment

**Course
description:**

This course will present the quantum
analog of Shannon’s information theory. This area has seen an explosion of
interest and a correspondingly rapid technical advance over the past ten years,
largely in response to the development of quantum-mechanically based
cryptographic protocols and Shor’s famous algorithm for factoring integers. The
unavoidable presence of noise in any quantum-mechanical information processing
device means that error-correction techniques will play a crucial role in any
practical application of quantum cryptography or computing. This course will
focus on asymptotic protocols for compression, communication, error correction
and state distillation, identifying the absolute limits placed on those tasks
by quantum mechanics.

Familiarity with quantum mechanics
is recommended. The course content is very mathematical, but elementary.
Students should be comfortable with basic probability theory, linear algebra
and real analysis. The material will be covered through a combination of
lectures and student presentations.

**Course
outline:**

- Classical
information theory:
- Compression:
Shannon’s noiseless coding theorem
- Error correction:
Shannon’s noisy coding theorem
- The birth of the
qubit: Schumacher compression
- Tools for quantum
information:
- Review of
quantum-mechanical formalism (including Bell’s theorem)
- Inequalities for
von Neumann entropy
- Strong subadditivity
- Three brilliant
trivialities:
- Superdense coding
- Teleportation
- Coherent classical
communication
- The family of
quantum protocols
- The mother, father
and fully quantum Slepian-Wolf protocols
- Consequences
- Entanglement
distillation
- State merging
- Entanglement-assisted
and quantum capacities
- Quantum reverse
Shannon theorem
- The HSW theorem:
classical data through a noisy quantum channel
- A noiseless
postlude:
- Superdense coding
of quantum states and its consequences
- Majorization and
entanglement manipulation

**Grading:** 55% assignments, 35% presentations, 10% scribe notes.

**Text:** There is no text for the course. However, roughly the
first month’s worth of material can be found in *Quantum Computation and Quantum Information* by Nielsen and Chuang,
which is an excellent introduction to the field as a whole. *Elements of Information Theory* by Cover
and Thomas should meet your classical information theory needs.

**Assignments:**

**Presentations:** More information can be found here.

**Scribe
notes:**

You will be expected to produce
detailed lecture notes for three 1.5 hour classes.

Use scribe.sty,
originally written by Jeff Erickson.

**Unedited
student notes: use at your own risk...**

Lecture 1: Uncertainty and compression
[ pdf tex ]

Lecture 2: Properties of entropy and
mutual information [ pdf tex
]

Lecture 3: Gambling, communication
and mutual information [ pdf tex ]

Lecture 4: Shannon’s noisy coding
theorem [ pdf tex ]

Lecture 5: Fano’s inequality and
intro to quantum mechanics [ pdf tex ]

Lecture 6: A computer science
perspective on nonlocality [ pdf tex ]

Lecture 7: Nonlocality (cont.d.)
Density operators and the partial trace. Superdense coding. [ pdf tex ]

Lecture 8: Quantum operations [ pdf tex ]

Lecture 9: Teleportation and intro
to resource inequalities [ pdf tex
]

Lecture 10: Quantum entropy [ pdf tex ]

Lecture 11: Coherent classical
communication: the cobit. [ pdf tex ]

Lecture 12: From Lieb’s concavity
theorem to monotonicity of relative entropy [ pdf ]

Lecture 13: Quantum data compression
[ pdf tex ]

Lecture 14: Fidelity vs trace
distance. Schumacher converse. Entanglement distillation. [ pdf tex ]

Lecture 15: State transfer and the
decoupling argument [ pdf tex
]

Lecture 16: Comments on group
integration. Decoupling calculation
(part 1) [ pdf tex ]

Lecture 17: Decoupling calculation
(part 2) [ pdf ]

Lecture 18: Optimality of decoupling.
Entanglement-assisted capacities [ pdf tex ]

Lecture 19: Qubit erasure channel
example. Quantum capacity [ pdf tex ]

**Embarrassing obligatory inclusion: **

By the
direction of Senate (January 29, 2003), all course outlines have to include the
following statement:

McGill University values academic
integrity. Therefore, all students must understand the meaning and consequences
of cheating, plagiarism and other academic offences under the Code of Student
Conduct and Disciplinary Procedures (see www.mcgill.ca/integrity for more
information).