QIC 890/CO 781:

Theory of Quantum Communication, Fall 2020


Debbie Leung

Email: wcleung(at)uwaterloo(dot)ca

Lectures (Sept 08 - Dec 03):

Tue/Thur 11-12:15, live on zoom (+recordings).

Supplemented with weekly self-study material when appropriate.

Click here for notes.

Click here for Assignments.

Office hours:

After class or by appointment. Slack discussion.


Course information


Communication is an important information processing task. It is also a crucial primitive in algorithms and cryptographic protocols. Examples of communication tasks include data compression, data transmission via noisy channels, and logic gates acting on multiple registers. In the quantum regime, communication channels are more powerful and complex than their classical counterparts. Many more types of data (quantum, classical, private) can be transmitted, and there are more interesting auxiliary resources to consider (entanglement, side classical channels in either direction).

This course (1) provides an overview on the methods of communication in the quantum setting, with particular emphasis in "superadditivity" (surprising new phenomena arising from combining different primitives), (2) explores applications of these uniquely quantum techniques to other quantum information processing tasks, (3) covers fundamental limits of communication, and inferences to the physical model and performance bounds on other quantum tasks.


Good understanding of the following: Postulates of quantum mechanics, quantum states, unitary operations, projective measurements, quantum circuits (universality not needed, but circuit representation of protocols will be heavily used), superdense coding, teleportation, no-cloning theorem, density matrices and purifications, general quantum operations (aka quantum channels) and their representations (Kraus, Stinespring, and Choi representations), POVM measurements, error measures such as trace distance, fidelity, and the diamond norm, and Uhlmann's theorem.

Most of these are covered as a small subset of the syllabus in CO481/CS467/PHYS467 or QIC710/CO681 in UW, and in many equivalent courses elsewhere. Formal enrollment in such a course is not strictly required, but fluency in the aforementioned topics will be tremendously helpful. Students who wish to take QIC710/CO681 simultaneously are encouraged to self-study the above topics and are welcomed to discuss with the instructor.

