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, live on zoom (+recording).

Each week, instructor will provide 1 hour of self-study material for students to complete before the Tue class.

Office hours:

After class and by appointment. Additional possibilities: student-organized weekly live discussions, chat group (piazza or Slack).


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
  • A wonder public lecture by Charles Bennett at Qiskit that also previews some of the topics and illustrate the spirit of the course.

    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?
  • No free lunch -- the no signalling principle
  • Surprise nonadditivity -- Superdense coding (SD) and teleportation (TP)
  • Optimality and duality of SD and TP
  • Good enough means good anywhere -- simulations and resource inequalities
  • 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 resulting in a presentation and a term paper due end of the term (40%)


    Posted July 31, 2020, 16:39

    Revised live discussion time.

    Posted July 09, 2020, 23:59

    Webpage was set up.