18.419 Course Home Page

Office Hours

Wednesdays, 1:30-3:00 or by appointment

This term, I am teaching 18.419, Seminar in Theoretical Computer Science. It meets Tuesday and Thursday at 2:30 in room 4-370. In this course, we will be reading papers in quantum computing and information theory. The topics I will be covering are going to be somewhat different from the topics listed in the catalog, since Ike Chuang is also teaching an advanced quantum information theory course this term (8.371J), and I don't want to overlap too much. Here's a tentative syllabus. I've left some gaps in it so that we can add extra papers, if anybody wants to present a paper that isn't on it, or so that we can catch up if some papers take more time than one lecture.
Quantum Complexity Theory
Tues. 02/03:
Introduction, the formalism of Quantum operations
Thur. 02/05:
Quantum space-bounded computation. We will be going over the papers "On the Complexity of Simulating Space-Bounded Quantum Computations" and "Space-bounded quantum complexity" which can be found on John Watrous' web page
Tues. 02/10:
We'll be finishing space-bounded complexity, and going over the proof that local Hamiltonian is complete for QMA, which can be found in the "Classical and Quantum Computation," by Kitaev, Vyalyi, and Shen (pp. 144-151).
Thur. 02/12:
We'll be finishing QMA, and go over "Succinct quantum proofs for properties of finite groups," by John Watrous, which can be found on John Watrous' web page
Tues. 02/17:
no class for President's day (Monday schedule)
Thur. 02/19:
I'll be going over Kitaev and Watrous "Parallelization, amplification, and exponential time simulation of quantum interactive proof systems," which can be found on here on citeseer, and also probably talk a little about "PSPACE has constant-round interactive proof systems," which can be found John Watrous' web page
Tues. 02/24:
Mariott and Watrous, "Quantum Arthur-Merlin Games," on John Watrous' web page
Thur. 02/26:
Last class on quantum complexity. I'm leaving a gap here in case the previous things run over. If they don't, I can talk about multiple-prover quantum interactive proofs.
Thur. 03/02:
Introduction to quantum channel capacities, classical Shannon theory, quantum entropy, entropy inequalities.
Thur. 03/04:
Schumacher coding. Jozsa and Schumacher, "A new proof of the quantum noiseless coding theorem," available from citeseer. This (and Schumacher's single-authored nearly simultaneously published paper here on citeseer) were the first papers on quantum data compression. Presented by Stephen Jordan
Tues. 03/09:
"Classical information capacity of a quantum noiseless channel," by Hausladen, Schumacher, Westmoreland, Wooters. available from citeseer There is also a good set of slides for a talk on this paper here on Schumacher's website (Lecture 4), presented by Brent Yan
Thur. 03/11:
Entanglement assisted capacity. The entanglement-assisted capacity formula is proved for a small class of channels in quant-ph/9904023 A generalization of this formula is proved for all channels in quant-ph/0402129, (although for the full proof of general entanglement-assisted capacity formula you need to use some entropy inequalities found in quant-ph/0106052 and quant-ph/0106075)
Tues. 03/16:
Private capacity and quantum capacity of quantum channels quant-ph/0304127
Thur. 03/18:
We will finish up the "Private capacity and quantum capacity ..." and start "Family of protocols for capacities of quantum channels" quant-ph/0308044
Tues. 03/23:
Spring Vacation
Thur. 03/25:
Spring Vacation
Tues. 03/30:
Family of protocols for capacities of quantum channels quant-ph/0308044
Thur. 04/01:
Fault tolerance by decoherence free subspaces This is contained in quant-ph/9908064, and possibly the followup quant-ph/0007013.
Tues. 04/06:
Quantum toric codes. presented by Victor Brar
Thur. 04/08:
Topological quantum memory quant-ph/0110143.
Tues. 04/13:
Quantum computation by anyons: presented by Cary
Thur. 04/15:
Quantum entanglement distillation and quantum capacities with a supplemental back channel. Topics taken from papers quant-ph/9511027. quant-ph/0003040. quant-ph/0102036.
Tues. 04/20:
Patriots Day
Thur. 04/22:
Quantum cryptography: Bennett and Brassard 84; Bennett 92; Shor and Preskill 2000
Tues. 04/27:
Oops ... I just realized I gave the wrong quant-ph number for the first paper in this week. I've fixed it below. Security proofs of Bennett 92 quant-ph/0212162. quant-ph/0308048.
Thur. 04/29:
Quantum vs. classical memory presented by Fen Zhao quan`t-ph/0305154.
Tues. 05/04:
Algorithm for dihedral hidden subgroup problem, by Kuperberg quant-ph/0302112, presented by Aram Harrow.
Thur. 05/06:
Other new quantum algorithms. (Pell's equation, quant-ph/0302134, and if we have time, hidden shift problems quant-ph/0211140,
Tues. 05/11:
David Milovich "A lambda calculus for quantum computation" quant-ph/0307150,
Thur. 05/13:
Debajyoti Bera This paper on one dimensional random walks, and Absorption problems for quantum walks in one dimension, quant-ph/0208122, and I'll talk a little bit about quantum communication complexity if there's any time left over.
I am open to suggestions from students as to other areas to cover.