CO 781, Theory of quantum communication, Spring 2010


Debbie Leung

Email: wcleung(at)uwaterloo(dot)ca


TTh 2:30-3:50pm, **** MC 5168 **** (let's not deal with that projector anymore)


May 6th (Thur) lecture moved to 1:30-2:50pm. Location -- MC 4064 not available at 1:30pm. So, meet at the small research room MC 5168. If the bigger classroom classroom is available by 2pm (still awaiting reply), we will move middle of the class.

May 11th (Tue) lecture rescheduled/canceled.

July 1st (Thur) is UW holiday.

Instructor office hours:

After class (except May 6th, June 1st, probably June 10, July 6th)

You can email your question or email to set up an appointment


Posted Aug 03, 6:47pm

Presentations posted (3 are still missing).

Posted Jul 20, 5:24pm

Notes from William Matthews for lectures 19-20 posted.

Posted Jul 20, 3:47am

Notes for lecture 21 posted. Part I is on the Rocket channel, part II on continuity.

Posted Jul 14, 7:32pm

Notes for lecture 16 reposted. Part I is on the Brady bunch and is the same as before. Part II is on the additivity of bound and noiseless resources, and this part has been corrected.

Posted Jul 13, 1:11pm

Notes for lecture 19 posted.

Posted Jul 13, 1:11am

Assignment 3 posted. Due July 29th. Also, notes for lecture 18 posted.

Posted Jul 5, 1:11am

Lecture notes for lecture 17 posted. For lecture 16, the second part concerning various proofs of additivity of noiseless resources will be replaced end of this week.

Posted Jun 29, 4:22am

Lecture notes for lecture 16 posted.

Posted Jun 27, 2:54am

Lecture notes for lecture 15 reposted. Several issues raised in class discussed in more detail in the appendix. Some minor corrections made as well.

Posted Jun 24, 4:32am

Lecture notes for lecture 15 posted. Note that there are 2 separate files.

Posted Jun 22, 3:10am

Lecture notes for lecture 14 posted. Last day before we head towards winter again.

Posted Jun 17, 1:23pm

6 more pages of lecture notes for lecture 13 posted as "part 2".

Posted Jun 17, 4:32am

Lecture notes for lecture 13 posted.

Posted Jun 15, 10:45pm

So, the optimality of the max ent state for coherent information proof has a problem -- that the communicated system is NOT independent of what Eve already has. Will fix it later. For now, I left the broken in the notes remarking on what the problem is, and added an earlier proof that only applies to the depolarizing channel. A lot of background materials added. # pages went from 16 to 42.

Posted Jun 15, 3:21am

Notes for lecture 12 posted, will repost with the last few pages after the lecture.

Posted Jun 13, 4:32pm

Notes for lecture 11 replaced now including the last three pages.

Posted Jun 11, 2:32am

Assignment 2 posted.

Posted Jun 10, 4:32am

Notes for lecture 11 posted. Last few pages will be added after class.

Posted Jun 08, 12:32am

Notes for lecture 9 part II replaced (the discussion on monotonicity/the-lack-of now included).

Posted Jun 08, 3:19am

Notes for lecture 10 posted.

Posted Jun 03, 4:22am

Notes for lecture 9 parts I and II posted.

Posted Jun 02, 3:04pm

Notes for lecture 8 part II posted. Please take a look especially if you missed lecture 8, since it's needed for large parts of lecture 9.

Posted Jun 01, 3:40am

Notes for lecture 8 posted. Note also we're moving to MC 5168.

Posted May 27, 3:11am

Notes for lecture 6 part 2 inflated and reloaded as lecture 7 notes (now 41 pages).

Posted May 25, 2:29am

Lecture 6 notes posted ... last bit of lecture 5 rewritten slightly and renamed lecture 6 part 1. Last lecture we had some trouble with the projector and ended up using MC 5168. This time, we will first try MC 4064, and move to MC 5168 if necessary. Note also the due date of assignment 1 moved to coming Thur.

Posted May 26, 11:52am

A1 fixed and replaced.

Posted May 19, 10:16pm

Lecture 5 notes posted ... may simplify slightly later.

Posted May 18, 12:16pm

Supplement to lecture 4 notes posted.

Posted May 18, 2:16am

Lecture 4 notes posted.

Posted May 16, 6:36pm

Minor changes to the notes for lecture 3 made (relative entropy added, some proofs on the board cleaned-up and included, a number changed in the subentropy, a diagram included on the ensemble with 2 states, and finally, the proof for the Holevo bound simplified and a mis-said step removed).

Posted May 13, 12:01pm

I made it back via the ash cloud. So, lecture will be as scheduled. Note that we will use MC 4064. Notes are just posted. Please print your own this time. Will email this announcement as well.

Posted May 9, 8:48am

Notes for lecture 2 "corrected" by removing the page about the swap gate, and assignment 1 posted.

Posted May 8, 11:18am

A mistake was spotted on the assignment question concerning the swap. Well-wishing (for a simple question+answer in this case) can be dangerous. The correct question will be posted soon.

Posted May 8, 9:21am

On background reading (will primarily use Nielsen and Chuang "Quantum Computation and Quantum Information" (Cambridge University Press).

expanded QM version 0 can be found in Sections 1.2-1.3.

some handy mathematical results (mostly linear algebra and matrix analysis) is given in Section 2.1. p62 has a list of the notations commonly used by quantum information scientists.

QM version 1 can be found in Sections 2.2, 2.4-2.5, 8.2-8.3.

Please revise the following in particular (Section 2.4-2.5):

(1) a pure state in a bipartite system can be written as a Schmidt decomposition

(2) tracing one of the system gives a "density matrix" or a mixed state in the other system

We will cover some of the ideas behind nonunitary evolutions end of next lecture.

Posted May 5, 1:47pm

Meet at small research room MC 5168 at 1:30pm. Sorry for the crowdedness, but the last time.

Posted May 5, 2:28am

Website slowly being constructed, lecture 1 notes uploaded with teleportation argument fixed.

Progress, forecast, and lecture notes:

Lecture 1, May 4th, 2010. Notes

Covered asymptotic equipartition theorem (AEP), briefly went through QM version 0, superdense coding and teleportation, concept of simulation and resource inequalities.

Lecture 2, May 6th, 2010. Notes 6-in-1 b/w printer format

Covered optimality proofs for superdense coding and teleportation, introduced cobit (coherent classical communication) which is the exact average resource between the ebit and the qbit. Covered ensembles and quantum data compression.

Lecture 3, May 13th, 2010.Notes 6-in-1 b/w printer format

Covered mutual information and quantum mutual information, accessible information, subentropy, and the Holevo bound. Introduced locking.

Lecture 4, May 18th, 2010. Notes 6-in-1 b/w printer format Supplementary notes 6-in-1 b/w printer format

Covered why entanglement and back communication cannot increase communication rates beyond naive advantages due to superdense coding. Covered locking in detail: (i) relation to entropy uncertainty inequalities and (ii) 5 proof ideas for locking with random basis. (i) and (ii) were condensed from quant-ph/0303088 and 0307104 Appendix B.

Lecture 5, May 20th, 2010. Notes 1 6-in-1 b/w printer format Notes 2 6-in-1 b/w printer format

Covered classical channels and Shannon's noisy coding theorem, except for the less heuristic proof of the direct coding theorem.

Long proof 6-in-1 b/w printer format

Lecture 6, May 25th, 2010. Notes part 1 6-in-1 b/w printer format

Finished direct coding theorem for classical channels, and move to classical communication capacity via quantum channel (will take lecture 6 and 7). Covered pretty good measurement and gentle measurement lemma.

Lecture 7, May 27th, 2010. Notes part 2 6-in-1 b/w printer format

We covered the packing lemma, the Holevo information as asymptotically achievable communication rate for the Q-box, and the HSW theorem for the classical capacity of a quantum channel, as planned!

Lecture 8, Jun 01, 2010. Notes 6-in-1 b/w printer format Notes II for lecture 8 4-in-1 b/w printer format

We discussed how to perform the optimization for the 1-shot Holevo information, for what channels it is known to be equal to the capacity. We've started the discussion on the equivalent additivity conjectures.

Lecture 9, Jun 03, 2010. Notes I 6-in-1 b/w printer format Notes II 6-in-1 b/w printer format

We saw fragments of arguments why the additivity conjectures are equivalent. Then, we discussed the task of transmitting quantum data via quantum channels, quantum error correction, the LSD theorem for quantum capacity of a quantum channel, and the properties of the coherent information.

Lecture 10, Jun 08, 2010. Notes 6-in-1 b/w printer format

We derived the LSD theorem (omitting some proofs). To do so, we covered Fannes inequality, the decoupling lemma, Uhlmann's theorem, etc.

Lecture 11, Jun 10, 2010. Notes 6-in-1 b/w printer format

Different approaches and coding methods for the LSD theorem, isometric extensions, complementary channels, degradable and antidegradable channels.

Lecture 12, Jun 15, 2010. Notes 6-in-1 b/w printer format

Capacity of the depolarizing channel. Effect of classical communication on coherent information.

Lecture 13, Jun 17, 2010. Notes 6-in-1 b/w printer format Notes II 6-in-1 b/w printer format

Degenerate QECC and superadditivity of coherent information. Additive extensions and upper bounds to capacities of depolarizing channels.

Lecture 14, Jun 22, 2010. Notes 6-in-1 b/w printer format

Capacity zoo part I: Classical or quantum capacity assisted by entanglement, and quantum capacity assisted by classical communication.

Lecture 15, Jun 24, 2010. Notes 6-in-1 b/w printer format Notes II 6-in-1 b/w printer format

Capacity zoo part II: father & mother protocols, and their children.

Lecture 16, Jun 29, 2010. Notes I 6-in-1 b/w printer format Notes II (corrected) 6-in-1 b/w printer format

The Brady bunch -- children of the father & mother, and no-go for catalysis of capacities by noiseless resources.

Lecture 17, July 6, 2010. Notes 6-in-1 b/w printer format


Lecture 18, July 8, 2010 (guest lecture by Motohisa Fukuda) Notes

Violation of additivity of Holevo information

Lectures 19-20, July 13,15, 2010 (guest lectures by William Matthews) Circuit (given in class) Notes (new)

The Quantum reverse Shannon theorem

Lecture 21, July 20: The rocket channel, and many separations of capacities. Continuity of channel capacities. Notes I 6-in-1 b/w printer format Notes II (corrected) 6-in-1 b/w printer format

Lectures 22-23, July 22, 27: Student presentations.

July 22:

Yingkai Ouyang: On Degradable Quantum Channels

Nicholas LeCompte: Squashed entanglement Addenda

Patrick Xian: Systematic approach towards decoupling in NMR quantum computation

July 27:

Chris Granade: Cryptographic distinguishability measures for quantum-mechanical states

Stacey Jeffery: Universally-composable Security of Key Distribution

Jonathan Lavoie: Optimality of the Pretty Good Measurement


Assignment 1 Due May 30. The goal is to help you understand the material, so, please feel free to ask questions if you want help. Also, there can be typos or other problems in the questions. Asking can likely help debug the assignment!

Assignment 2 Hand out end of May, due end of June, on mutual information (both quantum and classical), accessible information, Holevo information, and classical capacities.

Assignment 3 Due July 29th, on the quantum and the entanglement-assisted classical capacity of a quantum channel.


Click to email me.