Theory of Quantum Communication, Fall 2020
Debbie Leung
Email: wcleung(at)uwaterloo(dot)ca
Tue/Thur 11-12:15, live on zoom (+recordings).
Supplemented with weekly self-study material when appropriate.
After class or by appointment. Slack discussion.
Posted Dec 05, 2020, 01:45
(1) Term project scheduling finalized.
(2) Notes for lecture 24 revised.
Posted Dec 03, 2020, 15:30
(1) A quick note that Crowdmark will be going through scheduled maintenance on Sunday December 6, 2020 from 6:00am to 8:00am ET.
(2) Posted video for today's lecture.
(3) Notes for today's lecture revised.
Posted Dec 02, 2020, 18:40
Notes for guest lecture by Felix Leditzky posted.
Posted Dec 01, 2020, 17:30
Posted Dec 01, 2020, 00:05
Term project scheduling posted here.
Posted Nov 30, 2020, 23:40
Lecture notes for topic 5, part 6 posted. Lectute notes for topic 5, part 5, additional section on low-noise channels added.
Posted Nov 26, 2020, 15:00
Posted Nov 26, 2020, 03:25
Lecture notes for topic 5, part 5 posted.
Posted Nov 25, 2020, 02:00
Posted assignment 4. A Crowdmark invitation to submit your solutions has been sent.
Posted Nov 24, 2020, 16:00
Posted Nov 24, 2020, 03:10
Lecture notes for topic 5, part 4 posted.
Posted Nov 19, 2020, 17:20
Posted Nov 19, 2020, 01:40
Lecture notes for topic 5, part 3 posted.
Posted Nov 19, 2020, 01:40
Corrected lecture notes for topic 5, part 2 posted.
Posted Nov 17, 2020, 15:00
Posted Nov 17, 2020, 03:10
Lecture notes for topic 5, part 2 posted.
Posted Nov 12, 2020, 13:30
Posted Nov 12, 2020, 00:02
Lecture notes for topic 5, part 1 posted.
Posted Nov 10, 2020, 15:20
Posted Nov 10, 2020, 03:50
Lecture notes for topic 4, part 5 posted.
Posted Nov 08, 2020, 13:30
Posted assignment 3. A Crowdmark invitation to submit your solutions will be sent later tonight.
Posted Nov 05, 2020, 22:20
Posted Nov 05, 2020, 04:25
Lecture notes for topic 4, part 4 posted.
Posted Nov 03, 2020, 15:30
Posted Nov 03, 2020, 03:45
Lecture notes for topic 4, part 3 (part 2 ctd) posted.
Posted Nov 01, 2020, 20:30
Posted term project information. A Crowdmark invitation to submit proposal and 3-page abstract will be sent shortly.
Posted Oct 29, 2020, 18:30
Posted Oct 29, 2020, 03:30
Lecture notes for topic 4, part 2 posted.
Posted Oct 27, 2020, 14:45
Posted video for today's lecture.
Solutions to A1 posted on Slack under "general".
Posted Oct 27, 2020, 02:45
Lecture notes and slides for topic 4, part 1 posted.
Posted Oct 25, 2020, 00:20
A couple of typos on A2 part (h) have been found. Instead of changing the file, please check this thread for the corrections.
Posted Oct 23, 2020, 16:00
A small glitch with the poll has been fixed. Same link to access as previous announcement.
Posted Oct 23, 2020, 15:00
To help adjust the pace, the content, and the level of difficulty for the course, please participate in an online poll. You can also find it directly on Slack, under "general". Let's poll until 23:59 Sunday.
Posted Oct 22, 2020, 17:15
Posted Oct 22, 2020, 02:45
Lecture slides for topic 3, part 3 posted.
These slides are similar to the notes posted last week.
Posted Oct 20, 2020, 16:30
Posted Oct 20, 2020, 02:15
Lecture slides for topic 3, part 1 topic 3, part 2 posted.
These slides are about identical to the notes posted last week.
Posted Oct 17, 2020, 17:30
Posted assignment 2. A Crowdmark invitation to submit your solutions will be sent shortly.
Posted Oct 12, 2020, 23:55
(1) No classes on Oct 13, Oct 15, since it is reading week in UW.
(2) Self-study for this week: properties of Shannon entropy and mutual information. Click here for instruction.
(3) Next week (Oct 20 and 22), we will cover Shannon's noisy channel coding theorem. Click here for notes (from 2016).
(4) A2 will be posted mid-week.
Posted Oct 08, 2020, 14:30
(1) Posted video for today's lecture.
(2) A quick reminder that A1 is due tomorrow night. The problems are less intended to be puzzles that you solve on your own, but rather exercises that you learn in the process. The criteria is that you write up your own solutions. To arrive at these solutions, you can discuss questions, thoughts, solutions openly on Slack, and / or consult literature, instructor, or classmates. If you need a little more time, it is also OK.
Posted Oct 08, 2020, 03:15
Lecture notes for topic 2, part 3 posted. AQIS slides on embezzlement also posted.
Posted Oct 06, 2020, 15:40
Posted Oct 06, 2020, 02:30
Posted Oct 01, 2020, 14:00
Posted Oct 01, 2020, 13:00
Please go through the first 2 pages of this set of notes before next lecture! This defines the typical space for n copies of a density matrix that we need for Tue. Email me, ask on Slack, or come to class 10 mins before 11am on Tue if you have questions.
Posted Oct 01, 2020, 03:15
(1) Lecture notes for topic 2, part 1 posted.
(2) Rememeber the new passcode 781890 (if you use meeting ID).
Posted Sept 30, 2020, 18:00
Our next 2-3 lectures contains lecture 16 in QIC710 by Professor Cleve, but with many components beyond this lecture, so we cannot outsource our lectures. For consistency and self-contain-ness, I will give our lectures without assuming lecture 16 in QIC710. Meanwhile, you can consider a quick revision of his slides ...
Posted Sept 30, 2020, 12:00
(1) A passcode 781890 (concatenation of the course numbers) has been added to the zoom meeting (ID remains 862 6152 0800). Link has been updated accordingly.
(2) Website slightly updated -- class hour now officially 11-12:15, and self-study component demoted.
Posted Sept 29, 2020, 14:15
Posted Sept 29, 2020, 02:30
(1) Additional notes for approximate randomization added.
Posted Sept 26, 2020, 01:30
Posted assignment 1. You should have a Crowdmark invitation to submit your solutions.
Posted Sept 24, 2020, 17:40
Posted Sept 24, 2020, 04:20
Posted Sept 22, 2020, 18:30
Lecture notes for topic 1, part 4 replaced (correcting the dim of A,B on top left diagram on p15).
Posted Sept 22, 2020, 16:40
Posted Sept 22, 2020, 02:20
Posted Sept 21, 2020, 18:00
Posted Sept 17, 2020, 14:10
Posted Sept 17, 2020, 03:00
Posted Sept 15, 2020, 16:00
(1) Posted video for today's lecture. My apologies for forgetting to record in real time. The posted recording was on a repeat of the lecture, recapping some of the lively discussions (thx for the active participation!).
(2) minor corrections are made on the notes for topic 1, part 2.
Posted Sept 14, 2020, 19:05
(1) Lecture notes for topic 1, part 2, completed and replaced.
Posted Sept 10, 2020, 14:45
Posted Sept 10, 2020, 02:15
Posted Sept 08, 2020, 19:45
Posted Sept 08, 2020, 19:15
(1) Here's a list for background reading on density matrices and TCP maps
(2) Lecture notes for topic 1, part 1 replaced with minor corrections.
Posted Sept 08, 2020, 03:50
Posted Sept 07, 2020, 00:50
(1) Self-study material posted. (2) Slack channel invitation sent to those enrolled or those who contacted instructor. You can also email instructor for invitation, or click here to sign up.
Posted Sept 01, 2020, 14:30
Website reorganized. Please return end of this week for self-study material and sign-up instructions.
Posted July 31, 2020, 16:39
Revised live discussion time.
Posted July 09, 2020, 23:59
Webpage was set up.
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:
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
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 Sept 06, 2020.
Brief revision of superdense coding, teleportation, partial trace, and quantum channel.
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.
2020-09-15 Lecture 3: The No-signalling principle and optimality of teleportation and superdense coding
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.
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.
2020-09-29 Lecture 7: Beyond quantum mechanics?
2020-10-01 Lecture 8: Entropy, typicality, asymptotic equipartition theorem, and data compression.
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
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.
2020-10-29 Lecture 14: Accessible information.
2020-11-03 Lecture 15: Accessible information (ctd).
2020-11-05 Lecture 16: Classical capacity of Q-boxes.
2020-11-10 Lecture 17: Classical capacity of quantum channels, HSW theorem.
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)
2020-11-19 Lecture 20: proof of LSD Thm (second half)
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.
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.
2020-09-29 Lecture 7
2020-10-29 Lecture 14
2020-11-26 Lecture 22
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
Please submit all assignments and term paper to Crowdmark.
