Theory of Quantum Communication, Fall 2016
Debbie Leung
Email: wcleung(at)uwaterloo(dot)ca
Starting Sept 08: Tue/Thur 1:00-2:20pm, QNC 1201
In general: after class Tue/Thur. After answering quick questions at the classroom, I will move to my office QNC 3313. Students having a class that time can arrange alternative office hours on an individual basis.
Communication is an integral part of information processing. For instance, data compression, data storage, gates acting on multiple systems, as well as sending data over a distance are all special cases of communication.
This course is concerned with the fundamental limits of communication, whereby we learn about communication and also the physical theory behind:
1. We cover important results in the theory of quantum communication.
For example: superdense coding, teleportation, data compression, noisy channel coding theorems (both classical and quantum settings), how auxiliary resources like entanglement or feedback can improve communication, and superactivation, zero-error communication.2. We study fundamental concepts widely used in quantum communication that applies broadly to other aspects of quantum information. Examples include:
General:
Specific to the course:
Based on the above links for the courses:
Students should have good understanding of 4 lectures in QIC 710 before the term starts:
Students who wish to take QIC 710 and this course simultaneously are encouraged to self-study the above.
The current course will have partial overlaps with the following:
In QIC 710:
Lecture 15 will be given as reading assignment as the course progress, and we will fully cover the materials in lectures 13-14, and 16.
In QIC 820:
This more mathematically advanced treatment of the subjects can deepen your understanding of the subject, but will not be assumed as pre-requisite to the course.
4 Assignments (total 60%). Each will be given out upon completion of a topic, and due 7-10 days later.
1 term project resulting in a term paper and a presentation second half of November (40%).
Posted Aug 12, 2016, 23:59
Webpage was set up.
Posted Sept 07, 2016, 18:00
Topics and tentative plan included.
Posted Sept 08, 2016, 12:30
Notes for lecture 1 posted.
Posted Sept 13, 2016, 12:30
Notes for lecture 2 posted.
Posted Sept 13, 2016, 15:20
Notes for lecture 2 modified (we now distinguish m from M, b from B etc in the proof of C2).
Posted Sept 14, 2016, 21:40
Notes for lecture 3 posted.
Posted Sept 15, 2016, 17:30
Notes for last part of discussion for lecture 3 posted.
Posted Sept 19, 2016, 18:55
Notes for lectures 4-5 posted.
Posted Sept 22, 2016, 12:35
Additional notes for lectures 5 posted.
Posted Sept 22, 2016, 12:35
Preliminary version of A1 posted.
Posted Sept 22, 2016, 17:15
Small changes to the RSP and SD notes made, and they're now merged into one file.
Posted Sept 23, 2016, 03:15
Updated version of A1 posted.
Posted Sept 24, 2016, 01:15
3rd version of A1 posted, including a little more information for solving the problems, and tweaking some notations for better clarity.
Posted Sept 24, 2016, 18:00
In Q2a, each G_k is CP (completely positive) but not necessarily trace preserving.
Posted Sept 27, 2016, 12:25
Notes for lecture 6 posted.
Posted Sept 27, 2016, 18:15
Notes for lecture 6 re-posted.
Further clarifications and corrections to assignment 1.
It is intended that in Q1, the given cbits and the desired qbit are in the same direction (from Alice to Bob), while in Q2, the proof is structured to apply even with cbits in both directions. If you try hard enough, you can extend the proof in Q1 for two way cbits. But the real value of Q1 is an extension to channels in which Eve has an output that can be turned into Bob's output; these channels are called antidegradable and we will come back to this topic later. For Q3, the state $|\tilde{\phi}>$ transmitted to Bob should be $\rho_{\phi}$ (a state that depends on $|\phi>$). It can be mixed. My apologies.
Posted Sept 28, 2016, 17:00
Notes for lecture 7 posted.
Posted Sept 29, 2016, 15:30
Additional notes for lecture 7 posted.
Posted Oct 03, 2016, 18:15
Notes for lecture 8 posted.
Posted Oct 04, 2016, 12:25
Assignment 2 was posted.
Posted Oct 04, 2016, 16:15
Notes called "additional notes on entanglement dilution and concentration" reposted, with the circuit diagram for entanglement dilution included. The diagram is color-coded to make the resource transformation more obvious.
Posted Oct 04, 2016, 16:20
There is no Oct 11 lecture due to fall study period. The tentative plan of the course has been adjusted.
Posted Oct 05, 2016, 23:00
Notes for lecture 9 posted.
Posted Oct 13, 2016, 12:20
Notes for lecture 9 reposted (with an additional last page on the intuition).
Notes for the converse posted under "lecture 9" (but will be covered in lecture 10).
Notes for properties of quantum entropies posted as "lecture 10".
Posted Oct 17, 2016, 18:20
Notes for lecture 11 posted.
Lecture 11 starts 12:30pm Oct 18, 2016.
A2 due latest in class tomorrow.
Posted Oct 18, 2016, 18:40
NO LECTURE ON THUR OCT 20.
Posted Oct 25, 2016, 12:50
Notes for lecture 12 posted.
Posted Oct 26, 2016, 18:30
Notes for lecture 12 reposted, continuing to lecture 13.
Posted Oct 26, 2016, 18:35
I believe the last two lectures are Nov 29 and Dec 01. The plan is to have student presentations those two days, starting 12:30pm (to also make up for the missing lecture time on Oct 20). Please contact me for a topic if you haven't done so, and especially if you'd like to have a project on topic 5 or 6.
Posted Nov 02, 2016, 17:15
Notes for lecture 15 posted. We will finish off the last 5 pages of the previous lecture notes (repeated in the new pdf file) concerning the optimal ensemble for Holevo information, followed by a discussion of additivity. Depending on time and interest, we will cover parts of the notes uploaded (largely borrowed from previous years).
Posted Nov 03, 2016, 01:15
Assignment 3 posted.
Posted Nov 08, 2016, 12:50
Notes for lecture 16 posted.
Posted Nov 10, 2016, 12:50
Notes for lecture 17 posted, has some overlap with last set of notes.
Posted Nov 22, 2016, 12:40
Assignment 4 and notes for lecture 20-21 posted. Details for the presentation will be available later today.
Posted Nov 29, 2016, 12:50
Notes for a 20 min discussion of superactivation for lecture 22 posted, where the notes for lectures 20 and 21 are.
Topic 1 -- There is no free lunch [2.5 weeks]
Superdense coding (SD) and teleportation (TP), optimality and duality. The no signalling principle and consequences. Optimality of SD and TP. Cobits, SD and TP as inverses of one another. Simulations and resource inequalities. Remote state preparation (RSP), the curious cousin of teleportation. Quantum encryption, the unexpected twin of teleportation. Why QM better be linear, and we should avoid time travel.
~ Assignment 1 out Sept 20, due Sept 30.~
Topic 2 -- Entropy and data Compression [1 week]
IID source 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
Topic 3 -- Classical communication via classical channels [1 week]
Conditional entropy, relative entropy, mutual information, and joint typicality Distributed source coding Classical iid channels Error correcting codes. Shannon's noisy coding theorem. The direct coding theorem and the converse
~ No lecture on Oct 11 due to fall study break. ~
~ Assignment 2 out Oct 04, due Oct 14 (a little aheading of the lectures) ~
Topic 4 -- Classical communication via quantum channels [3 weeks]
Extractive classical information from quantum states Accessible information Holevo information, Holevo bound Entanglement and back communication cannot increase communication rates (beyond SD) Locking The HSW theorem for the classical capacity of a quantum channel Omitted 2016: (Tools: pretty good measurement, gentle measurement lemma, conditional typicality, random codes) Additivity issues, the existence of counterexamples.
~ Class cancelled Oct 20. Discuss make up class. ~
~ Assignment 3 out Nov 03, due Nov 11 ~
Topic 5 -- Quantum communication via quantum channel [2-3 weeks]
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) 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
~ This topic starts Nov 8, with 4.5 weeks of lecture remaining. Term project should be chosen no later than Nov 8.
~ Assignment 4 out Nov 17, due Nov 24 ~
Topic 6 -- Other capacities [? week]
Private capacity Entanglement assisted quantum/classical capacity Quantum capacity assisted by free classical communication No-go for catalysis of capacities by noiseless resources Separations of capacities Superactivation Rocket channel Entanglement assisted zero-error communication
~ No assignment ~
Student presentations -- To be scheduled. Term paper due Dec 5.
Communication setting, superdense coding and teleportation, circuit diagrams, and resource inequalities.
The non-signalling principle as a basic principle in communication theory, consequences.
Lecture 3, Sept 15, 2016. Additional notes for gates.
Optimality of superdense coding and teleportatio, cobits, superdense coding and teleportation with cobits as inverses of one another. Cobits and bipartite quantum gates.
One to one correspondence between generalized teleportation and generalized quantum encryption.Lecture 5, Sept 22, 2016. (1) remote state preparation & superdense coding. (2) Notes on beyond QM.
An example of non composably-good qbit: remote state preparation. Additional discussion on superdense coding. Beyond QM.
Assignment 1 (updated Sept 24, 01:15).
Further corrections:
In Q2a, each G_k is a CP map that is not necessary trace preserving. It is intended that in Q1, the given cbits and the desired qbit are in the same direction (from Alice to Bob), while in Q2, the proof is structured to apply even with cbits in both directions. If you try hard enough, you can extend the proof in Q1 for two way cbits. But the real value of Q1 is an extension to channels in which Eve has an output that can be turned into Bob's output; these channels are called antidegradable and we will come back to this topic later. For Q3, the state $|\tilde{\phi}>$ transmitted to Bob should be $\rho_{\phi}$ (a state that depends on $|\phi>$). It can be mixed. My apologies.
Asymptotic equipartition theorem, Shannon entropy, data compression.
Lecture 7, Sept 29, 2016 (part I), additional notes on entanglement dilution and concentration.
von Neumann entropy, quantum sources, and quantum data compression.
Conditional entropy, relative entropy, mutual information, and joint typicality.
Lecture 9, Oct 06, 2016.
Shannon's noisy channel coding theorem, up to direct coding theorem. Converse, covered on Oct 13.
Properties of quantum entropies.
Lecture 11-12, Oct 18-25, 2016.
Encoding classical data in quantum states, and retrieving it. Accessible information, Holevo bound, locking, and subentropy.
Lecture 12-13, Oct 25-27, 2016.
Capacity of Q boxes (updated). Gentle measurement lemma, PGM, packing lemma, direct coding theorem, converse.
Lecture 14, Nov 01, 2016, part 1, part 2.
Part 1: example of Q-box capacity. Part 2: HSW theorem for the classical capacity of quantum channels.
Optimal ensemble for Holevo information and nonadditivity, equivalences of additivity conjectures (if time permits).
Transmitting quantum data through quantum channels, coherent information, LSD theorem, decoupling approach. Proof for Thm 3 of 0702005.
Decoupling approach with approximations, direct coding for the LSD theorem.
Consequencs for the LSD theorem (I). Degradable channels.
Lecture 19, Nov 17, 2016 Part I Lecture 19, Nov 17, 2016 Part II.
Consequencs for the LSD theorem (II). Random Pauli channels, non-degenerate random stabilizer code, depolarizing channel, degenerate QECCs, and non-additivity of 1-shot coherent information.
Lecture 20-22, Nov 22-29, 2016 Part I Part II Part III Part IV
Upper bounds for quantum capacities using additive extensions. Assisted capacities. Quantum reverse Shannon theorem. Rocket channel and the separation of assisted capacities. Private vs quantum capacity, and superactivation.
Lecture 21-24. Student presentations.
Nov 24
Nicholas Funai: Quantum State Cloning Using Deutschian Closed timelike curves?
Nov 29
Ink Tansuwannont: Approximate quantum error correction and 4-bit code for amplitude damping channel
Shima Bab Hadiashar: Entanglement Spread
Dec 01
Ala Shayeghi: Approximate degradable quantum channels
Benjamin Lovitz: Limitations on separable measurements by convex optimization
Jason LeGrow: Information Locking
Dec 06
Hamoon Mousavi: Entanglement assisted classical capacity
Maria Kieferova: Noisy Interactive Quantum Communication
Maria Sobchuk: Zero error communication assisted by entanglement and nonlocal correlations