18.419 Course Home Page
Office Hours
Wednesdays, 1:303: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 4370. 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 spacebounded computation.
We will be going over the papers
"On the
Complexity of Simulating SpaceBounded Quantum Computations"
and
"Spacebounded quantum complexity"
which can be found on
John Watrous' web page
 Tues. 02/10:

We'll be finishing spacebounded 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. 144151).
 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 constantround
interactive proof systems," which can be found
John Watrous' web page
 Tues. 02/24:

Mariott and Watrous, "Quantum ArthurMerlin 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 multipleprover 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 singleauthored
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 entanglementassisted
capacity formula is proved for a small class of channels in
quantph/9904023
A generalization of this formula is proved for all channels in
quantph/0402129,
(although for the full proof of general entanglementassisted
capacity formula you need to use some entropy inequalities found in
quantph/0106052
and
quantph/0106075)
 Tues. 03/16:

Private capacity and quantum capacity of quantum channels
quantph/0304127
 Thur. 03/18:

We will finish up the "Private capacity and quantum capacity ..."
and start
"Family of protocols for capacities of quantum channels"
quantph/0308044
 Tues. 03/23:
 Spring Vacation
 Thur. 03/25:
 Spring Vacation
 Tues. 03/30:

Family of protocols for capacities of quantum channels
quantph/0308044
 Thur. 04/01:
 Fault tolerance by decoherence free subspaces
This is contained in
quantph/9908064,
and possibly the followup
quantph/0007013.
 Tues. 04/06:

Quantum toric codes.
presented by Victor Brar
 Thur. 04/08:

Topological quantum memory
quantph/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
quantph/9511027.
quantph/0003040.
quantph/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 quantph number for
the first paper in this week. I've fixed it below.
Security proofs of Bennett 92
quantph/0212162.
quantph/0308048.
 Thur. 04/29:

Quantum vs. classical memory presented by Fen Zhao
quan`tph/0305154.
 Tues. 05/04:

Algorithm for dihedral hidden subgroup problem, by Kuperberg
quantph/0302112,
presented by Aram Harrow.
 Thur. 05/06:

Other new quantum algorithms. (Pell's equation,
quantph/0302134,
and if we have time, hidden shift problems
quantph/0211140,
 Tues. 05/11:

David Milovich
"A lambda calculus for quantum computation"
quantph/0307150,
 Thur. 05/13:

Debajyoti Bera
This paper
on one dimensional random walks, and
Absorption problems for quantum walks in one dimension,
quantph/0208122,
and I'll talk a little bit about quantum communication complexity
if there's any time left over.
Here are the topics I am planning to go over.
 Quantum
Complexity Theory: QMA (the quantum equivalent of NP), Quantum interactive
proofs, QPSPACE = PSPACE.
 Quantum channel capacities and quantum data compression
(teleportation, superdense coding, Schumacher compression,
remote state preparation, classical and quantum capacities of a
quantum channel).
 Proofs of security in quantum cryptography
 Quantum faulttolerance via topological codes (Kitaev's paper on
torus codes; if I'm ambitious, maybe Kitaev's paper on quantum
computing and faulttolerance through anyons).
 Quantum communication complexity (Maybe).
 More quantum algorithms (Maybe).
I am open to suggestions from students as to other areas to cover.