QIC 890/CO 781:

Theory of Quantum Communication, Fall 2012


Debbie Leung

Email: wcleung(at)uwaterloo(dot)ca


Starting Sept 11: Tue/Thur 1:05-1:25pm, RAC1 2009 (until IQC moves to QNC)

Instructor office hours:

In general: you can just drop by my RAC office Mon/Tue/Thur afternoons. Note exceptions due to colloquium, Tue/Thur seminars, and of course, if you want to be sure I'm in, email me first.


  • Richard Cleve's lecture notes for QIC 710 (cumulative)
  • John Watrous' lecture notes for QIC 820 / CS 766 (F2011)
  • My lecture notes for QIC 890 / CO 781 (S2010)
  • Textbook by Nielsen and Chuang
  • Mark Wilde's text book
  • Requirements:

    7 assignments (70%)

    1 term project resulting in a term paper and a presentation (30%)


    Posted Sept 04, 2012, 01:00

    Webpage was set up.

    Posted Sept 11, 2012, 02:45

    This concerns the reference from QIC 710:

    Besides F2008 Lec 1-3 p10-22, F2009 Lec 14-15 (stated in the handout) the following can be particularly helpful:

    F2008 Lec 1-3 p20-22, p33-37 describe in detail what happens if one unitarily transforms or measures one out of two systems, p31-43 has a much longer version of teleportation, and p44-47 discusses no cloning.

    F2008 Lec 10-14 p66-69 covers trace and partial trace, p71-77 covers general quantum operations.

    Posted Sept 13, 2012, 01:00

    Assignment 1 was posted.

    Posted Sept 18, 2012, 01:50

    Preskill's Ph229 lecture notes, Chapter 5 p20-28 has a nice description of quantum data compression.

    Posted Sept 21, 2012, 02:18

    Assignment 2 was posted.

    Course outline, tentative schedule of lectures and assignments:

    Topic 1 -- Converting noiseless resources [2 lectures]

  • Primitives & axioms for quantum communication.
  • Superdense coding (SD) and teleportation (TP), optimality and duality.
  • Concepts of simulation and resource inequalities.
  • Cobits, SD and TP as inverses of one another.
  • Cryptographic properties of SD and TP (optional)
  • ~ Assignment 1 out Sept 13, due Sept 20.~

    Topic 2 -- Data Compression [1.5 lectures]

  • Asymptotic equipartition theorem (AEP)
  • Data compression (Shannon's noiseless coding theorem)
  • Shannon entropy
  • Quantum ensembles and quantum data compression
  • Von Neumann entropy
  • Topic 3 -- Quantifying information [2.5 lectures]

  • Conditional entropy and mutual information in the classical and quantum cases.
  • ~ Assignment 2 out Sept 20, due Sept 27 ~

  • Strong subadditivity and monotonicity of quantum mutual information, Araki-Lieb inequality
  • Accessible information
  • Holevo information, Holevo bound
  • Changes in entropy, accessible information, and Holevo information caused by communication, locking
  • Bounds on the Holevo information (and a bit of reflection)
  • Entanglement and back communication cannot increase communication rates (beyond SD)
  • ~ Assignment 3 out Sept 27, due Oct 4 ~

    Topic 4 -- Classical communication via classical channels [2 lectures]

  • Classical iid channels
  • Shannon's noisy coding theorem.
  • Converse, and the direct coding theorem
  • Topic 5 -- Classical communication via quantum channel [4 lectures]

  • The HSW theorem for the classical capacity of a quantum channel
  • (Tools: pretty good measurement, gentle measurement lemma, conditional typicality, random codes)
  • Additivity issues, the existence of counterexamples.
  • ~ Assignment 4 out Oct 9, due Oct 18 ~

    Topic 6 -- Quantum communication via quantum channel [4 lectures, starting week 7]

  • Definition of the quantum capacity and different measures for transmission with vanishing error.
  • Quantum error correcting codes
  • Coherent information of quantum states and quantum channels
  • The LSD theorem for the quantum capacity of a quantum channel
  • (Tools: Fannes inequality (converse), decoupling lemma (direct coding), Ulhmann's theorem, random codes)
  • ~ Assignment 5 out Oct 25, due Nov 01 ~

  • Different approaches and coding methods for the LSD theorem
  • Isometric extensions and complementary channels
  • Degradable and antidegradable channels (where LSD works)
  • Upper and lower bounds of quantum capacities, additive extensions, zero capacity conditions
  • Degenerate codes and statement of superactivation
  • ~ Assignment 6 out Nov 01, due Nov 08 ~

    Topic 7 -- Assisted capacities [5 lectures, starting week 8]

  • Entanglement assisted quantum capacity
  • Quantum capacity assisted by free classical communication
  • Mixed state entanglement purification and error correction (optional)
  • The Brady bunch
  • No-go for catalysis of capacities by noiseless resources
  • Separations of capacities
  • Superactivation
  • Rocket channel
  • ~ Assignment 7 out Nov 13, due Nov 20

    Topic 8 -- Selected topics [2 lectures], from:

  • Gaussian channels
  • The Quantum reverse Shannon theorem
  • Continuity of channel capacities
  • Network coding
  • Two-way channels
  • Zero-error communication
  • NB. Nov 15 class cancelled.

    NB. Timing and plans for topics 7 and 8 more tentative, until further notice.

    Student presentations -- Nov 27, 29. Term paper due Nov 29.

    Notes for some of the lectures:

    Lecture 2, Sept 13, 2012.

    Basic principles in communication theory, optimality of superdense coding and teleportation, cobit, duality of superdense coding and teleportation with cobits.

    Lecture 3, Sept 18, 2012.

    Asymptotic equipartition theorem, Shannon entropy, data compression, and quantum sources.

    Lecture 4, Sept 20, 2012.

    von Neumann entropy, Schumacher compression, properties of Shannon entropy, conditional entropy, relative entropy, and mutual information.

    Lecture 5, Sept 25, 2012.

    Quantum conditional entropy, quantum relative entropy, and quantum mutual information, and their properties. Strong subadditivity, monotonity of quantum mutual information, Araki-Lieb inequality, Holevo information for an ensemble (as the quantum mutual information of a classical-quantum system).

    Lecture 6, Sept 27, 2012.

    Accessible information, progress towards finding optimal measurements, Peres-Wootters example, lower and upper bounds, Holevo bound. [Lec 7: Communication bounds with two-way quantum communication, locking of accessible information.]

    Lecture 7-8, Oct 02-04, 2012.

    Classical channels, definition of achievable rates and channel capacity, Shannon noisy channel coding theorem. [Lec 9: Fanos inequality and data processing inequality]

    Lecture 9, Oct 09, 2012.

    Q-boxes, statement of classical capacity of Q-boxes, gentle measurement lemma, and pretty good measurement.

    Lecture 10, Oct 11, 2012.

    The packing lemma, and the direct coding theorem for the capacity of the Q-boxes.

    Lecture 11, Oct 16, 2012.

    The converse for the capacity theorem for Q-boxes. The HSW theorem for the classical capacity of a quantum channel. Consequences of the HSW theorem, and discussion on the "1-shot capacity".

    Lecture 12, Oct 18, 2012.

    Additivity and violation of additivity of the Holevo information. Equivalences of 4 additivity conjectures.

    Definition of quantum capacities, and different measures of faithful transmission of quantum states.

    Lecture 13, Oct 23, 2012.

    Further discussion in distance measures of channels.

    Quantum error correcting codes, brief discussion of degenerate codes and the stabilizer formalism, coherent information of quantum states.

    Lecture 14, Oct 25, 2012.

    Properties of coherent information, statement of the LSD (Lloyd-Shor-Devetak) theorem for the quantum capacity of a quantum channel, the converse, and the decoupling lemma.

    Lecture 15, Oct 30, 2012.

    Direct coding half of the LSD theorem. Variations on the codes and proofs (not covered in class). Complementary channel.

    Lecture 16, Nov 01, 2012.

    Degradable and antidegradable channels. Zero quantum capacity for antidegradable channels. Additivity of the 1-shot quantum capacity for degradable channels. Quantum capacity of the erasure channel and the dephasing channel. Characterization of degradable channels. Random Pauli channels, depolarizing channels, non-degradability, and their 1-shot capacity.

    Lecture 17, Nov 06, 2012 (as given in class) .

    Corresponding lecture notes from Spring 2010 (with more mathematical details) Part I Part II. Note the slightly different conventions (for example, q here is p above) compared to Graeme's guest lecture.

    Depolarizing channels, upper bound on rate achievable by non-degenerate codes (Hamming bound), degenerate codes that extend the nonzero capacity region (thus also showing the nonadditivity of the 1-shot quantum capacity). Additive extension, and upper bounds of quantum capacity of the depolarizing channel by convex decomposition into degradable channels.

    Lecture 18, Nov 08, 2012 (as given in class) .

    Corresponding lecture notes from Spring 2010

    Symmetric side channel assisted quantum capacity of a quantum channel, additivity of this capacity, private capacity of a quantum channel, PPT states and privacy, superactivation of quantum capacity, and the 50-50 erasure channel as a special symmetric side channel.

    Lecture 19, Nov 13, 2012.

    Assisted capacities. Entanglement assisted classical capacity of a quantum channel, additivity, converse and direct coding.

    Lecture 20, Nov 20, 2012.

    Entanglement assisted classical capacities for specific channels. Properties of entanglement assisted classical capacities, and relation to entanglement assisted quantum capacities, reverse Shannon theorem (both quantum and classical). Quantum capacities assisted by free classical communication. Free forward classical communication does not increasing quantum capacity of a quantum channel.

    Lecture 21, Nov 22, 2012.

    Quantum capacities assisted by free back classical communication, or free 2-way classical communication. Hierarchy of capacities. Rocket channel demonstrated much larger assisted capacities than unassisted capacities, and large violations of additivity.

    Lecture 22, Nov 27, 2012

    Kent Fisher: all about superactivation

    Michal Kotowski: entanglement spread and non-maximally entangled states

    Entanglement purification and 1-way assisted quantum capacities of quantum channel.

    Lecture 23, Nov 29, 2012

    Young Han: Universal Gate Construction with Quantum Teleportation

    Takafumi Nakano: (Part of) equivalence of additivity conjectures

    Family of protocols (the Brady bunch)


    Assignment 1, due Sept 20, 2012 in class.

    Assignment 2, due Sept 27, 2012 in class.

    Assignment 3, due Oct 04, 2012 in class.

    Assignment 4, due Oct 18, 2012 in class.

    Assignment 5, due Nov 01, 2012 in class.

    Assignment 6, due Nov 08, 2012 in class.

    Assignment 7, due Nov 15, 2012 in mailbox.

    Possible project topics (more and more will be added throughout the term):

    Visible communication

    Capacity of unitary two-way channels

    Optimal measurements for accessible information

    Hypothesis testing and relative entropy


    Codes for data compression

    Efficient high rate codes

    Optimality of pretty good measurements

    Equivalences of the 4 additivity conjectures

    Non-additivity of Holevo information

    Randomized arguments in quantum information

    Quantum error correcting codes

    Private capacity

    The above is not an exhaustive list. In particular, many items in the "selected topics" will not be covered in class in the end, and can be used for projects.

    Each student should choose a project topic by early Nov, and discuss the suitability with the instruction. The projects are intended to further investigate subjects relevant to the course, and students are encouraged to choose a topic relevant to their research. A project should not be something the student already knows.

    Presentation should be given in class last week of the term, along with a term paper between 6-15 pages.