18.419 Course Home Page

Office Hours

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.

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 fault-tolerance via topological codes (Kitaev's paper on torus codes; if I'm ambitious, maybe Kitaev's paper on quantum computing and fault-tolerance through anyons).
• Quantum communication complexity (Maybe).
• More quantum algorithms (Maybe).