Useful resources to learn the prerequisites:

  • Richard Cleve's lecture notes for QIC 710
  • Jon Yard's lecture notes for QIC 710
  • John Watrous' lecture notes for CS 766/QIC 820
  • John Preskill's course on quantum computation and lecture notes
  • Textbook by Nielsen and Chuang, Cambridge University Press
  • Textbook by Kaye, Laflamme, and Mosca, Oxford University Press
  • Public lecture by Charles Bennett at Qiskit that also previews some of the topics and illustrate the spirit of the course.

    Each of the following provides detailed background reading for density matrices and quantum TCP maps. Please use the links directly above to access.

  • Richard Cleve lecture notes for QIC 710, lectures 10-11, lecture 12.
  • John Watrous lecture notes for CS766/QIC 820, lectures 2-6.
  • Nielsen and Chuang, Chapter 2.4, Chapter 8.
  • W2019 CO481/CS467/PHYS467, files topic08-1nn.pdf, topic08-2n.pdf

    Text / References:

    The course material will be developed primarily in the lectures. The following additional references can also be interesting to some students.

  • Lecture notes in the Fall 2016 offering
  • John Preskill's notes Chapter 10
  • John Watrous' book Chapter 8
  • Mark Wilde's text book
  • Syllabus:

    Materials to be covered either in class, or in term projects.

    Topic 1 -- Basic principles and tools

  • What is communication?
  • Surprise nonadditivity -- Superdense coding (SD) and teleportation (TP)
  • Good enough means good anywhere -- resource inequalities, simulations, composability
  • No free lunch -- the no signalling principle
  • Optimality and duality of SD and TP, cobits, bidirection channels
  • Knowledge is power -- remote state preparation (RSP) and SD of quantum states
  • Spinoffs of TP -- quantum encryption, quantum message authentication, fault-tolerant gates
  • Why QM better be linear (and why you don't want to travel back in time)
  • Topic 2 -- Entropy and data Compression

  • Too good but it is true -- the Asymptotic equipartition theorem (AEP)
  • Shannon entropy
  • Data compression (Shannon's noiseless coding theorem)
  • Quantum ensembles and quantum data compression
  • Von Neumann entropy
  • Entanglement concentration and dilution (and the entropy of entanglement)
  • Entanglement embezzlement and entanglement spread
  • Topic 3 -- Classical communication via classical channels (warm-up)

  • Conditional entropy, relative entropy, mutual information, and joint typicality
  • Classical iid channels
  • Shannon's noisy coding theorem
  • The direct coding theorem (power of randomized proofs) and the converse
  • Topic 4 -- Classical communication via quantum channels

  • The tricky business to extract classical information from quantum states
  • No-cloning on steroid: information gain implies disturbance
  • All you can get: accessible information
  • Locking (encryption with a very small key, and surprise noncomposability due to side information)
  • Holevo information, Holevo bound
  • Entanglement and back communication cannot increase communication rates of noiseless channel (beyond SD)
  • The HSW theorem for the classical capacity of a quantum channel
  • Extremely useful technical tools omitted 2020: pretty good measurement, gentle measurement lemma, conditional typicality
  • Surprise equivalence of 4 seemingly different non-additivity phenomena
  • Topic 5 -- Quantum communication via quantum channel

  • Error definitions for transmitting quantum data, and the quantum capacity of a quantum channel
  • Isometric extensions and complementary channels
  • Coherent information of quantum states and quantum channels
  • The LSD theorem for the quantum capacity of a quantum channel
  • Tools (briefly covered): Fannes inequality (converse), decoupling lemma (direct coding), Ulhmann's theorem, random codes
  • Different approaches and coding methods for the LSD theorem (Omitted in 2020)
  • Degradable and antidegradable channels (when capacities can be calculated)
  • Degenerate codes and nonadditivity
  • Bounding of quantum capacities: additive extensions, zero capacity conditions, continuity, approximate degradability, postmodern bounds
  • Interesting channels exhibiting nonadditivity
  • Topic 6 -- Other capacities

  • Private capacity*
  • Entanglement assisted quantum/classical capacity
  • Quantum capacity assisted by free classical communication
  • No-go for increasing capacities using noiseless catalysis
  • Separations of capacities
  • Superactivation* (0+0>0 !!)
  • Rocket channel (extensive superadditivity)
  • Entanglement assisted zero-error communication
  • Capacities of unitary bidirectional channels
  • Assessments:

    4 Assignments (total 60%)

    1 term project (tentative: resulting in a presentation and a term paper due end of the term) (40%)

    Course materials

    Self-study material and lecture notes:

    Self-study material Sept 06, 2020.

    Brief revision of superdense coding, teleportation, partial trace, and quantum channel.

    Topic 1 part 1.

    2020-09-08 Lecture 1 and 2020-09-10 Lecture 2: What is communication of data?

    Self-study material Sept 14, 2020.

    Two examples on locality of quantum mechanics, the completely randomizing channel, and superdense coding of more general number of messages and teleportation of a system with general dimension.

    Topic 1 part 2.

    2020-09-15 Lecture 3: The No-signalling principle and optimality of teleportation and superdense coding

    Topic 1 part 3.

    2020-09-17 Lecture 4: The cobit, duality of TP and SD, and unitary bidirection channels

    Self-study material Sept 21, 2020.

    Some background material on absorbing operations in measurements, transpose trick, and partial trace needed for topic 1, part 4.

    Topic 1 part 4.

    2020-09-22 Lecture 5: Equivalence of generalized teleportation and generalized encryption of quantum states

    Topic 1 part 5. Additional note p1, p2.

    2020-09-24 Lecture 6: Non-composable qbit: remote state preparation and approximate encryption of pure states

    Self-study material Sept 29, 2020.

    Follow up discussion on whether back communication changes C2, C3 in part 2. References to information gain implies disturbance and Haar measure.

    Topic 1 part 6.

    2020-09-29 Lecture 7: Beyond quantum mechanics?

    Topic 2 part 1.

    2020-10-01 Lecture 8: Entropy, typicality, asymptotic equipartition theorem, and data compression.

    Topic 2 part 2.

    2020-10-06 Lecture 9: von Neumann entropy, typical space, quantum data compression.

    Topic 2 part 3 and AQIS slides on embezzlement.

    2020-10-08 Lecture 10: entanglement of entropy, entanglement dilution, entanglement concentration, entanglement spread, and embezzlement of entanglement.

    Self-study material Oct 13, 2020.

    Please go through p1-8 of the above notes. We build on the concept of Shannon entropy, and introduce conditional entropy, relative entropy, mutual information, and many interesting results such as subadditivity, conditioning reduces entropy, mixing increases entropy, and the strong subadditivity (equivalent to the data processing inequality). This portion concerns standard classical information theory, is relatively straightforward to read, and and might have been seen by some, so, it seems a natural choice for self-study. Following a quick discussion in class, I will state the result during lectures so you can read at your own pace. Lecture 11 will start with p9-11 (on joint typicality and the Joint AEP) of this pdf file

    Topic 3 file 1 and file 2.

    2020-10-20 and 2020-10-22 Lecture 11 and 12: Shannon's noisy coding theorem. Available slides for lecture 11: slides pdf file 1 and slides pdf file 2, and slides pdf file 3.

    Topic 4 part 1 slides and notes from 2016.

    2020-10-27 Lecture 13: Properties of quantum entropies.

    Topic 4 part 2 slides.

    2020-10-29 Lecture 14: Accessible information.

    Topic 4 part 3 slides.

    2020-11-03 Lecture 15: Accessible information (ctd).

    Topic 4 part 4 slides.

    2020-11-05 Lecture 16: Classical capacity of Q-boxes.

    Topic 4 part 5 slides.

    2020-11-10 Lecture 17: Classical capacity of quantum channels, HSW theorem.

    Topic 5 part 1 slides.

    2020-11-12 Lecture 18: Coherent information, LSD Thm Statement

    Topic 5 part 2 slides. Corrected version.

    2020-11-17 Lecture 19: proof of LSD Thm (first half)

    Topic 5 part 3 slides.

    2020-11-19 Lecture 20: proof of LSD Thm (second half)

    Topic 5 part 4 slides.

    2020-11-24 Lecture 21: degradable channels and their quantum capacities

    Topic 5 part 5 slides. Additional notes on capacity of low-noise channels..

    2020-11-26 Lecture 22: nonadditivity of the coherent information and the channel capacity of the depolarizing channel.

    Topic 5 part 6 slides.

    2020-12-01 Lecture 23: superactivation of quantum capacity (0+0>0).

    Guest lecture by Felix Leditzky lecture notes.

    2020-12-03 Lecture 24: Limitations on quantum communication -- computing upper bounds on capacities.

    Recorded lectures:

    2020-09-08 Lecture 1

    2020-09-10 Lecture 2

    2020-09-15 Lecture 3

    2020-09-17 Lecture 4

    2020-09-22 Lecture 5

    2020-09-24 Lecture 6

    2020-09-29 Lecture 7

    2020-10-01 Lecture 8

    2020-10-06 Lecture 9

    2020-10-08 Lecture 10

    2020-10-20 Lecture 11

    2020-10-22 Lecture 12

    2020-10-27 Lecture 13

    2020-10-29 Lecture 14

    2020-11-03 Lecture 15

    2020-11-05 Lecture 16

    2020-11-10 Lecture 17

    2020-11-12 Lecture 18

    2020-11-17 Lecture 19

    2020-11-19 Lecture 20

    2020-11-24 Lecture 21

    2020-11-26 Lecture 22

    2020-12-01 Lecture 23

    2020-12-03 Lecture 24


    Please submit all assignments and term paper to Crowdmark.

    Assignment 1, due Friday Oct 09, 10pm

    Assignment 2, due Friday Oct 30, 10pm. Note that symbols are defined globally for all four questions.

    Term project information, short proposal due any time Novemeber 08.

    Assignment 3, due Friday Nov 20, 10pm

    Assignment 4, due Monday Dec 07, 10pm

    Term project scheduling.